ハッシュテーブルとトライ（プレフィックスツリー）を選択するにはどうすればよいですか？

StackOverflow https://stackoverflow.com/questions/245878

質問

ですから、ハッシュテーブルとプレフィックスツリーのどちらかを選択する必要がある場合、どちらを選択するかを決定する要因は何ですか。私自身の素朴な観点からは、トライを使用すると、配列として格納されないため、余分なオーバーヘッドがありますが、実行時間の観点から（最長のキーは最長の英語の単語であると仮定）、本質的にO （1）（上限に関連して）。たぶん最長の英語の単語は50文字ですか？

ハッシュテーブルは、インデックスを取得するとすぐに検索されます。ただし、インデックスを取得するためにキーをハッシュすることは、50ステップ近くを簡単に実行できるようです。

誰かがこれについてより経験豊富な視点を提供してくれますか？ありがとう！

役に立ちましたか？

解決

試行の利点：

基本：

  • 予測可能なO（k）ルックアップ時間。kはキーのサイズです
  • ルックアップがなければk未満の時間がかかります
  • 順序トラバーサルをサポート
  • ハッシュ関数は不要
  • 削除は簡単です

新しい操作：

  • キーのプレフィックスをすばやく検索したり、特定のプレフィックスを持つすべてのエントリを列挙したりできます。

リンクされた構造の利点：

  • 共通のプレフィックスが多数ある場合、それらに必要なスペースは共有されます。
  • 不変の試行は構造を共有できます。適切なトライを更新する代わりに、1つのブランチに沿ってのみ異なる新しいトライを作成できます。これは、同時実行、テーブルの複数の同時バージョンなどに役立ちます。
  • 不変のトライは圧縮可能です。つまり、ハッシュコンシングによって、サフィックスの構造も共有できます。

ハッシュテーブルの利点：

  • 誰もがハッシュテーブルを知っていますよね？ご使用のシステムには、ほとんどの目的で試行するよりも速く、適切に最適化された優れた実装が既に用意されています。
  • キーには特別な構造は必要ありません。
  • リンクされた明白なトライ構造よりもスペース効率が高い（以下のコメントを参照）

他のヒント

すべては、解決しようとしている問題に依存します。挿入と検索だけが必要な場合は、ハッシュテーブルを使用します。プレフィックス関連のクエリなど、より複雑な問題を解決する必要がある場合は、トライがより良い解決策である可能性があります。

誰もがハッシュテーブルとその使用法を知っていますが、正確に一定のルックアップ時間ではなく、ハッシュテーブルの大きさ、ハッシュ関数の計算の複雑さに依存します。

効率的なルックアップのために巨大なハッシュテーブルを作成することは、小さなレイテンシ/スケーラビリティが問題になるほとんどの産業シナリオ（高頻度の取引など）でのエレガントなソリューションではありません。キャッシュミスを減らすために、メモリ内で占有するスペースに対して最適化されるデータ構造に注意する必要があります。

トライアルが要件により適している非常に良い例は、メッセージングミドルウェアです。さまざまなカテゴリのメッセージのサブスクライバーおよびパブリッシャー（JMSの用語-トピックまたは交換）が100万人いるので、トピック（実際は文字列）に基づいてメッセージをフィルターで除外する場合、ハッシュテーブルを作成することは絶対に望まない100万のトピックを持つ100万のサブスクリプションのために。より良いアプローチは、トピックをトライで保存することです。そのため、トピックの一致に基づいてフィルタリングが行われる場合、その複雑さはトピック/サブスクリプション/パブリッシャーの数に依存しません（文字列の長さのみに依存します）。スペースの要件を最適化するためにこのデータ構造を使用して創造性を高め、キャッシュミスを減らすことができるため、気に入っています。

ツリーを使用：

  1. オートコンプリート機能が必要な場合
  2. 「a」または「axe」などで始まるすべての単語を検索します。
  3. 接尾辞ツリーは、ツリーの特別な形式です。サフィックスツリーには、ハッシュではカバーできない利点の全リストがあります。

HashTable の実装は、基本的な Trie の実装と比較してスペース効率が高くなっています。しかし、文字列では、ほとんどの実際のアプリケーションで順序付けが必要です。しかし、HashTableは辞書的な順序を完全に乱します。アプリケーションが辞書順（部分検索、特定のプレフィックスを持つすべての文字列、ソートされた順序のすべての単語など）に基づいて操作を実行している場合、トライを使用する必要があります。ルックアップのみの場合、HashTableを使用する必要があります（ほぼ間違いなく、最短のルックアップ時間を提供します）。

PS：これら以外に、 3項検索ツリー（TST）が最適な選択です。ルックアップ時間はHashTableよりも長くなりますが、他のすべての操作では時間効率が高くなります。また、試行よりもスペース効率が高くなります。

誰も明示的に言及していないが、心に留めておくことが重要だと思うものがあります。ハッシュテーブルとさまざまな種類の試行の両方に、通常 O（k）操作があります。ここで、 k は文字列の長さ（ビット単位、または同等の文字単位）です。

これは、適切なハッシュ関数があることを前提としています。 「農場」が必要ない場合および「農場の動物」同じ値にハッシュするには、ハッシュ関数はキーのすべてのビットを使用する必要があるため、「農場の動物」をハッシュします。 「農場」の約2倍の時間がかかります。 （ただし、何らかのローリングハッシュシナリオを使用している場合を除きますが、同様の操作を節約するシナリオも試行されます）。そして、バニラを試してみると、「農場の動物」を挿入する理由は明らかです。 「農場」の約2倍の時間がかかります。長期的には、圧縮された試行でも同様です。

トライの挿入と検索は、入力文字列O（s）の長さに対して線形です。

ハッシュは、ルックアップと挿入のためにO（1）を提供しますが、最初に、再びO（s）である入力文字列に基づいてハッシュを計算する必要があります。

結論、漸近的な時間の複雑さはどちらの場合も線形です。

データの観点からトライにはさらにオーバーヘッドがありますが、圧縮されたトライを選択すると、ハッシュテーブルとほぼ同程度になります。

ネクタイを破るには、次の質問を自問してください：完全な単語のみを検索する必要がありますか？または、プレフィックスに一致するすべての単語を返す必要がありますか？ （予測テキスト入力システムのように）。最初のケースでは、ハッシュを探します。よりシンプルでクリーンなコードです。テストと保守が簡単。接頭辞または接尾辞が重要である、より詳細な使用例については、試してみてください。

そしてもしあなたがただ楽しみのためにそれをするなら、トライを実装することは日曜日の午後を有効に使うでしょう。

一部の（通常は組み込みのリアルタイム）アプリケーションでは、処理時間がデータに依存しないことが必要です。その場合、ハッシュテーブルは既知の実行時間を保証できますが、トライはデータに基づいて異なります。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top