ハッシュテーブルとトライ（プレフィックスツリー）
1. 序章
このチュートリアルでは、ハッシュテーブルとトライの2つのデータ構造を見ていきます。 ハッシュテーブルまたはトライデータ構造で解決できる問題を定義します。 次に、2つのソリューションを比較し、それらの類似点と相違点を指摘します。
2. 問題の説明
ハッシュテーブルまたはトライで解決できる問題から始めましょう。 文字列のリストと文字列を含む辞書が与えられた場合、辞書にあるかどうかを確認したいと思います。
3. ハッシュテーブルソリューション
使用できますハッシュ表辞書を作成します。
3.1. ハッシュテーブルの構築
文字列をハッシュテーブルに入れるとき、文字列のハッシュ値を計算するためにハッシュ関数が必要です。 ハッシュ関数は、可変長の入力文字列を受け取り、固定長の出力値を生成できます。
通常、ハッシュ関数の出力は、ハッシュテーブル内の文字列を格納する場所を指す整数インデックスです。 たとえば、次の多項式ローリングハッシュ関数を使用して、文字列を整数に変換できます。
ここで、とはいくつかの正の数です。
ハッシュ関数は入力文字列のすべての文字を考慮する必要があるため、ハッシュ関数の時間計算量はです。ここで、は入力文字列の長さです。 したがって、辞書を作成する時間は、すべての文字列の合計文字数に比例します。
3.2. ハッシュテーブルルックアップ
文字列がハッシュテーブルにあるかどうかを確認するとき、同じハッシュ関数を使用してのハッシュ値を計算できます。 次に、ハッシュテーブルを検索して、計算されたハッシュ値が含まれているかどうかを確認します。
ハッシュ値の計算には時間がかかります。ここで、は入力文字列の長さです。 通常、優れたハッシュ関数がある場合、ルックアッププロセスには一定の時間がかかります。 したがって、全体的なルックアップ時間の複雑さはです。
4. トライソリューション
trieデータ構造を使用して辞書を作成することもできます。
トライでは、2つのノード間のリンクは、キー付き文字列の文字を表します。 たとえば、次のトライは文字列の辞書を表します。
ノードが辞書内の文字列全体を表す場合、それを完全なノードとしてマークします。
4.1. トライ建設
文字列をtrieに挿入すると、ノードから開始して、最初の文字に対応するリンクを検索します。 リンクがすでに存在する場合は、次の子レベルへのリンクに従ってツリーを下に移動し、次の文字の検索を続行します。 リンクが存在しない場合は、新しいノードを作成し、現在のキー文字に一致する親のリンクにリンクします。
すべての文字が完成するまで、入力文字列の各文字に対してこの構築手順を繰り返します。 次に、最後のノードを完全なノードとしてマークします。
たとえば、上記の例のトライに新しい単語「」を追加するには、最初にノードから「」パスをたどります。 次に、キャラクターとの追加のノードとリンクを作成します。 最後に、最後のノードを完全なノードとしてマークします。
トライ構造では、キーを計算するためのハッシュ関数は必要ありません。 ただし、入力文字列の各文字を確認する必要があります。 したがって、文字列をトライに追加するための時間計算量は、入力文字列の長さでもあります。
4.2. トライルックアップ
文字列がtrieにあるかどうかを確認するのと同様の方法を使用できます。 から始めて、入力文字列の内容に基づいて文字リンクをたどることができます。 すべての文字に一致するパスを見つけることができ、最後のノードが完全なノードである場合、入力文字列はトライに存在します。 それ以外の場合、トライには入力文字列が含まれません。
入力文字列の各文字を1回だけトラバースするため、全体的なルックアップ時間の複雑さもです。
5. 比較
2つのアプローチは同じではありません。 2つを比較できるいくつかの側面を見てみましょう。
5.1. ルックアップ速度
ハッシュテーブルの文字列を検索するときは、最初に文字列のハッシュ値を計算しますが、これには時間がかかります。 次に、優れたハッシュ関数があると仮定すると、メモリ内のハッシュ値を見つけるのに時間がかかります。 したがって、全体的なルックアップ時間の複雑さはです。
トライの文字列を検索するときは、文字列の各文字を調べて、トライ内の対応するノードを見つけます。 全体的なルックアップ時間の複雑さもです。
ただし、トライには、文字列全体を取得するためのオーバーヘッドがあります。 文字パスに沿ってトライノードを見つけるには、メモリに複数回アクセスする必要があります。 ハッシュテーブルの場合、入力文字列のハッシュ値を1回だけ計算する必要があります。 したがって、ハッシュテーブルで文字列全体を検索すると、比較的高速になります。
ハッシュテーブルの場合、文字列がハッシュテーブルに存在するかどうかに関係なく、入力文字列全体のハッシュ値を常に計算します。 トライの場合、一致する文字リンクが見つからない場合は、検索を早期に停止できます。 したがって、入力文字列がトライに存在しない場合、トライのルックアップ速度は速くなる可能性があります。
5.2. メモリ要件
最初にハッシュテーブルを作成するときは、通常、メモリのサイズを均一にハッシュすることで衝突を回避するために、メモリの大きなチャンクを事前に割り当てます。 将来、ハッシュテーブルに文字列を挿入するときは、文字列の内容を保存するだけで済みます。
トライデータ構造の場合、文字リンクポインタや完全なノードフラグなどの追加データを格納する必要があります。 したがって、トライは文字列データを格納するためにより多くのメモリを必要とします。 ただし、共通のプレフィックスが多数ある場合は、プレフィックスノードを共有できるため、メモリ要件は小さくなります。
全体として、ハッシュテーブルとトライの間のメモリ要件は、事前に割り当てられたハッシュテーブルメモリと入力辞書文字列のサイズに基づいています。
5.3. アプリケーション
ハッシュテーブルのルックアップ速度は比較的高速ですが、文字列全体の完全一致のみをサポートします。 トライソリューションは、オートコンプリートなど、より多くのアプリケーションをサポートするためにより柔軟です。 また、辞書にあるすべての単語をアルファベット順にトライで簡単に印刷できます。
したがって、フルテキストルックアップアプリケーションが必要な場合は、ルックアップ速度が速いため、ハッシュテーブルの方が適しています。 ただし、プレフィックスに一致するすべての単語を返したい場合は、トライが解決策です。
6. 結論
この記事では、ハッシュテーブルとトライの2つのデータ構造について説明しました。 これら2つのデータ構造の時間計算量とメモリ要件を比較しました。 また、使用に適したアプリケーションについても説明しました。
