0

アイテムの配列 (〜 5000 アイテム、各アイテムは英単語) と、アイテムのペア間の距離関数があります。グループ内のすべてのアイテムが距離基準を満たす配列内のアイテムのグループを検索したい (たとえば、アイテムのすべてのペアの距離が 2 より小さい)。通常、グループはできるだけ大きくする必要がありますが、これに関する正式な定義や厳密な要件はありません。

私の実装言語は PHP ですが、これを効率的に処理できるアルゴリズムに関する一般的なアドバイスを探しています。

更新:頂点がアイテムであるグラフを作成することでこれを解決できると思います。距離の制約を満たすアイテム間にエッジがあります。グラフを作成したら、Bron–Kerbosch のようなアルゴリズムを実行して、すべての最大クリークをリストできます。これがうまくいった場合は更新しますが、その間にあなたの考えを自由に追加してください.

4

3 に答える 3

1

この関数はどのように定義されていますか? 事前に計算されていますか？その場合、計算された関数表現を反復処理し、基準に基づいて単語のペアを取得できます。そうでない場合は、単語のすべてのペア間の関数を計算する以外に選択肢はありません (これはグラフ アプローチで必要です)。Bron-Kerbosch アルゴリズムの代わりに、次のようなランダム化 + 近似戦略を使用します。

http://dimacs.rutgers.edu/Workshops/Challenge10/abstracts.html#ovelgonne

http://dl.acm.org/citation.cfm?id=1933306.1934471

これは、モジュール性を最大化するアプローチに基づいています。モジュール性は、クラスター内のエッジ数に対するクラスター内の発信エッジ数の比率です。あなたの場合、比率が 0 のクラスターを探し、それらの中で最大のものを選択します。このアルゴリズムは非常に高速で、私が扱ったほとんどのデータセットで機能します。モジュール性ベースの方法はこの問題に対して過剰かもしれませんが、私はこれが問題を考える良い方法だと思います + このアルゴリズムの実装はオンラインで入手できます (論文の著者による C 実装)。

于 2013-07-25T21:17:05.627 に答える
0

私が問題を理解しているのは次のとおりです。

「AG」は言葉の略です。" # " は 2 つの単語の間の距離を表します。そして、距離 <= 2 のペアを見つける必要があります。

  A B C D E F G
A * # # # # # #
B   * # # # # #
C     * # # # #
D       * # # #
E         * # #
F           * #
G             *

基本的には 2 レベルのループが必要です。できることは、比較時間を短縮することです。上記のマトリックスの "#" 部分のみを比較します。PHPのコードは次のとおりです。

$result = array();
while ( ($word = array_shift($arrWordList)) !== NULL ) {
    foreach ($arrWordList as $otherWord ) {
        if ( calc_dist($word, $otherWord) <= 2 ) {
            $result[] = array($word, $otherWord);
        }
    }
}

そして、$result を使用して何かを続けることができます。

于 2013-07-22T10:51:50.460 に答える
0

条件をグループのすべてのメンバーに適用する場合は、グループの重複を可能にするクラスタリング アルゴリズムが必要です。これはかなり複雑なテーマなので、クラスタリング アルゴリズム、特に重複するグループ用に設計されたC-Means Clusteringに関する文献を参照することをお勧めします。

于 2013-07-22T10:59:21.623 に答える