4

メモリにT9辞書があります（trie / hash_map）。辞書には単語評価のペアが含まれているため、辞書から単語が選択されると、その評価が増加し、単語評価のペアが単語リストに表示されます。

辞書から単語を選ぶ方法があるとしましょう。そのメソッドは、いくつかの単語評価ルーチンも実行します。

入力には、電話で押された数字の文字列（1〜9、単語を変更するための「*」および「」）があります。

質問：

  1. 文字列を高速に解析するアルゴリズムはありますか？
  2. どのデータ構造がそこに適しているでしょうか？

UPD：

問題の全文（問題D）

Hash_mapの実装

実装を試す

4

1 に答える 1

8

私が特に効率的だと思う1つのオプションは、キーストロークに基づいて単語を予測するために特別に最適化された変更された構造にトライを前処理することです。

直感的には、新しい構造は、任意の時点で押される可能性のある数字から作成されたトライです。次に、各トライノードは、それらの数字を使用してスペルアウトされる可能性のある単語の優先キューを格納します。次に、次のアルゴリズムを使用して、使用する単語を予測できます。

  • トライのルートから始めます。
  • 各桁について、その桁に対応するポインタをたどります。
  • トライを離れる場合、提案はありません。
  • それ以外の場合は、これらの数字から正確に形成できる単語の優先度付きキューを調べてから、その優先度付きキュー内で使用回数が最も多い要素を提案します。

このアルゴリズムには時間がかかりますO（n + T max）。ここで、nは数字の文字列の長さであり、Tmaxは指定されたプレフィックスで最も人気のある単語を見つけるのに必要な時間です。これは、バイナリヒープのようなものではO（1）になる可能性がありますが、より複雑なヒープでは遅くなる可能性があります。

このデータ構造を構築するには、次のように単語/頻度の元のリストを前処理します。単語ごとに、その文字に対応する一連の数字を決定します。たとえば、「monsoon」という単語は6667666になり、「apple」という単語は27753になります。次に、そのシーケンスを数字のトライに挿入し、必要に応じて新しいノードを作成します。この数字列に対応する最後のノードに到達したら、そのノードの対応する優先度キューに単語を挿入します。この操作の合計時間は実際にはかなり良いです。合計n文字の単語のリストが与えられた場合、これはO（n T insert）時間で実行できます。ここでT insert優先キューに単語を挿入するのに必要な時間です。これは、各文字に最大3回アクセスする必要があるためです。1回は数字に変換するため、1回は数字のトライの適切なエッジをたどるため、もう1回は優先キューに挿入するためです。

このアプローチにより、新しい単語を予測子に非常に簡単に挿入することもできます。ユーザーが数字のトライから離れたり、ナンバーワンの単語ではない単語を選択したりするときはいつでも、トライに適切な一連のノードを作成し、その単語を正しい優先度に挿入することで、その単語を数字のトライに挿入できます。列。

最小要素へのポインタを格納する平衡二分探索木から優先キューを作成すると、O（n）時間で一連のn桁の最速の単語を検索するように実装でき、その後、すべての言い換えると、償却されたO（1）時間ごとにその接頭辞が付いています。この方法で、新しい単語を非常に簡単に挿入または削除することもできます。

単語はトライに格納されているため、O（1）では、現在のトライノードから現在の番号で指定された子ノードに移動するだけで、現在の単語の推測を更新できます。ユーザーがスペースキーを押すと、数字のトライのルートにリセットされます。最後に、ユーザーがスターをヒットすると、上記のトリックを使用して、特定のトライノードで次に人気のある単語を確認できます。

お役に立てれば！

于 2011-08-26T22:35:43.467 に答える