キーフレーズのデータベース（ウィキペディアの記事のタイトルから抽出）から、テキストドキュメントでキーフレーズの出現を検索したいと思います。（つまり、ドキュメントがあれば、対応するウィキペディアの記事があるフレーズがあるかどうかを調べたい）Aho-Corasickアルゴリズムについて知りました。何百万ものエントリの辞書用にAho-Corasickオートマトンを構築することが効率的でスケーラブルかどうかを知りたいです。
3571 次
4 に答える
12
簡単な計算をしましょう：
平均長が 10 文字で、各パターンに割り当てられた 1 単語 (4 バイト) の長さの値 (ラベル、トークン、ポインターなど) を持つ 100 万のパターン (文字列、フレーズ) があるとします。
次に、パターンのリストを保持するためだけに、10+4=1400 万バイト (14Mb) の配列が必要になります。
それぞれ 10 バイト (文字、文字) の 100 万のパターンから、1000 万以下のノードで AC トライを構築できます。このトライの大きさは、実際には各ノードのサイズによって異なります。少なくとも、ラベル (文字) 用に 1 バイト、トライ (またはターミナル ノードのパターン) 内の次のノードへのポインター用にワード (4 バイト) と、ターミナル ノードをマークするための 1 ビット (ブール値) を保持する必要があります。合計約 5バイト
したがって、100 万パターン 10 文字のトライの最小サイズは、最小 5000 万バイトまたは約 50 Mb のメモリが必要になります。
実際には 3 ～ 10 倍になる可能性がありますが、500Mb のメモリでさえ今日は非常に適度であるため、非常に扱いやすいです。(Word や Outlook などの Windows アプリケーションと比較してください)
Aho-Corasick (AC) アルゴリズムは速度の点でほとんど無敵であり、複数のパターン マッチに最適なアルゴリズムであることに変わりはありません。それは、学問的なゴミは別として、私の強い個人的な教育を受けた意見です。
AC を上回る可能性のある「新しい」最新かつ最高のアルゴリズムに関するすべてのレポートは、非常に誇張されています (DNA のような短いパターンの特殊なケースを除く)。
実際には、AC の唯一の改善点は、より多くのより高速なハードウェア (複数のコア、より高速な CPU、クラスターなど) に沿って進む可能性があります。
私の言葉を鵜呑みにしないで、自分で試してみてください。ただし、AC の実際の速度は実装 (言語とコーディングの品質) に大きく依存することを覚えておいてください。
于 2012-12-04T16:44:59.410 に答える
6
理論的には、メモリ階層の影響のみを受けて線形速度を維持する必要があります。キャッシュに収まらないほど大きくなると速度が低下し、非常に大きくなると、ページアウトが開始されると問題が発生します。 。
OTOH Aho-Corasickの大きなメリットは、入力された文字列内の任意の場所で発生する可能性のある適切なサイズの部分文字列を検索する場合です。テキストドキュメントがすでに単語に分割されていて、検索フレーズが6以下の場合単語の長さの場合、K単語のフレーズのハッシュテーブルを作成し、K = 1..6の場合、その中の入力テキストから単語のすべてのK単語の連続するセクションを検索できます。
（コメントへの回答）
Aho-Corasickはメモリ内に存在する必要があります。これは、あちこちでポインタを追跡するためです。メモリの外で作業する必要がある場合は、昔ながらの並べ替え/マージに戻るのがおそらく最も簡単です。入力データからK-wordレコードのファイルを作成します。ここで、Kは、関心のあるフレーズの最大単語数です。並べ替えてから、並べ替えられたWikipediaフレーズのファイルとマージします。これは、Unix / Linuxで、sortやjoinなどのユーティリティと、少しのshell / awk / perl / whateverを使用して、ほぼ手作業で実行できる可能性があります。http://en.wikipedia.org/wiki/Key_Word_in_Contextも参照してください（私は、コンピューターの印刷物のバインドされたページとして提供される、これらのインデックスの1つを実際に使用したのに十分な年齢です）。
于 2011-02-27T17:27:34.537 に答える
1
さて、回避策があります。構築された辞書の AC トライを xml のような形式でテキスト ファイルに書き込み、そのトライの最初の 6 レベルのインデックス ファイルを作成するなど... 私のテストでは、辞書 (500'000 エントリ)、および 150-200 記号の文に対して ~100 の結果に対して ~150ms を取得します。
詳細については、このペーパーをご覧ください: http://212.34.233.26/aram/IJITA17v2A.Avetisyan.doc
于 2011-06-07T14:42:39.867 に答える
0
パフォーマンスを向上させる方法は他にもあります: - 状態遷移を圧縮: 32 ビットまで下げることができます。- ポインターを捨てます。状態遷移をフラット ベクトルに書き込みます。- ツリー ルートの近くにあるノードをまとめてパックします。それらはキャッシュに格納されます。実装には、元のパターン セットの 1 文字あたり約 3 バイトが必要であり、32 ビット ノードの場合、約 10M 文字のパターン空間を使用できます。64 ビット ノードの場合、まだ制限に達していない (または計算していない)。
ドキュメント: https://docs.google.com/document/d/1e9Qbn22__togYgQ7PNyCz3YzIIVPKvrf8PCrFa74IFM/view ソース: https://github.com/mischasan/aho-corasick
于 2018-08-25T21:28:30.040 に答える