単語のグループで一致するフレーズを見つける

Question

テキストファイルを解析し、単語の数を数えて降順にソートするプログラムを作成しました。これは素晴らしいですが、私は別のレベルを取り上げたいと思います。

私は繰り返されるテキスト内の単語フレーズを見つけることができるようにしたいと思います。キー私はちょうどソートザ・キーと出力とに基づいている

その後、

hash: 
    "word":3, 
    "test":12, 
    ..... 

：

私の現在のアルゴリズムでは、最初にその単語とハッシュテーブルを作成し、この値のようにカウント言葉にアップしたテキストを分割することです出来ました。

Happy Birthday to You 
Happy Birthday to You 
Happy Birthday Dear (name) 
Happy Birthday to You. 

From good friends and true, 
From old friends and new, 
May good luck go with you, 
And happiness too. 

Alternative ending: 
How old are you? 
How old are you? 
How old, How old 
How old are you? 

私はワードカウントをうまく得ることができますが、私はすべてのフレーズにマッチしたい場合：

だが、私はこの幸せな誕生日の歌を持っているとしましょうか？

例えば、この6ワードがフレーズが二回一致すると言える。

happy birthday to you happy birthday 

対5ワードフレーズ一致：

birthday to you happy birthday 
happy birthday to you happy 

一部4ワードフレーズ

how old are you 
happy birthday to you 
to you happy birthday 
how old how old 
birthday to you happy 

と一致します

など、一致する単語フレーズは2つまでです。

私は、行間でもフレーズ全体を照合することにもっと関心があります。なぜなら、今後の処理のために出力を調べなければならないからです。

私はこの目標を達成するためにどのようなアルゴリズムを使用できますか？

Answer 1

まず、あなたの言語を使って、簡単に言葉を繰り返すようにする簡単な正規表現でトークンをトークン化したいかもしれませんすべての空白/改行文字のString.splitメソッド。そのような文字列配列を残す必要があります：["Happy", "birthday", "to", "you", "happy", ...]。後で正規表現を使用する場合は、文字列を小文字にする必要はありません。

for (var start = 0; start < tokens.length; start+=1) { 
    for (var end = start; end < tokens.length; end+=1) { 
     var phrase = tokens.slice(start, end) 
     // Count occurrences of phrase ... 
    } 
} 

は、上記の開始点として、すべての単語を使用します。

、あなたはstartとendポインタを作成し、そのように反復することによって達成することができ通路からフレーズを抽出する必要があることに続き抽出と、その後のすべての単語を抽出の終点として使用して、単一の単語およびフレーズ全体をphraseで取得することができます。これらのフレーズの（n + n^2）/ 2が（私の数学が正しければ）あることに注意してください。だから、このことは指数関数的な成長をしています。終了するまでフレーズのすべてを積極的に保存している場合は、大きなデータの場合にメモリ使用量がかなり大きくなる可能性があります。

正規表現の一致自体は、指定されたフレーズの出現回数を見つけることができるため、ハッシュテーブルを使用して作業結果を保存することに限定されません。あなたは、その節に複数の出現があるフレーズを保存するだけで、メモリに保存することができます。

Answer 2

単語の組み合わせで同じアルゴリズムを使用できます。 最大サイズnのキューを使用すると、最後のn個の単語を（たとえばイテレータを使用して）連結し、ハッシュテーブルに追加できます。 のnまでのn = 2を繰り返し、これを>（あなたの#words/2）、またはまったく繰り返しが

例 見つからなかった「W1 W2とW3は、 W3 W1 W2。」

は、ハッシュテーブルを与える必要があります。.. 2 「W2 W3“ ：1 「W3 W3“ ：1 「W3 W1“ ： HASH2： 「W1、W2“ 1 ..for N = 2、N = 3の場合 （大文字とカンマを無視します）あなたの最高カウントは1になり、あなたは壊れる可能性があります

Cleあなたの単語リストの改行と連結が必要かもしれない場合には空白の空白を使用する