Loading AI tools
ウィキペディアから
基数木（英: Radix tree）またはパトリシア木（英: Patricia tree）とは、文字列集合を格納するトライ木に基づく特殊化された集合データ構造である。パトリシアトライ（英: Patricia trie）とも。通常のトライ木に比較すると、基数木の辺は単一の文字ではなく文字の並びでラベル付けされる。それは、文字列でもよいし、整数やIPアドレスなどを表すビット列でもよい。辞書式順序を適用できるオブジェクトの並びなら何でもラベルとして使用できる。基数木と言った場合、整数を格納する木構造のみを指すことが多く、パトリシア木といった場合は特に格納するデータを限定しないが、基本的に構造や動作原理は同じである。
基数木は簡単に言えばメモリ使用量を最適化したトライ木であり、トライ木で子ノードが1つしかないノードを子ノードとマージしたものである。その結果、内部ノードは必ず2つ以上の子ノードを持つことになる。通常のトライ木と異なり、辺には1つの文字だけでなく文字の並びがラベルとして付与される。これは、集合が小さい場合（特に長い文字列の集合）や長い接頭部を共有する文字列の集合などで効果を発揮する。
以下のような主な操作がサポートされており、いずれも O(k) である（k は集合内の最大文字列長）。
基数木の典型的拡張として、ノードを「白」と「黒」に分ける方式がある。ある文字列が格納されているかを調べるとき、根ノードから文字列とラベルが一致する辺を辿っていく。文字列が全てラベルと一致したとき、その位置にあるノードが「黒」だった場合、検索は失敗となる。ノードが「白」だった場合、検索は成功となる。これを利用すると、接頭部が共通な多数の文字列で木構造を構築して、それらのノードは「白」にしておき、例外を「黒」を使って示すということができる。
基数木は、キーが文字列で表される連想配列の構築に便利である。IPルーティングでは、IPアドレスの階層的構成が木構造に合っていることから、例外を除いた広い範囲のアドレスを表すのに基数木が適している。情報検索においては、テキスト文書の転置インデックス(接尾辞木)にも使われる。
1968年、Donald R. Morrison が "Patricia tries" と呼んだのが始まりである。PATRICIA は頭字語であり、"Practical Algorithm to Retrieve Information Coded in Alphanumeric"（英数字で符号化された情報を検索するための実用的アルゴリズム）の略である[1]。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 は基数木の一種で、キャッシュを考慮した文字列検索用データ構造である。時間計算量も領域計算量もハッシュテーブルに匹敵する[2]。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
