6

長い説明よりも例の方がはるかに優れていると思います:)

配列の配列があるとしましょう:

("Server1", "Server_1", "Main Server", "192.168.0.3")
("Server_1", "VIP Server", "Main Server")
("Server_2", "192.168.0.4")
("192.168.0.3", "192.168.0.5")
("Server_2", "Backup")

各行には、同義語である文字列が含まれています。そして、この配列の処理の結果として、私はこれを取得したい:

("Server1", "Server_1", "Main Server", "192.168.0.3", "VIP Server", "192.168.0.5")
("Server_2", "192.168.0.4", "Backup")

そのため、一種の再帰アルゴリズムが必要だと思います。プログラミング言語は実際には問題ではありません — 一般的なアイデアについて少しだけ助けが必要です。私はphpまたはpythonを使用するつもりです。

ありがとうございました！

4

5 に答える 5

6

この問題は、グラフ内の接続されたノードのすべてのグループを見つけるグラフ理論の問題に還元できます。

この問題を解決する効率的な方法は、「フラッド フィル」アルゴリズムを実行することです。これは、基本的に再帰的なブレス ファースト検索です。このウィキペディアのエントリでは、フラッド フィル アルゴリズムと、それをグラフの接続領域を見つける問題の解決にどのように適用するかについて説明しています。

元の質問をグラフ上の質問にする方法を確認するには、各エントリ (「Server1」、「Server_1」など) をグラフ上のノードにします。ノードが同義語である場合にのみ、ノードをエッジで接続します。マトリックス データ構造は、十分なメモリがあれば、エッジを追跡するのに特に適しています。それ以外の場合は、特にシノニムの数が制限される可能性が高いため、マップのような疎なデータ構造が機能します。

  • Server1 はノード #0
  • Server_1 はノード #1 です
  • Server_2 はノード #2

次に、edge[0][1] = edge[1][0] = 1 は、ノード #0 と #1 の間にエッジがあることを示します (これは、それらが同義語であることを意味します)。edge[0][2] = edge[2][0] = 0 の場合、Server1 と Server_2 が同義語ではないことを示します。

複雑性分析

このデータ構造の作成は非常に効率的です。これは、文字列からノード番号へのマッピングのルックアップを伴う単一の線形パスで十分にクレートできるためです。文字列からノード番号へのマッピングを辞書に保存する場合、これは O(n log n) ステップになります。

フラッド フィルの実行は O(n) であり、グラフ内の各ノードに 1 回だけアクセスします。したがって、全体のアルゴリズムは O(n log n) です。

于 2011-05-26T06:40:23.627 に答える
2

同義語グループを示す整数マーキングを導入します。1最初に、すべての単語に からまでの異なるマークを付けますN。

次に、コレクションを検索し、インデックスがiありj、同義語である2 つの単語を見つけた場合は、両方の単語の数が少なく、マークiが付いているすべての単語にコメントします。j繰り返しの後N、類義語のすべてのグループを取得します。

これは、いくつかの汚れた、完全に効率的なソリューションではありません。共用体検索構造を使用すると、パフォーマンスが向上すると思います。

于 2011-05-26T06:34:31.840 に答える
1

編集：これはおそらくあなたの問題を解決するための最も効率的な方法ではありません。最大のパフォーマンスに関心がある場合（たとえば、数百万の値がある場合）、より複雑なアルゴリズムを作成することに関心があるかもしれません。

PHPは機能しているようです（少なくとも特定の例のデータでは）：

$data = array(
    array("Server1", "Server_1", "Main Server", "192.168.0.3"),
    array("Server_1", "VIP Server", "Main Server"),
    array("Server_2", "192.168.0.4"),
    array("192.168.0.3", "192.168.0.5"),
    array("Server_2", "Backup"),
);

do {
    $foundSynonyms = false;
    foreach ( $data as $firstKey => $firstValue ) {
        foreach ( $data as $secondKey => $secondValue ) {
            if ( $firstKey === $secondKey ) {
                continue;
            }
            if ( array_intersect($firstValue, $secondValue) ) {
                $data[$firstKey] = array_unique(array_merge($firstValue, $secondValue));
                unset($data[$secondKey]);
                $foundSynonyms = true;
                break 2; // outer foreach
            }
        }
    }
} while ( $foundSynonyms );

print_r($data);

出力：

Array
(
    [0] => Array
        (
            [0] => Server1
            [1] => Server_1
            [2] => Main Server
            [3] => 192.168.0.3
            [4] => VIP Server
            [6] => 192.168.0.5
        )

    [2] => Array
        (
            [0] => Server_2
            [1] => 192.168.0.4
            [3] => Backup
        )

)
于 2011-05-26T06:52:58.403 に答える
1

これにより、PHP の例 (Python 3) よりも複雑さが軽減されます。

a = [set(("Server1", "Server_1", "Main Server", "192.168.0.3")),
    set(("Server_1", "VIP Server", "Main Server")),
    set(("Server_2", "192.168.0.4")),
    set(("192.168.0.3", "192.168.0.5")),
    set(("Server_2", "Backup"))]

b = {}
c = set()
for s in a:
    full_s = s.copy()
    for d in s:
        if b.get(d):
            full_s.update(b[d])
    for d in full_s:
        b[d] = full_s
    c.add(frozenset(full_s))

for k,v in b.items():
    fsv = frozenset(v)
    if fsv in c:
        print(list(fsv))
        c.remove(fsv)
于 2011-05-26T08:45:37.193 に答える