95,000 語の辞書に含まれているかどうかに関係なく、単語を探しているとしましょう。単語の長さを使用して検索を容易にすることはできません。私の質問は、O(n) ルックアップを行わずに単語を見つける最速の方法に関するものです。
ここに私の2つの考えがあります：
まず、ハッシュテーブルに単語を保存し、単語のルックアップは O(1) です。これは私の考えでは最良のシナリオのようですが、Trie を使用して別の Web サイトを調べることも提案されました。これに関する私の質問は、非常に多くの単語を保持するトライがあります。 この場合、ルックアップは O(k) になります。
では、大きな辞書から単語を見つける最適な方法は何でしょうか?
最適性はユースケースによって異なります。ルックアップ時間またはスペースを気にしますか? (また、新しい単語を挿入することを気にしますか?)。
時間的にできる最善の方法は、ハッシュ テーブルを使用することですが、ディクショナリの場合はスペース効率が悪くなります。トライは、単語全体ではなく接頭辞を格納するため、スペース要件を圧縮しますが、検索に時間がかかります。したがって、あなたの質問に答えるには、ハッシュテーブルよりも多数の単語を使用して試行する方がスペース効率が高くなります。
単一の単語を検索するだけの場合、ハッシュ テーブルまたはツリー構造を設定するコストは線形検索を超えます。これらの構造は、（非常に）多くの用途でコストが償却されると（非常に）効率的になります。
ディクショナリがソートされている場合 (なぜディクショナリがソートされないのでしょうか?)、log(n)ファイル内のバイナリ検索で 1 つの単語を検索できます。追加の構造は必要ありません。
辞書で単語を見つける最良の方法は B+ ツリーだと思います。その理由を説明しましょう。
10 個の文字列のルート ブロックがあるとします。ブロック内の文字列は並べ替えられます。これらの 10 個の文字列の後に、10 個の文字列の別のセルへのポインターが続き、それが 1 つになります。最初のキーワードから始まり、比較して小さい単語が見つかるまで (StringCompare)。
各文字列の隣に、比較して小さい単語を含むセルを示すポインターがあることを標準として考えると、データの最終ブラケットに到達するまでに 5 つの手順と 5 つの比較が必要になります。あなたのキーワードが含まれていません。
5 つの比較 + 最後の括弧内の比較では、10*10*10*10*10 語の辞書を検索しています。
アルゴリズムは、セル内の文字列の数を基数とする対数速度 Log 100000 です。各セルに 10 個の単語がある場合、5 つのステップが必要です。
ツリーのルートのみを Ram メモリに格納する必要があることに注意してください。その他のすべてのブロックは、いくつかの手順でパフォーマンスを大幅に低下させることなく、ハード ドライブに格納できます。
私が正しく説明したことを願っています:D 少なくとも私は試しました! 楽しんで
このデータ構造はハッシュテーブルよりも高速になる可能性があるため、Trie が推奨されます。ハッシュ テーブルはO(1)理想的な場合にのみ使用され、実際のアプリケーションでは衝突が発生する可能性があります。さまざまなタイプのトライ データ構造では、この問題は発生しません。
もう 1 つのケースは圧縮です。Trie は、ハッシュ テーブルよりもはるかにコンパクトです。ハッシュ テーブルには、効率的な挿入操作のためにある程度のスペースが必要です。ハッシュ テーブルの負荷率が 100% に近い場合、挿入操作に非常に長い時間がかかります。
ハッシュ テーブルでは、キーをディクショナリの少なくとも 1 つのキーと比較する必要があります。この場合のキー比較ではO(k)、キーの長さが k になります。trie を使用すると、同じことを行うことができます。ルックアップ操作はO(k).
試行では、順序付けされたトラバーサル、ハッシュ テーブルが許可されますが、許可されません。
そこには多くの種類の試行があります。たとえば、この特定のケースでは三分探索トライが非常に優れています。配列にマップされたトライも、通常のハッシュ テーブルと比較して非常に高速です。