接尾辞木

接尾辞木またはサフィックス木は、与えられた文字列の接尾部を木構造で表すデータ構造であり、多くの文字列操作の高速な実装に利用されている。

文字列 の接尾辞木は木構造であり、その枝には文字列が対応し、木構造の根から葉までの経路ごとにそれぞれ の接尾部の1つが対応している。従って、これは の接尾部に関する基数木である。

文字列 からそのような木構造を構築するには、 の長さに対して線形な時間と空間を要する。構築できれば、いくつかの操作が高速化される。接尾辞木は最長共通部分文字列問題の線形な解法の1つでもある。これらの高速化の代償として、接尾辞木に要するメモリ空間は文字列そのものを格納するのに要するメモリ空間よりもかなり大きくなる。

1. 歴史
-----

この概念は //position tree// として 1973年、Weiner が初めて紹介した。ドナルド・クヌースはその論文を "Algorithm of the Year 1973" と評した。1976年、McCreight が構築法を大幅に単純化し、1995年には Ukkonen がさらに洗練させた。Ukkonen のアルゴリズムは接尾辞木を線形時間かつオンラインで構築する最初のアルゴリズムであった。

2. 接尾部の例
--------

ある文字列の接尾部とは、その文字列の先頭から1文字ずつ文字を除いていった残りの部分文字列全体を指す。例えば、"BANANA" の接尾部は次のようになる。

BANANA ANANA NANA ANA NA A従って、長さ の文字列の接尾部としては、元の文字列も含めると 個の文字列が存在することになる。

3. 定義
-----

長さ の文字列 に関する接尾辞木は、木構造として次のように定義される :

根から葉までのそれぞれの経路に の接尾辞が一対一に対応する。
各枝には空でない文字列が対応する。
根と葉以外のノードには少なくとも2つの子ノードがある。どのような文字列にもこういった構成の木構造を構築できるわけではないので、 には本来含まれない終端記号を補うことがある。これにより、ある接尾部が別の接尾部の接頭部とならないようにし、 個の葉が必ず存在して、それぞれが の 個の接尾部のいずれかに対応するようにする。根以外の中間ノードは全て分岐を伴うので、中間ノードの最大個数は 個となり、全体としては最大 個のノードが存在しうる。

接尾辞木の線形時間構築の鍵となるのは「接尾辞リンク」である。完全な接尾辞木では、根以外の内部ノードは全て他の内部ノードへの接尾辞リンクを持つ。根からあるノードまでの経路に対応する文字列が で が1つの文字、 が文字列であるとき、そのノードから を経路とするノードへの接尾辞リンクが存在する。図示された接尾辞木では、ANA に対応するノードから NA に対応するノードへ接尾辞リンクがある。接尾辞リンクは、接尾辞木を使ったアルゴリズムでも使われる場合がある。

4. 機能
-----

文字のサイズが一定または整数の場合、長さ の文字列 に関する接尾辞木の構築には の時間がかかる。文字サイズが一定でない場合、構築時間は実装に依存する。以下では文字サイズが一定という前提でコストを表示している。そうでない場合、コストは実装に依存する。

長さ の文字列 に関する接尾辞木があるとする。あるいは、長さの総和が の文字列集合 の汎用接尾辞木があるとする。これについて、以下のような機能がある。

文字列検索:
長さ の文字列 が部分文字列かどうかを 時間で判定する。
長さの総和が のパターン群 が最初に出現する位置を 時間で検出する。
長さの総和が の部分文字列群が 回出現する全位置を 時間で検出する。
正規表現 //P// の検索を の準線形時間で行うことが期待できる。
パターン の各接尾部について、 で表される接頭部と の部分文字列との最長一致を 時間で探す。これを の matching statistics と呼ぶ。
文字列の属性検出:
文字列 と の最長共通部分文字列を 時間で探す。
全ての繰り返し出現する部分文字列を 時間で探す。
LZWなどのLempel-Ziv法の解凍を 時間で探す。
最長繰り返し部分文字列を 時間で探す。
最短でかつ最頻出する部分文字列を 時間で探す。
に現れない 内の最短文字列が 個あるとき、 時間でそれらを探す。
一度だけ出現する最短部分文字列を 時間で探す。
各 について の部分文字列で 内で他に出現しない最短なものを 時間で探す。接尾辞木はノード間の最も近い共通先祖  の検索を 時間でできる。また、以下のようなことも可能である。

接尾部 と の最長共通接頭部 を 時間で探す、
長さ のパターン を最大 文字の不一致を許容した上で探すとき、 個見つかる場合の時間が となる。
最長の回文を 時間で探す。長さ のギャップを含む場合は 、 文字の不一致を許す場合は となる。
個の連続の繰り返しを 時間で探す。k文字の不一致を許容する場合 となる。
内の少なくとも 個の文字列にある最長共通部分文字列を 時間で探す。

5. 応用
-----

接尾辞木はバイオインフォマティクスで、DNAや蛋白質を長い文字列に見立てたパターン検索によく使われる。接尾辞木の最大の利点は、ミスマッチを許容した効率的な検索能力である。また、繰り返しのデータを検出できることからデータ圧縮にも使われ、ブロックソートのソート段階でも使われる。データ圧縮法のLZWの一種であるLZSSでも使われている。接尾辞木を使ったデータ・クラスタリングのアルゴリズムが一部の検索エンジンに使われている。

6. 実装
-----

各ノードまたは枝に要するメモリ空間を で表すと、接尾辞木全体には の空間が必要である。枝の長さの総和は だが、各枝に対応する情報は //S// の部分文字列の位置と長さであり、全体として必要なメモリ空間は ワードとなる。最悪の場合の例として、フィボナッチ列を接尾辞木で表すと、 個のノードを要する。

接尾辞木を実装する際の重要な問題として、親ノードと子ノードの関係の表し方がある。最も典型的な実装は「兄弟リスト; sibling list」と呼ばれる線形リストを使う方法である。各ノードが最初の子ノードへのポインタを持ち、子ノード同士を線形リストでつなぐ。ハッシュテーブル、ソート済み/未ソート配列、平衡2分探索木なども使われ、それぞれ実行時間特性が異なる。ここでは以下に注目する。

ある文字に対応する子ノードを探すコスト
子ノードを挿入するコスト
あるノードの全子ノードをリストアップするコスト文字のサイズを としたとき、コストは以下のようになる。

なお、挿入コストは償却計算量であり、ハッシュ操作のコストは衝突が発生しない完全ハッシュを前提としている。

各ノードや枝に情報が分散するため、接尾辞木は効率が悪く、よい実装であっても元の文字列の約10倍から20倍のメモリを消費する。接尾辞配列はこれを4倍程度に削減でき、研究者はさらなるメモリ使用量削減方法を模索している。

7. 関連項目
-------

接尾辞配列 
接尾辞トライ木

8. 参考文献
-------

9. 外部リンク
--------

[1]  渋谷哲朗
[2] by Dr. Sartaj Sahni 
[3] by Lloyd Allison
[4] Mark Nelson によるリンク集
[5]
[6] C言語で書かれた汎用接尾辞木ライブラリ
[7] libstree の Perl 版
[8] C言語で書かれたより高速な汎用接尾辞木ライブラリ
[9] Strmat の Python 版