接尾辞木
長さ n {\displaystyle n} の文字列 S {\displaystyle S} に関する接尾辞木は、木構造として次のように定義される ( page 90):
根から葉までのそれぞれの経路に S {\displaystyle S} の接尾辞(接尾部)が一対一に対応する。
各枝には空でない文字列が対応する。
根と葉以外のノードには少なくとも2つの子ノードがある。
どのような文字列にもこういった構成の木構造を構築できるわけではないので、 S {\displaystyle S} には本来含まれない終端記号(一般に $ で表される)を補うことがある。これにより、ある接尾部が別の接尾部の接頭部とならないようにし、 n {\displaystyle n} 個の葉が必ず存在して、それぞれが S {\displaystyle S} の n {\displaystyle n} 個の接尾部のいずれかに対応するようにする。
最長繰り返し部分文字列を Θ ( n ) {\displaystyle \Theta (n)} 時間で探す。 最短でかつ最頻出する部分文字列を Θ ( n ) {\displaystyle \Theta (n)} 時間で探す。 D {\displaystyle D} に現れない Σ {\displaystyle \Sigma } 内の最短文字列が z {\displaystyle z} 個あるとき、 O ( n + z ) {\displaystyle O(n+z)} 時間でそれらを探す。 一度だけ出現する最短部分文字列を Θ ( n ) {\displaystyle \Theta (n)} 時間で探す。 各 i {\displaystyle i} について S i {\displaystyle S_{i}} の部分文字列で D {\displaystyle D} 内で他に出現しない最短なものを Θ ( n ) {\displaystyle \Theta (n)} 時間で探す。
接尾辞木はノード間の最も近い共通先祖 (LCA) の検索を Θ ( n ) {\displaystyle \Theta (n)} 時間でできる( chapter 8)。また、以下のようなことも可能である。
接尾部 S i [ p . . n i ] {\displaystyle S_{i}[p..n_{i}]} と S j [ q . . n j ] {\displaystyle S_{j}[q..n_{j}]} の最長共通接頭部 を Θ ( 1 ) {\displaystyle \Theta (1)} 時間で探す( page 196)、
接尾辞木はバイオインフォマティクスで、DNAや蛋白質を長い文字列に見立てたパターン検索によく使われる。接尾辞木の最大の利点は、ミスマッチを許容した効率的な検索能力である。また、繰り返しのデータを検出できることからデータ圧縮にも使われ、ブロックソートのソート段階でも使われる。データ圧縮法のLZWの一種であるLZSSでも使われている。接尾辞木を使ったデータ・クラスタリングのアルゴリズムが一部の検索エンジンに使われている。
根以外の中間ノードは全て分岐を伴うので、中間ノードの最大個数は n − 1 {\displaystyle n-1} 個となり、全体としては最大 n + ( n − 1 ) + 1 = 2 n {\displaystyle n+(n-1)+1=2n} 個のノードが存在しうる。
接尾辞木の線形時間構築の鍵となるのは「接尾辞リンク(サフィックスリンク)」である。完全な接尾辞木では、根以外の内部ノードは全て他の内部ノードへの接尾辞リンクを持つ。根からあるノードまでの経路に対応する文字列が χ α {\displaystyle \chi \alpha } で χ {\displaystyle \chi } が1つの文字、 α {\displaystyle \alpha } が(空文字列を含む)文字列であるとき、そのノードから α {\displaystyle \alpha } を経路とするノードへの接尾辞リンクが存在する。図示された接尾辞木では、ANA に対応するノードから NA に対応するノードへ接尾辞リンクがある。接尾辞リンクは、接尾辞木を使ったアルゴリズムでも使われる場合がある。