string - 与えられた文でどの単語が発生しているかを見つける

Question

私は単語のリストを持っています。単語数は約100万語。

リストのどの単語が文字列に存在するかを確認し、その単語を返す必要があります (文に含まれるすべての単語を返す必要はなく、最初の単語を返すだけで十分です)。

解決策の 1 つは、文字列内のすべての単語を 1 つずつチェックすることですが、効率的ではありません。

誰かがそれを行う効率的な方法を指摘できますか?

Answer 1

Knuth-Morris-Prattアルゴリズムを使用します。百万の言葉はそれほど多くはありませんが。テキスト本文をトライ構造に変換し、それを使用して検索リストをチェックすることもできます。特に全文検索に使用されるSuffix Treeと呼ばれる特別な種類の Trie があります。

Answer 2

二分探索を実行するために単語のリストが順序付けられている (または順序付けられた二分木のような効率的なデータ構造に挿入されている) 場合を除き、提案している解決策は最も効率的な解決策です。

Answer 3

単語リストをツリーまたはハッシュ テーブルに入れます。