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

Question

大量のテキストから最も一般的なフレーズを収集するプログラムを作成することを考えています。問題が単語を見つけるだけに縮小された場合、新しい単語をそれぞれハッシュマップに格納し、出現ごとにカウントを増やすのと同じくらい簡単になります。しかし、句の場合、文の各順列をキーとして保存することは実行不可能に思えます。

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

Answer 1

同じ順序で出現する連続する単語の一般的なパターンを検索していると仮定します (たとえば、「世界のトップ」は「世界のトップ」または「トップの世界」と同じフレーズとしてカウントされません)。

もしそうなら、次の線形時間アプローチをお勧めします。

1. テキストを単語に分割し、重要でないと思われるものを削除します (つまり、大文字、句読点、単語の区切りなどを削除します)。
2. テキストを整数の配列 (一意の単語ごとに 1 つの整数) に変換します (たとえば、"cat" のすべてのインスタンスが 1 になり、すべての "dog" が 2 になります)。単語から数字への変換。単語が辞書にない場合は、新しい ID を割り当てます。
3. 整数の配列の接尾辞配列を構築します (これは、配列のすべての接尾辞のソートされたリストであり、線形時間によって構築できます。たとえば、ここのアルゴリズムと C コードを使用します) 。
4. 接尾辞配列の最長共通接頭辞配列を構築します。(これは、たとえば、このC コードを使用して線形時間で行うこともできます) この LCP 配列は、接尾辞配列内の連続するペア間の各接尾辞の先頭にある共通語の数を示します。

これで、一般的なフレーズを収集することができます。

フレーズの終わりをどのように決定したいかは、あまり明確ではありません。1 つの可能性は、繰り返される 4 つの単語のすべてのシーケンスを単純に収集することです。
これは、最も長い共通プレフィックス配列が >= 4 である場所を調べるサフィックス配列を処理することにより、線形時間で実行できます。範囲 [start+1...start+len] 内のインデックス x の各実行は、LCP[ x] >= 4 (x の最後の値を除くすべて) は、len 回繰り返されるフレーズに対応します。句自体は、たとえば接尾辞 start+1 の最初の 4 語で指定されます。

このアプローチは、文末をまたぐフレーズを検出する可能性があることに注意してください。これを防ぐために、ピリオドなどの句読点を一意の整数に変換することをお勧めします。