テキストファイルからの単語候補のデータ構造

Question

問題：テキスト行にテキストが多数含まれています。これでユーザーはいくつかの文字を入力し、与えられたファイル内のテキストに基づいて提案を自動補完する必要があります。 ファイルにcomputer science is fun. computer engineering is awesomeが含まれているとします。 ユーザーがcomと入力した場合、提案としてcomputer scienceとcomputer engineeringとする必要があります。ユーザーがisと入力した場合、提案はfunとawesomeである必要があります。ユーザは、テキストファイル内にあるかもしれない単語を入力することができる。単語がファイルにない場合は、提案はありません。

この問題の最適なデータ構造は何でしょうか。
私はトライを作ることができると知っていますが、ユーザーがcomと入力すると、computerしか提案できないことがあります。

ありがとうございました。

Answer 1

準備：

1. ソート辞書的にこの配列

クエリ文字列

の配列として、テキストファイルのすべての行を読む：

1. がlower boundインデックスを取得します。入力文字列：first
2. 入力文字列の最後の文字の値を1（最大値でない場合）に増やし、この新しい入力文字列ののインデックスlower boundを取得します。最後の文字を増やせない場合は、arrrayの終わりを過ぎたインデックスを使用してください。 [first, last)：

すべての可能な提案が最後のインデックスを含まないこれらの2つの境界の間にソートされた配列です。

提案が多すぎる場合は、3つの短い提案を提案するか、統計的な頻度で並べ替えるだけでフィルタリングできます。

提案の数を提案する代わりに印刷することもできます。 googleがあなたのクエリと一致するページの数を示す方法と同様です。そして、マッチの数があなたのUIによって管理可能な場合にのみ、文字列を提案します。