単純な単語のオートコンプリートは、既に入力された文字に一致する単語のリストを表示するだけです。しかし、テキストコーパスの統計モデルに依存して、以前に入力された単語に応じて、単語が発生する確率に従ってオートコンプリートリストの単語を並べ替えたいと思います。これにはどのようなアルゴリズムとデータ構造が必要ですか? 良いチュートリアルへのリンクを教えてもらえますか?
12233 次
2 に答える
14
オートコンプリートの確率は必要ありません。代わりに、コーパス内の単語をキーとして、その頻度を値として使用して、プレフィックス ツリー(別名trie ) を構築します。部分的な文字列に遭遇したら、できる限りトライをたどり、到達したポイントからすべての接尾辞を生成し、それらを頻度順に並べ替えます。
ユーザーが以前に見たことのない文字列を入力すると、頻度 1 でトライに追加されます。ユーザーが見た文字列を (おそらく候補リストから選択して) 入力すると、その頻度が増加します。
[確率モデルでは単純なインクリメントはできないことに注意してください。最悪の場合、モデル内のすべての確率を再計算する必要があります。]
この種のアルゴリズムをさらに深く掘り下げたい場合は、Jurafsky と Martin によるSpeech and Language Processing (の最初の章) を読むことを強くお勧めします。言語処理の離散確率をかなり詳細に扱います。
于 2012-07-12T10:03:05.587 に答える
6
Peter norvigは、Googleの「あなたはどういう意味ですか...？」ベイズ推定を使用して効果的に機能する機能。これは非常に優れた読み物であり、オートコンプリート機能に適応できるはずです。
于 2012-07-12T09:48:24.433 に答える