autocomplete - オートコンプリートアルゴリズム、論文、戦略など

Question

「オートコンプリート」を試すための優れたリソースやコードを誰かが持っているかどうか疑問に思っています

オートコンプリートの背後にある理論、どこから始めればよくある間違いなどを知りたいです。

Enso、Launchy、Google chrome、さらには tcsh などの製品がオートコンプリートを実行する方法に魅力を感じ、いくつかのサンプルコードを好奇心で始めたところ、これは以前に広く調査された分野であるに違いないという結論に達しました。

これを実装する方法について、誰かが優れた技術リソースを共有してくれれば幸いです。

前もって感謝します。

score 12 · Accepted Answer

score 2 · Accepted Answer

GWT を使用したオートコンプリートの実装に関するこのブログを確認してください。

しかし、実装がどのように行われるかを理解するために、最初は非常に単純なものから始めることをお勧めします。Trie から始めて、おそらく完全にクライアントに保存してから、必要に応じてサーバークエリを使用して最適化します。

score 0 · Accepted Answer

オートコンプリートは通常、次のいずれかを使用して実装されます。

木。ツリー構造 (プレフィックスツリー、サフィックスツリー、dawg など) で検索可能なテキストをインデックス化することにより、メモリストレージを犠牲にして非常に高速な検索を実行できます。ツリートラバーサルは、近似マッチングに適合させることができます。
パターン分割。テキストをトークン (ngram) に分割することにより、単純なハッシュスキームを使用してパターンの出現を検索できます。
フィルタリング。一連の潜在的な一致を見つけ、順次アルゴリズムを適用して各候補をチェックします。

この件に関するいくつかの論文：

Java オートコンプリートライブラリである fullyを見てください。

autocomplete - オートコンプリート アルゴリズム、論文、戦略など