algorithm - トライに使用するノードデータ構造

Question

初めてトライを使用します。次に通過するブランチを決定する際に、トライに使用するのに最適なデータ構造を知りたいと思いました。配列、ハッシュマップ、リンクリストの中から探していました。

Answer 1

これらの各オプションには、それぞれ長所と短所があります。

子ノードを配列に格納すると、配列にインデックスを付けるだけで、どの子にアクセスするかを非常に効率的に検索できます。ただし、ノードあたりのスペース使用量は高くなります：O（|Σ|）。ここで、Σは、それらの子のほとんどがnullであっても、単語を形成できる文字のセットです。

リンクリストに子ノードを格納する場合、必要な子を見つけるためにリンクリストのすべてのノードをスキャンする必要がある場合があるため、子を見つけるのに必要な時間はO（|Σ|）になります。一方、使用している子供だけを保管するので、スペース効率はかなり良くなります。ここで固定サイズの配列を使用することも検討できます。これにより、スペースの使用量はさらに増えますが、挿入と削除に非常にコストがかかります。

子ノードをハッシュテーブルに格納する場合、子を見つけるための（予想される）時間はO（1）になり、メモリ使用量は（おおよそ）子の数にのみ比例します。興味深いことに、ハッシュする値が事前にわかっているため、事前計算をいくらか犠牲にして、動的な完全ハッシュテーブルを使用して最悪の場合のO（1）ルックアップを保証することを検討できます。

別のオプションは、子ノードを二分探索木に格納することです。これにより、三分探索木のデータ構造が生じます。この選択は、リンクリストとハッシュテーブルオプションの間のどこかにあります。スペースの使用量が少なく、先行クエリと後続クエリを効率的に実行できますが、BSTでの検索コストのため、ルックアップの実行コストがわずかに増加します。挿入が発生しない静的トライがある場合は、各ポイントでBSTとしてウェイトバランスの取れたツリーを使用することを検討できます。これにより、検索の実行時間が長くなります（O（n + log k）。ここで、nは検索する文字列の長さ、kはトライ内の単語の総数です）。

つまり、配列のルックアップは最速ですが、最悪の場合のスペース使用量は最悪です。静的サイズのアレイは、メモリ使用量が最も優れていますが、挿入と削除にコストがかかります。ハッシュテーブルは、（平均して）かなり高速なルックアップと良好なメモリ使用量を備えています。二分探索木は真ん中のどこかにあります。ここでハッシュテーブルを使用することをお勧めしますが、スペースを重視し、ルックアップ時間を気にしない場合は、リンクリストの方が適している可能性があります。また、アルファベットが小さい場合（たとえば、バイナリトライを作成している場合）、配列のオーバーヘッドはそれほど悪くないので、それを使用することをお勧めします。

お役に立てれば！

Answer 2

アルファベットのためだけにトライを構築しようとしている場合は、配列を使用してから、パーティシア ツリー (スペース最適化トライ) を使用することをお勧めします。 http://en.wikipedia.org/wiki/Radix_tree

これにより、配列を使った高速検索が可能になり、特定のノードの分岐係数が低い場合でもスペースを無駄にしません。