接尾辞木
この概念は position tree として 1973年、Weiner が初めて紹介した。ドナルド・クヌースはその論文を "Algorithm of the Year 1973" と評した。1976年、McCreight が構築法を大幅に単純化し、1995年には Ukkonen がさらに洗練させた。Ukkonen のアルゴリズムは接尾辞木を線形時間かつオンラインで構築する最初のアルゴリズム(文字列全体を入力する前から構築を開始できるアルゴリズム)であった。
接尾辞木(せつびじき)またはサフィックス木(英: Suffix tree)は、与えられた文字列の接尾部を木構造(基数木)で表すデータ構造であり、多くの文字列操作の高速な実装に利用されている。
文字列 S {\displaystyle S} の接尾辞木は木構造であり、その枝には文字列が対応し、木構造の根から葉までの経路ごとにそれぞれ S {\displaystyle S} の接尾部の1つが対応している。従って、これは S {\displaystyle S} の接尾部に関する基数木である。
文字列 S {\displaystyle S} からそのような木構造を構築するには、 S {\displaystyle S} の長さに対して線形な時間と空間を要する。構築できれば、いくつかの操作が高速化される( S {\displaystyle S} の部分文字列を探す、誤字をある程度許容した上での部分文字列特定、正規表現パターンとのマッチングなど)。接尾辞木は最長共通部分文字列問題の線形な解法の1つでもある。これらの高速化の代償として、接尾辞木に要するメモリ空間は文字列そのものを格納するのに要するメモリ空間よりもかなり大きくなる。
文字のサイズが一定または整数の場合、長さ n {\displaystyle n} の文字列 S {\displaystyle S} に関する接尾辞木の構築には Θ ( n ) {\displaystyle \Theta (n)} の時間がかかる。文字サイズが一定でない場合、構築時間は実装に依存する。以下では文字サイズが一定という前提でコストを表示している。そうでない場合、コストは実装に依存する。
長さ n {\displaystyle n} の文字列 S {\displaystyle S} に関する接尾辞木があるとする。あるいは、長さの総和が n = | n 1 | + | n 2 | + . . . + | n K | {\displaystyle n=|n_{1}|+|n_{2}|+...+|n_{K}|} の文字列集合 D = { S 1 , S 2 , . . . , S K } {\displaystyle D=\{S_{1},S_{2},...,S_{K}\}} の汎用接尾辞木があるとする。これについて、以下のような機能がある。
文字列検索: 長さ m {\displaystyle m} の文字列 P {\displaystyle P} が部分文字列かどうかを O ( m ) {\displaystyle O(m)} 時間で判定する( page 92)。 長さの総和が m {\displaystyle m} のパターン群 P 1 , . . . , P q {\displaystyle P_{1},...,P_{q}} が最初に出現する位置を O ( m ) {\displaystyle O(m)} 時間で検出する(接尾辞木を Ukkonen のアルゴリズムで構築した場合)。