単語のリストが与えられます - javaの単語補完のための良いアルゴリズムは何でしょうか？トレードオフ：速度/効率/メモリフットプリント

Question

潜在的な無料/有料アプリケーションのハードウェア/ソフトウェア要件（最終的な目標はモバイルJavaアプリケーション）を検討しています。

アプリケーションは次の簡単な目標から開始されます。データベース内の関連する単語のリストを指定すると、単一の文字列入力で単語補完を行うことができます。

つまり、私はすでにデータベースの内容を知っていますが、アルゴリズムのメモリフットプリント/速度/検索効率によって、サポートされるデータ量が決まります。

私はサフィックスベースのツリー検索で始めましたが、この単純なアプローチのスピード/メモリサイズのトレードオフと比べて、誰かが会議で話されているより複雑なものと経験があるのだろうかと思っています。

正直なところ、最初のアプリケーションの文脈は500ワード未満であるため、問題はないかもしれませんが、最終的にはアプリケーションが数万から数十万に拡張される可能性があります。

私は単純なものから始めて、後で切り替えることができると思いますが、以前のトレードオフを理解することを願っています！

Answer 1

単語の補完は、指定された接頭辞で始まるすべての単語を検索することを提案します。

Triesは、要素を追加または削除する場合に特に適しています。他のノードは再割り当てする必要はありません。

辞書がかなり静的で、検索が重要な場合は、はるかに単純なデータ構造を考えてみましょう。 binary-searchを実行すると、正しい接頭辞で始まる候補を検出し、その両端を線形検索して他のすべての候補を検出できます。