単語とフレーズのリストに近い一致のリストを効率的に見つける

Question

アルゴリズムを探していますが、問題の名前がわからないので何も見つかりません。うまくいけば、問題の私の説明は意味をなさない！

あなたが長いフレーズのリストを持っているとしましょう。各フレーズは単語のセットです。ユーザは単語のリストを入力し、そのリストはそのフレーズ内のすべての単語がそのリスト内に見つかるフレーズに「一致する」。リストの「スコア」は、一致するフレーズの数です。目標は、リストのスコアを最も向上させる単語のリストをユーザーに提供することです。

ここに簡単な例があります。我々は10個のフレーズ持っている：森の中で

1. ウッドキャビン
2. キャンプを
3. キャンプキャビン
4. 楽しいキャンプ
5. ボン火災
6. キャンプファイヤー
7. スイミング穴
8. 楽しいキャビン
9. 木の火
10. 暖炉

そして、ユーザーは、このリストを提供します：

キャンプ

• 木材
• 楽しい
• は、我々はフレーズ1と4と一致し、そのスコアがありますしかし、ユーザーが「キャビン」をリストに追加すると、さらに3つのフレーズが一致し、スコアが5になります。「火災」は2に追加されますスコア。

  ほとんどの時間をかけてオプションを繰り返すことができるので、複雑な問題はほとんどありません。しかし、リストが数十万に増えると、数百ミリ秒もかかり始める。プロセスをより速くするためのインデックスを作成する方法があるはずだが、インデックスの構造を考えることはできないと思う。

  このすべてを読む時間がかかった人は、ありがとう！うまくいけば誰かが私が話していることを知っているだろう。

Answer 1

単語を出現回数にマップする必要があります。ハッシュテーブルを使用すると、非常に素早く行うことができます（O（N） - フレーズ内の単語の数をNとする） - すべてのフレーズをループし、単語を分割します。カウントしていない場合は、カウント1のマップに追加します。

入力のスコアを計算するには、入力単語をループして出現回数を累積します。 O（M） - この時間Mは入力語の数である。

私はあなたがより良い（少なくとも1回はフレーズをスキャンする必要があります）、地図の適切な実装（ほとんどすべての現代の言語で利用可能）を得ることはできません。

Answer 2

サフィックスツリー。

これらはむしろばかばかしく複雑なものですが、基本的に各文字（26 * 2）のノードを保存してから、各文字の接尾辞を格納しますので、thやanなどのエントリはおそらくqjまたはそれ以外の組み合わせは発生しません。次に、それらのサフィックスを取得します（3つの文字の組み合わせは許可されません）。 非常に高速な検索が可能ですが、正確である必要はありません。 a * dに一致させたい場合は、aの接尾辞の後ろにdの接尾辞をつけて、それからnulを主張します。