基数木

基数木（英: Radix tree）またはパトリシア木（英: Patricia tree）とは、文字列集合を格納するトライ木に基づく特殊化された集合データ構造である。パトリシアトライ（英: Patricia trie）とも。通常のトライ木に比較すると、基数木の辺は単一の文字ではなく文字の並びでラベル付けされる。それは、文字列でもよいし、整数やIPアドレスなどを表すビット列でもよい。辞書式順序を適用できるオブジェクトの並びなら何でもラベルとして使用できる。基数木と言った場合、整数を格納する木構造のみを指すことが多く、パトリシア木といった場合は特に格納するデータを限定しないが、基本的に構造や動作原理は同じである。

概要

基数木は簡単に言えばメモリ使用量を最適化したトライ木であり、トライ木で子ノードが1つしかないノードを子ノードとマージしたものである。その結果、内部ノードは必ず2つ以上の子ノードを持つことになる。通常のトライ木と異なり、辺には1つの文字だけでなく文字の並びがラベルとして付与される。これは、集合が小さい場合（特に長い文字列の集合）や長い接頭部を共有する文字列の集合などで効果を発揮する。

以下のような主な操作がサポートされており、いずれも O(k) である（k は集合内の最大文字列長）。

検索

ある文字列が集合に含まれているかどうかを調べる。この操作はトライ木とほぼ同じだが、辺によっては複数の文字に対応している点が異なる。

挿入

木構造に文字列を追加する。文字列が一致するところまで走査していき、そこから新たな辺を追加して残りの文字列をラベルとして付ける。なお、残りの文字列の先頭から一部分までが共通な別の辺がすでにある場合、共通部分を辺として新たに作り、そこから2つに分かれるようにする。

削除

文字列を木構造から削除する。まず、対応する葉ノード（と辺）を削除し、その親ノードの別の子ノードが1つしかない場合は、マージを行う。

辞書順の前の項目を探す

辞書式順序で1つ前の文字列を探す。

辞書順の後の項目を探す

辞書式順序で1つ後の文字列を探す。

基数木の典型的拡張として、ノードを「白」と「黒」に分ける方式がある。ある文字列が格納されているかを調べるとき、根ノードから文字列とラベルが一致する辺を辿っていく。文字列が全てラベルと一致したとき、その位置にあるノードが「黒」だった場合、検索は失敗となる。ノードが「白」だった場合、検索は成功となる。これを利用すると、接頭部が共通な多数の文字列で木構造を構築して、それらのノードは「白」にしておき、例外を「黒」を使って示すということができる。

応用

基数木は、キーが文字列で表される連想配列の構築に便利である。IPルーティングでは、IPアドレスの階層的構成が木構造に合っていることから、例外を除いた広い範囲のアドレスを表すのに基数木が適している。情報検索においては、テキスト文書の転置インデックス(接尾辞木)にも使われる。

歴史

1968年、Donald R. Morrison が "Patricia tries" と呼んだのが始まりである。PATRICIA は頭字語であり、"Practical Algorithm to Retrieve Information Coded in Alphanumeric"（英数字で符号化された情報を検索するための実用的アルゴリズム）の略である。Gernot Gwehenberger もほぼ同時期に独立に同じデータ構造を考案し発表している。

他のデータ構造との比較

以下の比較では、キーの長さを k、格納している要素数を n としている。

平衡2分探索木では、検索・挿入・削除には O(log n) の時間がかかるが、基数木では O(k) である。一般に k ≥ log n であるから、これは利点とは見なされないが、平衡2分探索木での比較は常に文字列の比較であり、最悪で O(k) の時間がかかる。特に長い接頭部が共通な文字列を多数格納していると遅くなる。一方、トライ木では比較は文字の比較で定数時間で済み、長さ m の文字列なら m 回の比較が必要となる。基数木は比較回数も少なく、走査するノード数も少ない。

ただし、基数木にはトライ木と同じ欠点がある。これらは、文字列や文字列に写像できるデータしか扱えない。それに対して平衡2分探索木は、順序関係のある任意のデータ型を扱える。これは例えば、大小比較だけが可能だが、シリアライズできないデータ型で問題となる。

ハッシュテーブルは一般に挿入・削除に O(1) の時間しかかからないとされているが、これはキーの操作を定数時間とみなしているためであって、キーの構造を考慮すると変わってくる。キーの長さが k なら、ハッシュテーブルでの挿入・削除には O(k) の時間がかかり、衝突が発生すると処理方式によってはさらに時間がかかる。基数木は最悪でも O(k) で挿入・削除できる。また、基数木では可能な辞書式順序の前後を取り出す操作もハッシュテーブルでは不可能である。

派生

HAT-trie は基数木の一種で、キャッシュを考慮した文字列検索用データ構造である。時間計算量も領域計算量もハッシュテーブルに匹敵する。

外部リンク

• Monash University: Algorithms and Data Structures Research & Reference Material: PATRICIA, by Lloyd Allison
• NIST's Dictionary of Algorithms and Data Structures: Patricia Tree
• A heavily commented dictionary implementation by Herbert Glarner。基数木を使用した辞書の実装（Linoleumというクロスプラットフォームのアセンブラを使用）。
• Jonathan Corbet's article on the Radix Tree API in the Linux Kernel
• Java implementation of Radix Tree, by Tahseen Ur Rehman
• Patricia Trie C++ template class implementation, by Radu Gruian
• Crit-bit trees, by D.J. Bernstein