トライ (データ構造)
トライ木（英: trie）やプレフィックス木（英: prefix tree）とは、順序付き木の一種。あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックス（接頭部）があり、ルート（根）には空の文字列が対応している。値は一般に全ノードに対応して存在するわけではなく、末端ノードや一部の中間ノードだけがキーに対応した値を格納している。2分探索木と異なり、各ノードに個々のキーが格納されるのではなく、木構造上のノードの位置とキーが対応している。
キーが文字列である連想配列の実装構造としても使われる。右図の例では、ノードを表す丸の中にキーが書かれ、連想される値がその下に書かれている。値が書かれていないノードはキー文字列の途中までにしか対応していない。各英単語には整数の値が対応している。
トライ木は一種の決定性有限オートマトンと見ることもできるが、エッジ（枝）に対応する記号（文字）はその順序が暗黙のうちに決定される（辞書順など）。
キーは必ずしもノードに格納される必要はない。右図はトライ木の概念を示したもので実装は一般に異なる。
トライ木のキーは必ずしも文字列である必要はない。トライ木のアルゴリズムを文字列以外の任意のデータ構造に適用することは容易である。
trie という名称は "retrieval"（探索、検索）が語源であるため、"tree" と同じ発音を用いる（リトゥリーヴァル）。しかし、ツリー構造との混同を避けるために「トライ」という読み方を奨励する人もいる。日本語では、「トライ木」という呼び方がほぼ定着している。
利点と欠点（2分探索木との比較）
[編集]2分探索木と比較したトライ木の主な利点:
- キー検索が高速である。長さ m のキー検索の時間計算量は最悪でも O(m) である。2分探索木での時間計算量は O(log n) である。ただしn は木を構成するノード数である（木の深さに応じた時間がかかり、2分探索木の深さは n の対数となる）。トライ木が検索処理で行う文字でインデックス付けした配列の操作なども、実際のマシンでは高速である。
- 多数の短い文字列を格納する場合にはトライ木の方がメモリを節約できる。これはキーが明示的に格納されないためであり、複数のキーがノードを共有するためである。
- トライ木は最も長いプレフィックスとマッチするよう探索を進められるので、最も長いプレフィックスが共通なキーを効率的に捜せる。また、そのような共通プレフィックスに対応したノードに新たな値を格納できる。
- トライ木は木構造として平衡を保つ必要はない。2分探索木は深さが平衡していないと性能に悪影響がある（平衡2分探索木参照）。
トライ木の欠点:
- トライ木はキーの順序を与えるが、辞書順でなければならない。
- トライ木は入力ノード数に対して深さが極めて大きくなりうる。例えば、少数の非常に長い文字列を格納するトライ木などである（この場合、パトリシア木が適する）。
- トライ木のアルゴリズムは単純な2分探索木よりも複雑である。
- データを文字列として表すのは常に簡単とは言えない。例えば、複雑なデータ構造や浮動小数点数などをキーとする場合、工夫が必要となる。
トライ木は基本的にキーとして文字列を必要とするが、様々なデータ型を文字列に変換することもできる。例えば、整数を単にビットの列と見れば、文字列と何ら変わらない。ルーティングテーブルやページテーブルではその性質から、プレフィックスが共通の整数がキーとしてよく使われる（つまり偏りがある）。
トライ木はキーの長さが可変でキー検索が失敗する場合があるとき（そのキー文字列がキーとされていない場合）、最も便利である。固定長のキーで常に検索が成功するならパトリシア木の方が適している。これは子ノードが1つしかないノードをその子ノードとまとめてしまう方法である（図の例で言えば、"i" のノードと "in" のノードをまとめる）。例えば、経路がほとんど分岐しない構造になっている場合、これはメモリ使用量を削減することになる。
性能の定量化
[編集]トライ木の探索時間は、キー文字列の長さが一定であれば O(1) とみなせるが、厳密には異なる。キーが N 個あるとき、文字の種類が k なら、最も長いキーは logkN 文字がその長さの下限となる。このことから、トライ木の探索時間は厳密には Ω(logN) であり、これは2分探索と同じである。
この結果は必ずしもトライ木の利点を否定するものではない。トライ木の高速性の利点は各ノードでの比較が高速である点にある。2分探索での一回の比較は比較対象の短いほうを m 文字としたとき O(m) が最悪時間となる。一方トライ木では各ノードでの比較は1文字の比較であるため、その時間は一定である。これは単に理論上の違いというわけではない。というのも2分探索木で末端に近いノードまで行くと常にプレフィックスが共通なノードで文字列比較を行うため、比較時間が長くなってしまうからである。
応用
[編集]他のデータ構造の代替
[編集]既に述べたようにトライ木は2分探索木に比較して様々な利点がある。トライ木はハッシュテーブルの代替としても使用でき、次のような利点がある:
- 理論上、平均検索性能は同じだが、実測するとトライ木の方が速い。
- ハッシュテーブルの検索の最悪時間は O(N) である。
- キーの衝突（コリジョン）が発生しない。
- ハッシュ関数を用意する必要がない。
- トライ木ではキーの辞書順を自動的に生成できる。
トライ木をハッシュテーブルの代替として使用した際の欠点は次の通り:
- 格納されている全キーを文字列として取り出すのが簡単ではない。
- ハッシュテーブルよりもメモリ効率が悪い。
- ハッシュテーブルはプログラミング言語に最初から用意されているが、トライ木はそうではない。
辞書表現
[編集]トライ木の典型的な応用として辞書の格納がある。例えば、携帯電話などで使われている。トライ木の利点として検索の高速性と新たなエントリの挿入やエントリの削除の容易性が活用されている。しかし、単に辞書の単語を格納するだけなら（つまり、各単語の意味などが必要とされない場合）、非輪状決定性有限オートマトンのほうがメモリ効率がよい。
トライ木はスペルチェッカなどの近似的マッチングアルゴリズムの実装にも適している。
擬似コード
[編集]以下の擬似コードは与えられた文字列がトライ木にあるかどうかを判定する汎用のアルゴリズムを示したものである。ここで、children は子ノード群の配列であり、terminal ノードとは格納された単語に対応するノードを意味する。
function find(node, key) {
if (key is an empty string) { # 基本ケース。キーが空文字列の場合
return is node terminal?
} else { # 再帰ケース
c = first character in key # キーが空でないので、その1文字目を取り出す
tail = key minus the first character # 1文字目を除いた文字列
child = node.children[c] # 文字コードが配列キーとなる
if (child is null) { # 子がないので再帰できないがキーは空になっていない
return false
} else {
return find(child, tail)
}
}
}
ソート
[編集]辞書順にキー文字列をソートする処理は次のようにトライ木で実現される:
- 全キーをトライ木に挿入する。
- 深さ優先探索のような決まった順序でトライ木から全キーを取り出す。
これは一種の基数ソートである。
トライ木を使って N 個のキーのソートを N 個のプロセッサで行うと（並列アルゴリズム）、その時間は Ω(1) となる。ただし、キーの長さはある一定の上限があるものとする。キーが共通のプレフィックスを持っていたり、同じキーが複数個あったりするので、並列処理の性能上の利点が小さくなるという問題はある。
全文検索
[編集]特殊なトライ木としてサフィックス木がある。これを使って高速全文検索のためにテキストのサフィックス（接尾部）でインデックス付けを行うことができる。
実装の工夫
[編集]
トライ木を表現する方法は何通りもある。メモリの使用量と操作の速さの間のトレードオフがある。
基本的な方法は、ノードに（文字, 子ポインタのリスト）を格納する方法である。これは単純であるが、木の葉の方に近づくと子供の少ないノードがたくさん出来るためメモリの無駄遣いである。
二重連鎖木
[編集]別の方法は、ノードに（文字, 子ノードへのポインタ, 兄弟ノードへのポインタ）の3つ組みを格納する方法である。つまり二重連鎖木である。子ノードへのポインタは1つ目の子供だけをさし、2つ目の子供は、その子供から兄弟ノードへのポインタを使い参照する。
三分探索木
[編集]更に別の方法は、子供の集合を2分探索木で表現する方法である。この場合、トライ木は三分探索木になる。
ダブル配列
[編集]1989年に青江順一がダブル配列を利用する方法を発表した[1]。トライ木は決定性有限オートマトンとして解釈する事が出来るが、決定性有限オートマトンはデフォルト（default）・ベース（base）・次（next）・チェック（check）の4つの配列で表現できる[2][3]。トライ木の場合はデフォルトは不要である。その上で、s から t へ c により遷移する場合は、以下の関係が成立すれば良い。
check[base[s] + c] = s next[base[s] + c] = t
動的に要素が増えていく場合 next と check は同じように増えていくのでまとめる事が出来るが、base は同じ速度では増えていかず分裂してしまう。そこで、ダブル配列では、base と next を統合し、以下の関係が成立するように管理する。
check[base[s] + c] = s base[s] + c = t
すると、base と check だけが残り、この2つは同じ速さで増えていき、一つの構造体にまとめる事が出来る。
ある要素がトライ木に含まれているかどうか調べる際に、二重連鎖木を使った方法では、兄弟ノードはポインタ（連結リスト）をたどって行かないといけないが、ダブル配列では一発で遷移できる。
実装としては Theppitak Karoonboonyanan が libdatrie を公開している[4]。
整数を格納するトライ木
[編集]二分トライ木
[編集]二分トライ木（英: binary trie）やビット単位トライ木（英: bitwise trie）とは、整数を格納するトライ木で、上位ビットから 0 また 1 で左右に分岐する[5]。
高速化のためのテクニックとして、下記の２つの方法が使える。
- 葉ノードは子が無く、子を指すポインタが空くので、葉ノード同士を双方向連結リストでつないでしまう。前後のノードを O(1) でたどれるようになる。
- jumpポインタをノードに付け、一気に葉ノードまでジャンプする。
x-高速トライ木
[編集]
x-高速トライ木（英: x-fast trie）は、検索キーとして与えられた整数以上(以下)の値をもつ、キーに最も近い葉ノードを得る操作(successor, predecessor)を高速にできるようにした二分トライ木のバリエーションである。通常の二分トライ木との相違点は、階層高さごとのハッシュテーブル、葉ノード同士の双方向連結リスト、中間ノードが子ノードを0側(1側)のひとつしか持たない時に格納される、その中間ノード下で最大(最小)値をもつ葉ノードへのリンク(descendant pointer)を持つことである。[6]。階層にたいして二分探索をおこなうことで、木に格納する整数のビット数 w に対し、Successor, Predecessorの時間計算量がO(log w)となる。1982年に Dan E. Willard が発表した[7]。
y-高速トライ木
[編集]y-高速トライ木（英: y-fast trie）とは、格納する整数が w ビットの時、x-fast trie に全体の 1/w だけしか格納せず、残りを Treap などの平衡2分探索木に O(w) 個ずつに分けて入れる[8]。これにより全体の空間計算量が、実際に木に格納されたデータの数 n に対し O(n) となり、x-高速トライ木より改善する。また、追加・削除の時間計算量が O(log w) になる。1982年に Dan E. Willard が x-fast trie と同時に発表した[7]。
関連項目
[編集]参考文献
[編集]- ^ Jun-ichi Aoe (1989). “An Efficient Digital Search Algorithm by Using a Double-Array Structure”. IEEE Transactions on Software Engineering 15 (9): 1066-1077.
- ^ Stephen C. Johnson (1975). “YACC-Yet another compiler-compiler”. Computing Science Technical Report 32: 1-34.
- ^ A.V. エイホ; R. セシィ; J.D. ウルマン; M.S. ラム (2009). コンパイラ―原理・技法・ツール (Information & Computing). ISBN 978-4781912295
- ^ An Implementation of Double-Array Trie
- ^ 13.1 BinaryTrie: A digital search tree
- ^ Bose, Prosenjit; Douïeb, Karim; Dujmović, Vida; Howat, John; Morin, Pat (2010), Fast Local Searches and Updates in Bounded Universes, Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010), pp. 261–264
- ^ a b Willard, Dan E. (1983). “Log-logarithmic worst-case range queries are possible in space Θ(N)”. Information Processing Letters (Elsevier) 17 (2): 81–84. doi:10.1016/0020-0190(83)90075-3. ISSN 0020-0190.
- ^ 13.3 YFastTrie: A Doubly-Logarithmic Time SSet
- R. de la Briandais: File Searching Using Variable Length Keys. Proceedings of the Western Joint Computer Conference, 1959, pages 295–298.
- E. Fredkin: Trie Memory. Communications of the ACM, 3(9):490-499, Sept. 1960.
- Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 6.3: Digital Searching, pp.492–512.
外部リンク
[編集]- NIST's Dictionary of Algorithms and Data Structures: Trie
- Tries by Lloyd Allison
- PHPによるトライ木の実装
