大量のテキストで最も一般的なフレーズを見つける効率的なアルゴリズム

Question

大量のテキストに最も一般的なフレーズを収集するプログラムを作成することを考えています。問題が、単に新しい単語をハッシュマップに格納してから、それぞれの出現回数を増やすほど単純な単語を見つけることにまで減らされていたかどうか。しかし、フレーズでは、文の各順列をキーとして格納することは実行不可能に思えます。

基本的には、十分な大きさのテキストからすべての可能なフレーズを抽出する方法を見つけることに問題が絞り込まれています。フレーズを数え、出現回数でソートするのは簡単です。

Answer 1

同じ順序で表示される連続する単語の共通パターンを検索しているとします（たとえば、「世界のトップ」は「世界のトップ」または「トップの世界」と同じ句として数えられません"）。 （つまり、大文字、句読点、単語の区切りなどを削除）

1. 言葉にあなたのテキストを分割し、あなたが重要な考慮しないものを削除します。

   もしそうなら、私は、次の線形時間のアプローチは推薦します

2. テキストを整数の配列（ユニークワードごとに1つの整数）に変換します（たとえば、 "cat"のすべてのインスタンスが1になり、すべての "dog"が2になります）。これは、ハッシュベースの辞書を使用して、単語から数字への変換を保存する。単語が辞書にない場合は、新しいIDを割り当てます。最長共通の構築
3. から
4. （アルゴリズムとCコードhereを使用して例えば、これはあなたの配列のすべてのサフィックスのソートされたリストで、線形時間で構築することができる）整数の配列のための接尾辞アレイを構築接尾辞配列の接頭辞配列。これは、例えばC codeを使用して線形時間で行うこともできます。このLCP配列は、接尾辞配列内の連続する対の間の各接尾辞の先頭にある共通語の数を示します。

これであなたの共通のフレーズを集めることができるようになりました。

フレーズの終わりをどのように判断したいかははっきりしません。 1つの可能性は、繰り返す4単語のすべてのシーケンスを単純に収集することです。
これは、最長の共通接頭辞配列が> = 4である場所を見て接尾辞配列を操作することによって、線形時間で実行できます。[start + 1 ... start + len] LCP [x] = 4（xの最後の値を除くすべての値）は、len回繰り返されるフレーズに対応します。フレーズ自体は、たとえば、接尾辞start + 1の最初の4語で与えられます。

このアプローチでは、文章の終わりのフレーズが見つかる可能性があることに注意してください。これを防ぐには、フルストップなどの句読点を一意の整数に変換することをお勧めします。