接尾辞木（せつびじき）またはサフィックス木（）は、与えられた文字列の接尾部を木構造(基数木)で表すデータ構造であり、多くの文字列操作の高速な実装に利用されている。文字列 formula_1 の接尾辞木は木構造であり、その枝には文字列が対応し、木構造の根から葉までの経路ごとにそれぞれ formula_1 の接尾部の1つが対応している。従って、これは formula_1 の接尾部に関する基数木である。文字列 formula_1 からそのような木構造を構築するには、formula_1 の長さに対して線形な時間と空間を要する。構築できれば、いくつかの操作が高速化される（formula_1 の部分文字列を探す、誤字をある程度許容した上での部分文字列特定、正規表現パターンとのマッチングなど）。接尾辞木は最長共通部分文字列問題の線形な解法の1つでもある。これらの高速化の代償として、接尾辞木に要するメモリ空間は文字列そのものを格納するのに要するメモリ空間よりもかなり大きくなる。この概念は "position tree" として 1973年、Weiner が初めて紹介した。ドナルド・クヌースはその論文を "Algorithm of the Year 1973" と評した。1976年、McCreight が構築法を大幅に単純化し、1995年には Ukkonen がさらに洗練させた。Ukkonen のアルゴリズムは接尾辞木を線形時間かつオンラインで構築する最初のアルゴリズム（文字列全体を入力する前から構築を開始できるアルゴリズム）であった。ある文字列の接尾部とは、その文字列の先頭から1文字ずつ文字を除いていった残りの部分文字列全体を指す。例えば、"BANANA" の接尾部は次のようになる。従って、長さ formula_7 の文字列の接尾部としては、元の文字列も含めると formula_7 個の文字列が存在することになる。長さ formula_7 の文字列 formula_1 に関する接尾辞木は、木構造として次のように定義される ( page 90): どのような文字列にもこういった構成の木構造を構築できるわけではないので、formula_1 には本来含まれない終端記号（一般に codice_1 で表される）を補うことがある。これにより、ある接尾部が別の接尾部の接頭部とならないようにし、formula_7 個の葉が必ず存在して、それぞれが formula_1 の formula_7 個の接尾部のいずれかに対応するようにする。根以外の中間ノードは全て分岐を伴うので、中間ノードの最大個数は formula_16 個となり、全体としては最大 formula_17 個のノードが存在しうる。接尾辞木の線形時間構築の鍵となるのは「接尾辞リンク（サフィックスリンク）」である。完全な接尾辞木では、根以外の内部ノードは全て他の内部ノードへの接尾辞リンクを持つ。根からあるノードまでの経路に対応する文字列が formula_18 で formula_19 が1つの文字、formula_20 が（空文字列を含む）文字列であるとき、そのノードから formula_20 を経路とするノードへの接尾辞リンクが存在する。図示された接尾辞木では、codice_2 に対応するノードから codice_3 に対応するノードへ接尾辞リンクがある。接尾辞リンクは、接尾辞木を使ったアルゴリズムでも使われる場合がある。文字のサイズが一定または整数の場合、長さ formula_7 の文字列 formula_1 に関する接尾辞木の構築には formula_24 の時間がかかる。文字サイズが一定でない場合、構築時間は実装に依存する。以下では文字サイズが一定という前提でコストを表示している。そうでない場合、コストは実装に依存する。長さ formula_7 の文字列 formula_1 に関する接尾辞木があるとする。あるいは、長さの総和が formula_27 の文字列集合 formula_28 の汎用接尾辞木があるとする。これについて、以下のような機能がある。接尾辞木はノード間の最も近い共通先祖 (LCA) の検索を formula_24 時間でできる（ chapter 8）。また、以下のようなことも可能である。接尾辞木はバイオインフォマティクスで、DNAや蛋白質を長い文字列に見立てたパターン検索によく使われる。接尾辞木の最大の利点は、ミスマッチを許容した効率的な検索能力である。また、繰り返しのデータを検出できることからデータ圧縮にも使われ、ブロックソートのソート段階でも使われる。データ圧縮法のLZWの一種であるLZSSでも使われている。接尾辞木を使ったデータ・クラスタリングのアルゴリズムが一部の検索エンジンに使われている。各ノードまたは枝に要するメモリ空間を formula_63 で表すと、接尾辞木全体には formula_24 の空間が必要である。枝の長さ（対応する文字数）の総和は formula_83 だが、各枝に対応する情報は "S" の部分文字列の位置と長さであり（部分文字列のコピーを枝ごとに持つ必要はない）、全体として必要なメモリ空間は formula_24 ワードとなる。最悪の場合の例として、フィボナッチ列を接尾辞木で表すと、formula_85 個のノードを要する。接尾辞木を実装する際の重要な問題として、親ノードと子ノードの関係の表し方がある。最も典型的な実装は「兄弟リスト; sibling list」と呼ばれる線形リストを使う方法である。各ノードが最初の子ノードへのポインタを持ち、子ノード同士を線形リストでつなぐ（子供同士のリストなので兄弟リスト）。ハッシュテーブル、ソート済み/未ソート配列（動的配列）、平衡2分探索木なども使われ、それぞれ実行時間特性が異なる。ここでは以下に注目する。文字のサイズ（種類）を formula_86 としたとき、コストは以下のようになる。なお、挿入コストは償却計算量（amortized complexity）であり、ハッシュ操作のコストは衝突が発生しない完全ハッシュを前提としている。各ノードや枝に情報が分散するため、接尾辞木は効率が悪く、よい実装であっても元の文字列の約10倍から20倍のメモリを消費する。接尾辞配列はこれを4倍程度に削減でき、研究者はさらなるメモリ使用量削減方法を模索している。

出典:wikipedia