辞書データベースから単語を検索するための最も効率的な方法は何ですか。私は答えを探しました、そして人々はトライデータ構造を使うことを提案しました。しかし、大量の単語のツリーを作成するための戦略は、プライマリメモリをロードすることです。データ構造プロジェクトにこの実装を含むAndroidアプリを作成しようとしています。だから誰かが辞書がどのように機能するか教えてもらえますか？
携帯電話でt9辞書を使用している場合でも、単語の候補が画面にすばやく表示されます。アルゴリズムとその背後にある設計を知りたい。
大きな辞書を検索するのに最も便利なTrieを使用できます。あまりにも多くの単語が同様の起動を使用しているため、物理メモリへのアクセス数が制限されている場所で使用できる定数因子検索の周りで brgins を試してください。Webで多くの実装を見つけることができます。
誰かがトライに慣れていない場合は、このサイトが良いと思います。サンプルをここに引用しています。
トライ (検索による) は、アルファベットの文字列を格納するのに役立つ多方向ツリー構造です。これは、スペル チェック プログラムや自然言語の「理解」プログラムで英語 (たとえば) の単語の大規模な辞書を格納するために使用されています。与えられたデータ:
an, ant, all, allot, alloy, aloe, are, ate, be対応するトライは次のようになります。
これは Java での実用的な Trie の実装です: http://code.google.com/p/google-collections/issues/detail?id=5
それを行う方法はたくさんあります。少し前に使用したもの (辞書を変更しない場合は特に便利です) は、プレフィックス インデックスを作成するものです。
つまり、エントリを語彙的にソートします。次に、さまざまな最初の文字の範囲の (終了) 位置を保存します。つまり、エントリに 1 から 1000 のインデックスがあり、単語 "aardvark -- azerbaijan" が 1 から 200 の範囲を取る場合、別のテーブル "a | 200" にエントリを作成し、最初に同じことを行います。そして二文字目。次に、特定の単語を検索する必要がある場合は、検索範囲を大幅に縮小します。私の場合、最初の 2 文字のインデックスで十分でした。
繰り返しますが、この方法では、Android に存在すると思われる SQLite などの DB を使用する必要があります。
トライを使用することは確かにスペースを意識しています。150,000 ワードをトライにロードした後に RAM 使用量を確認したところ、使用量は 150 MB でした (Trie は C++ で実装されていました)。メモリ消費はポインタによるものでした。私は 30 MB 前後で (150 MB と比較して) メモリの浪費が非常に少ない 3 項試行で終了しましたが、時間の複雑さは少し増加しました。もう 1 つのオプションは、"Left child Right sibling" を使用することです。この場合、メモリの浪費は非常に少なくなりますが、時間の複雑さは 3 項トライよりも大きくなります。
