基数木

基数木（ラディックス木）とパトリシア木

基数木（Radix tree）またはパトリシア木（Patricia tree）は、トライ木をベースにした特殊なデータ構造で、文字列の集合を格納するために最適化されています。パトリシアトライとも呼ばれます。通常のトライ木とは異なり、基数木の辺は単一の文字ではなく、文字の並び（文字列、ビット列など）でラベル付けされます。これにより、特に長い文字列や共通の接頭辞を持つ文字列の集合を扱う際に、メモリ使用量と検索効率を大幅に向上させることができます。基数木は整数を格納するものを指す場合が多く、パトリシア木は格納するデータを限定しませんが、基本的な構造と動作原理は同じです。

概要

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

主な操作

基数木では、以下の主要な操作がサポートされており、いずれも O(k) の時間計算量で実行できます（kは集合内の最大文字列長）。

検索: ある文字列が集合に含まれているかを調べます。トライ木とほぼ同じですが、辺が複数の文字に対応している点が異なります。
挿入: 木構造に文字列を追加します。文字列が一致する箇所まで走査し、そこから新しい辺を追加して残りの文字列をラベルとして付けます。共通の接頭辞を持つ辺が既に存在する場合は、共通部分を新たな辺として作成し、そこから分岐するようにします。
削除: 木構造から文字列を削除します。対応する葉ノードを削除し、親ノードの子ノードが1つしかない場合は、マージ処理を行います。
辞書順の前の項目を探す: 辞書順で1つ前の文字列を探します。
辞書順の後の項目を探す: 辞書順で1つ後の文字列を探します。

基数木の拡張

基数木の典型的な拡張として、ノードを「白」と「黒」に分ける方式があります。文字列の検索時に、根ノードからラベルが一致する辺を辿っていき、最終ノードが「白」であれば検索成功、「黒」であれば検索失敗とします。これにより、接頭辞が共通な多数の文字列を「白」ノードで格納し、例外となる文字列を「黒」ノードで示すことができます。

応用

基数木は、キーが文字列で表される連想配列の構築に非常に便利です。また、IPルーティングでは、IPアドレスの階層構造が木構造に合っているため、広範囲のアドレスを効率的に表現できます。情報検索の分野では、テキスト文書の転置インデックス（接尾辞木）にも利用されています。

歴史

1968年、Donald R. Morrisonが「Patricia tries」として発表したのが始まりです。PATRICIAは、「Practical Algorithm to Retrieve Information Coded in Alphanumeric」の略です。Gernot Gwehenbergerもほぼ同時期に独立して同様のデータ構造を考案しています。

他のデータ構造との比較

平衡2分探索木: 検索、挿入、削除に O(log n) の時間がかかりますが、基数木では O(k) です。一般に k ≧ log n なので、有利とは言えませんが、平衡2分探索木での比較は文字列の比較であり、最悪で O(k) の時間がかかることを考慮すると、共通接頭辞を持つ文字列が多い場合は基数木が有利です。
トライ木: 文字単位での比較で定数時間ですが、基数木は比較回数も少なく、走査するノード数も少ないため効率的です。
ハッシュテーブル: 一般に挿入、削除が O(1) とされていますが、キーの構造を考慮すると O(k) となります。基数木も最悪で O(k) です。また、基数木では可能な辞書順の前後を取り出す操作は、ハッシュテーブルではできません。

派生

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

まとめ

基数木（パトリシア木）は、文字列集合を効率的に格納・検索するための強力なデータ構造です。その特性から、様々な分野で幅広く応用されています。

もう一度検索