接尾辞木

接尾辞木とは

接尾辞木（サフィックス木とも呼ばれる）は、与えられた文字列のすべての接尾辞（文字列の末尾から始まる部分文字列）を、木構造で表現したデータ構造です。この木構造は、文字列操作を高速化するための強力なツールとして、様々な分野で利用されています。

基本的な構造

接尾辞木は、根から葉までの経路が、元の文字列のいずれかの接尾辞に対応するように構成されます。各枝には文字列が割り当てられており、根から葉に向かって枝をたどることで、接尾辞を読み取ることができます。この構造により、特定の接尾辞や部分文字列を高速に検索することが可能になります。

歴史

接尾辞木の概念は、1973年にPeter Weinerによって「position tree」として初めて紹介されました。その後、1976年にEdward McCreightによって構築法が大幅に単純化され、1995年にはEsko Ukkonenによってさらに洗練されたアルゴリズムが開発されました。特にUkkonenのアルゴリズムは、文字列全体を事前に知らなくても、逐次的に接尾辞木を構築できるオンラインアルゴリズムとして画期的でした。

接尾辞の例

例えば、文字列 "BANANA" の接尾辞は、以下のようになります。

BANANA
ANANA
NANA
ANA
NA
A

このように、長さ n の文字列には、n 個の接尾辞が存在します。

接尾辞木の定義

長さ n の文字列 S に対する接尾辞木は、以下の特徴を持つ木構造として定義されます。

1. 根から葉までの各経路が、S の接尾辞に一対一対応する。
2. 各枝には、空でない文字列が対応する。
3. 根と葉以外のノードは、少なくとも2つの子ノードを持つ。

接尾辞木を構築する際、文字列の末尾に終端記号（通常は「$」）を追加することがあります。これにより、ある接尾辞が別の接尾辞の接頭辞となることを防ぎ、すべての接尾辞が葉ノードに対応するようにします。

接尾辞リンク

接尾辞木の効率的な構築には、「接尾辞リンク」と呼ばれる特別なポインタが重要な役割を果たします。接尾辞リンクは、ある内部ノードから、そのノードに対応する文字列の最初の文字を除いた文字列に対応する別の内部ノードへのポインタです。このリンクにより、接尾辞木の構築やアルゴリズムの実行が効率化されます。

接尾辞木の機能

接尾辞木は、以下のような様々な文字列処理機能を高速に実現できます。

文字列検索

長さ m の文字列が部分文字列かどうかを O(m) 時間で判定
複数のパターンが最初に出現する位置を O(m) 時間で検出
部分文字列群が z 回出現する全位置を O(m + z) 時間で検出
正規表現の検索を準線形時間で実行可能
パターン P の各接尾部とデータ D の部分文字列との最長一致を Θ(m) 時間で探索

文字列の属性検出

二つの文字列の最長共通部分文字列を高速に発見
繰り返し出現する部分文字列を効率的に検出
データ圧縮の基本となるLempel-Ziv法の解凍を高速化
最長、最短、最頻出の部分文字列を効率的に検索
文字列内に存在しない最短の文字列を検出
一度だけ出現する最短部分文字列を検出
特定の文字列にのみ現れる最短部分文字列を検出

その他の機能

ノード間の最も近い共通先祖 (LCA) を高速に検索
接尾辞の最長共通接頭部を高速に検索
最大 k 文字の不一致を許容したパターン検索を効率的に実行
最長の回文を高速に検出
連続する繰り返しの文字列を効率的に検出
複数の文字列に現れる最長共通部分文字列を高速に発見

接尾辞木の応用

接尾辞木は、バイオインフォマティクス、データ圧縮、検索エンジンなど、多岐にわたる分野で応用されています。

バイオインフォマティクス：DNAやタンパク質の配列解析、パターン検索
データ圧縮：繰り返しパターンの検出、LZWやLZSSなどの圧縮アルゴリズム
検索エンジン：データクラスタリング、効率的なテキスト検索

実装

接尾辞木の実装には、ノードや枝の表現方法、子ノードの管理方法など、様々な選択肢があります。

メモリ使用量

接尾辞木全体に必要なメモリ空間は、文字列の長さ n に対して Θ(n) となります。ただし、実際の実装では、元の文字列の10倍から20倍程度のメモリを消費することがあります。

子ノードの表現方法

兄弟リスト：線形リストを使用。
ハッシュテーブル：高速な検索が可能。
ソート済み/未ソート配列：動的配列を使用。
平衡2分探索木：効率的な挿入/検索が可能。

実装上の注意点

接尾辞木の効率的な実装は、メモリ使用量、検索速度、挿入速度など、様々な要素を考慮する必要があります。メモリ使用量を削減するために、接尾辞配列などの代替データ構造も研究されています。

参考文献

接尾辞木に関するより詳しい情報や実装方法については、以下の文献やWebサイトをご参照ください。

渋谷哲朗「接尾辞木について (PDF)」
Suffix Trees by Dr. Sartaj Sahni
Suffix Trees by Lloyd Allison
Suffix Trees Mark Nelson によるリンク集
NIST's Dictionary of Algorithms and Data Structures: Suffix Tree

接尾辞木は、文字列処理の分野で非常に強力なツールです。その理論と実装を理解することで、より高度な文字列操作やアルゴリズム開発が可能になるでしょう。

もう一度検索