三分探索木

三分探索木とは

三分探索木（Ternary Search Tree）は、トライ木を改良したデータ構造で、各ノードを二分探索木のように扱うことで、より効率的な文字列検索を可能にします。トライ木では各ノードが文字に対応する子ノードを持つことで文字列の接頭辞を表現しますが、三分探索木では各ノードが以下の3つの子ノードを持ちます。

左ノード: 現在のノードの文字よりも小さい文字を持つノードを指します。
中央ノード: 現在のノードの文字の次の文字を持つノードを指します。
右ノード: 現在のノードの文字よりも大きい文字を持つノードを指します。

この構造により、単語のスペルチェックや辞書検索などの文字列を扱うアプリケーションにおいて、高速な検索を実現できます。

三分探索木の構造

三分探索木の各ノードは、格納された文字列の接頭辞を表します。中央ノードに繋がる部分は、そのノードまでの経路を共通の接頭辞として持つ文字列を表します。例えば、以下のような三分探索木を考えてみましょう。


c
/ | \
a u h
| | | \
t t e u
/ / | / |
s p e i s


この木には "as", "at", "cup", "cute", "he", "i", "us" という文字列が格納されています。これらの値を取得する手順は次のようになります。

1. 頂点ノードから、中央ノードを持たないノードまでの経路を記録します。
"c-a-t-s"
"c-a-t"
"c-u-t-p"
"c-u-t-e"
"c-h-e"
"c-h-u-i"
"c-h-u-s"
2. 記録された経路を、頂点から順に見ていき、もしそのノードの子が中央ノードでなければ、そのノードの文字を削除します。
"a-s" (cはaの左ノードなので削除)
"a-t" (cはaの左ノードなので削除。aはtの中央ノードなので残す。)
"c-u-p"
"c-u-t-e"
"h-e"
"i"
"u-s"
3. 上記の手順により、それぞれの文字列が取得できます。

終端文字について

部分文字列を含む文字列（例えば、"cute"と"cut"）を三分探索木に格納する場合、終端文字を表すノードを利用して表現します。例えば、先ほどの例に "cut" を追加すると、次のようになります。


c
/ | \
a u h
| | | \
t t e u
/ / | / |
s p e i s
/
#


ここで `#` が終端文字を表しており、"cut" が格納されていることを示します。

三分探索木の効率

三分探索木は、二分探索木と同様に、平衡化することが可能です。平衡化された三分探索木において、長さ m の文字列を検索するために必要な文字比較の回数は、要素数が n の場合、最大で m + log₂(n) 回となります。ここで重要なのは、比較が文字列単位ではなく文字単位で行われるという点です。

三分探索木の圧縮

トライ木における基数木と同様に、三分探索木も圧縮して無駄なノードを減らすことが可能です。例えば、先の例では、 "cu", "te", "he", "us" を一つのノードにまとめることで、木構造をよりコンパクトにできます。

まとめ

三分探索木は、トライ木を基にした効率的な文字列検索のためのデータ構造です。各ノードが3つの子ノードを持つことにより、検索効率を向上させ、平衡化や圧縮などの最適化も可能です。辞書検索やスペルチェックなど、文字列を扱う様々な場面で活用できます。

関連事項

二分探索木
ハッシュテーブル

参考資料

Ternary Search Trees (Jon Bentley and Bob Sedgewick)

外部リンク

Ternary Search Trees
Tree::Ternary (Perl module)
Ternary Search Tree code
STL-compliant Ternary Search Tree in C++
Ternary Search Tree in C++
Ternary Search Tree in Ruby
pytst - C++ Ternary Search Tree implementation with Python bindings
Algorithm for generating search strings given a Ternary Search Tree

もう一度検索