aho corasickのスケーラビリティ

Question

私は、キーフレーズ（ウィキペディアの記事タイトルから抜粋）のデータベースから、キーフレーズの出現をテキスト文書で検索したいと考えています。 （すなわち、文章のいずれかに対応するウィキペディアの記事があるかどうかを調べたい文書がある場合）、Aho-Corasickアルゴリズムについて知りました。何百万というエントリの辞書のAho-Corasickオートマトンを構築するのが効率的でスケーラビリティがあるかどうかを知りたい。

Answer 1

理論上は線形速度の対象はメモリ階層の影響のみを維持する必要があります。キャッシュに入るには大きすぎるほど速度が遅くなり、実際に大きくなると問題が発生しますページアウトが始まります。

OTOH Aho-Corasickとの大きな勝利は、フィードインされている文字列内の任意の場所で発生する可能性のある適切なサイズの部分文字列を検索する場合です。テキスト文書が既に単語に切り詰められていて、より多く6語の長さであれば、K-単語フレーズのハッシュテーブルを作成し、K = 1..6の場合、その中の入力テキストから単語のすべてのK-単語連続セクションを検索することができます。あなたはあらゆる場所にポインタを辿ることになるので、

（コメントするに回答）

アホ - Corasickは、メモリに住んでする必要があります。メモリ外で作業しなければならない場合は、旧式のソート/マージに戻るのが最も簡単でしょう。入力データからK単語レコードのファイルを作成します。ここで、Kは関心のある任意のフレーズの単語の最大数です。並べ替えて並べ替えられたWikipediaのフレーズのファイルとマージします。 Unix/Linuxでは、並べ替えや結合などのユーティリティや、shell/awk/perl/etcのようなユーティリティを使用して、ほとんどこれを手作業で行うことができます。 http://en.wikipedia.org/wiki/Key_Word_in_Contextも参照してください（私は実際にこれらのインデックスの1つを使用するのに十分古く、コンピュータの印刷出力のバインドされたページとして提供されています）。

Answer 2

回避策があります。構築された辞書のACトライをXML形式のテキストファイルに書き込んで、そのトライの最初の6つのレベルのインデックスファイルを作成します。私のテストでは、辞書（500'000エントリ）、150〜200シンボルの文に対して〜100の結果に対して〜150msが得られます。詳細については

、この論文をチェックアウト：http://212.34.233.26/aram/IJITA17v2A.Avetisyan.doc

Answer 3

はちょうど簡単な計算をしてみましょう：

は、あなたが100万のパターン（文字列、フレーズ）を持っていると仮定し、平均長さ10個の文字と値を（各パターンに割り当てられた1ワード（4バイト）の長さのラベル、ラベル、トークン、ポインタなど）

パターンのリストを保持するために10 + 4 = 1400万バイト（14Mb）の配列が必要です。

10万ノード以下のACトライを構築するには、それぞれ100万個のパターンから10バイト（文字、文字）を作成できます。このトライの実際の大きさは、各ノードのサイズによって異なります。 trie（または端末ノードのパターン）の次のノードへのポインタのラベル（文字）と単語（4バイト）に1バイトを加え、端末ノードをマークするために1ビット（ブール値）を加えてください。 合計約5バイト

したがって、100万パターンのトライの最小サイズは10文字です。必要なメモリは、最小5,000万バイトまたは約50Mバイトです。

現実的には、3〜10倍の可能性がありますが、今日でも500Mbのメモリでも非常に緩やかなので、非常に管理しやすいです。（WordやOutlookなどのWindowsアプリケーションと比較する）

Aho-Corasick（AC）アルゴリズムの速度に関しては、ほぼ無敵であることを考えると、これまでのところ、それは学問的なごみ以外の個人的な教育的意見です。

ACを上回る可能性がある「新しい」最新かつ最高のアルゴリズムのすべてのレポートが（多分DNAのような短いパターンで、いくつかの特別な場合を除いて）非常に誇張されている

ACの唯一の改善は、実際にラインに沿って行くことができますより多くの高速なハードウェア（複数のコア、より高速なCPU、クラスタなど）

私の言葉を取って、自分でテストしないでください。しかしACの実際のスピードは実装（言語とコーディングの質）に強く依存することに注意してください。