接尾辞木のソースを表示

[[画像:Suffix_tree_BANANA.svg|thumb|250px|right|文字列 <code>BANANA</code> に <code>$</code> を補った接尾辞木。根から葉（四角で表示）への6つの経路が6つの接尾辞 <code>A$</code>, <code>NA$</code>, <code>ANA$</code>, <code>NANA$</code>, <code>ANANA$</code>, <code>BANANA$</code> に対応。四角の中の数字は対応する接尾辞の開始位置を示す。接尾辞リンクは破線の矢印で示されている。]]
'''接尾辞木'''（せつびじき）または'''サフィックス木'''（{{lang-en-short|Suffix tree}}）は、与えられた[[文字列]]の[[接尾辞|接尾部]]を[[木構造 (データ構造)|木構造]]([[基数木]])で表す[[データ構造]]であり、多くの文字列操作の高速な実装に利用されている。

文字列 <math>S</math> の接尾辞木は[[木構造 (データ構造)|木構造]]であり、その枝には文字列が対応し、木構造の根から葉までの経路ごとにそれぞれ <math>S</math> の接尾部の1つが対応している。従って、これは <math>S</math> の接尾部に関する[[基数木]]である。

文字列 <math>S</math> からそのような木構造を構築するには、<math>S</math> の長さに対して線形な時間と空間を要する。構築できれば、いくつかの操作が高速化される（<math>S</math> の部分文字列を探す、誤字をある程度許容した上での部分文字列特定、[[正規表現]]パターンとのマッチングなど）。接尾辞木は[[最長共通部分文字列]]問題の線形な解法の1つでもある。これらの高速化の代償として、接尾辞木に要するメモリ空間は文字列そのものを格納するのに要するメモリ空間よりもかなり大きくなる。

== 歴史 == 
この概念は ''position tree'' として 1973年、Weiner が初めて紹介した<ref name="Wei73">{{cite conference | author=P. Weiner | title=Linear pattern matching algorithm
 | book-title=14th Annual IEEE Symposium on Switching and Automata Theory | date=1973年 | pages=1-11}}</ref>。[[ドナルド・クヌース]]はその論文を "Algorithm of the Year 1973" と評した。1976年、McCreight が構築法を大幅に単純化し<ref name="McC76">{{cite journal | author=Edward M. McCreight | title=A Space-Economical Suffix Tree Construction Algorithm | journal=Journal of the ACM | volume=23 | issue=2 | date=1976年 | pages=262--272 | url=http://doi.acm.org/10.1145/321941.321946}}</ref>、1995年には Ukkonen がさらに洗練させた<ref name="Ukk95">{{cite journal | author=E. Ukkonen | title=On-line construction of suffix trees | journal=Algorithmica | volume=14 | issue=3 | date=1995年 | pages=249--260 | url=http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf}}</ref><ref name="GK97">{{cite journal | author=R. Giegerich and S. Kurtz | title=From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction | journal=Algorithmica | volume=19 | issue=3 | date=1997年 | pages=331--353 | url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.9399}}</ref>。Ukkonen のアルゴリズムは接尾辞木を線形時間かつ[[オンラインアルゴリズム|オンライン]]で構築する最初のアルゴリズム（文字列全体を入力する前から構築を開始できるアルゴリズム）であった。

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

: BANANA
: ANANA
: NANA
: ANA
: NA
: A

従って、長さ <math>n</math> の文字列の接尾部としては、元の文字列も含めると <math>n</math> 個の文字列が存在することになる。

== 定義 ==
長さ <math>n</math> の文字列 <math>S</math> に関する接尾辞木は、木構造として次のように定義される (<ref name="Gus97">{{cite book | last = Gusfield | first = Dan | origyear = 1997 | date = 1999年 | title = Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology | publisher = Cambridge University Press | location = USA | id = ISBN 0-521-58519-8}}</ref> page 90): 
* 根から葉までのそれぞれの経路に <math>S</math> の接尾辞（接尾部）が一対一に対応する。
* 各枝には空でない文字列が対応する。
* 根と葉以外のノードには少なくとも2つの子ノードがある。

どのような文字列にもこういった構成の木構造を構築できるわけではないので、<math>S</math> には本来含まれない終端記号（一般に <code>$</code> で表される）を補うことがある。これにより、ある接尾部が別の接尾部の接頭部とならないようにし、<math>n</math> 個の葉が必ず存在して、それぞれが <math>S</math> の <math>n</math> 個の接尾部のいずれかに対応するようにする。根以外の中間ノードは全て分岐を伴うので、中間ノードの最大個数は <math>n-1</math> 個となり、全体としては最大 <math>n+(n-1)+1=2n</math> 個のノードが存在しうる。

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

== 機能 ==
文字のサイズが一定または整数の場合、長さ <math>n</math> の文字列 <math>S</math> に関する接尾辞木の構築には <math>\Theta(n)</math> の時間がかかる<ref name="Far97">{{cite conference  | author=Martin Farach | title=Optimal suffix tree construction with large alphabets | book-title=Foundations of Computer Science, 38th Annual Symposium on | date=1997 | pages=137--143 | url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.4336}}</ref>。文字サイズが一定でない場合、構築時間は実装に依存する。以下では文字サイズが一定という前提でコストを表示している。そうでない場合、コストは実装に依存する。

長さ <math>n</math> の文字列 <math>S</math> に関する接尾辞木があるとする。あるいは、長さの総和が <math>n=|n_1|+|n_2|+...+|n_K|</math> の文字列集合 <math>D=\{S_1,S_2,...,S_K\}</math> の[[汎用接尾辞木]]があるとする。これについて、以下のような機能がある。

* 文字列検索:
** 長さ <math>m</math> の文字列 <math>P</math> が部分文字列かどうかを <math>O(m)</math> 時間で判定する（<ref name="Gus97"/> page 92）。
** 長さの総和が <math>m</math> のパターン群 <math>P_1,...,P_q</math> が最初に出現する位置を <math>O(m)</math> 時間で検出する（接尾辞木を Ukkonen のアルゴリズムで構築した場合）。
** 長さの総和が <math>m</math> の部分文字列群が <math>z</math> 回出現する全位置を <math>O(m + z)</math> 時間で検出する（<ref name="Gus97"/> page 123）。
** [[正規表現]] ''P'' の検索を <math>n</math> の準線形時間で行うことが期待できる（<ref name="BYG96">{{cite journal | author=Ricardo A. Baeza-Yates and Gaston H. Gonnet | title=Fast text searching for regular expressions or automaton searching on tries | journal=Journal of the ACM | volume=43 | number=6 | date=1996年 | issn=0004-5411 | pages=915--936 | doi=10.1145/235809.235810 | publisher=ACM Press | address=New York, NY, USA | url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.133.2155}}</ref>）。
** パターン <math>P</math> の各接尾部について、<math>P[i...m]</math> で表される接頭部と <math>D</math> の部分文字列との最長一致を <math>\Theta(m)</math> 時間で探す（<ref name="Gus97"/> page 132）。これを <math>P</math> の '''matching statistics''' と呼ぶ。
* 文字列の属性検出:
** 文字列 <math>S_i</math> と <math>S_j</math> の[[最長共通部分文字列]]を <math>\Theta(n_i + n_j)</math> 時間で探す（<ref name="Gus97"/> page 125）。
** 全ての繰り返し出現する部分文字列（maximal repeats/supermaximal repeats）を <math>\Theta(n + z)</math> 時間で探す（<ref name="Gus97"/> page 144）。
** [[Lempel–Ziv–Welch|LZW]]などのLempel-Ziv法の解凍を <math>\Theta(n)</math> 時間で探す（<ref name="Gus97"/> page 166）。
** 最長繰り返し部分文字列を <math>\Theta(n)</math> 時間で探す。
** 最短でかつ最頻出する部分文字列を <math>\Theta(n)</math> 時間で探す。
** <math>D</math> に現れない <math>\Sigma</math> 内の最短文字列が <math>z</math> 個あるとき、<math>O(n + z)</math> 時間でそれらを探す。
** 一度だけ出現する最短部分文字列を <math>\Theta(n)</math> 時間で探す。
** 各 <math>i</math> について <math>S_i</math> の部分文字列で <math>D</math> 内で他に出現しない最短なものを <math>\Theta(n)</math> 時間で探す。

接尾辞木はノード間の[[最も近い共通先祖]] (LCA) の検索を <math>\Theta(n)</math> 時間でできる（<ref name="Gus97"/> chapter 8）。また、以下のようなことも可能である。
* 接尾部 <math>S_i[p..n_i]</math> と <math>S_j[q..n_j]</math> の最長共通接頭部 を <math>\Theta(1)</math> 時間で探す（<ref name="Gus97"/> page 196）、
* 長さ <math>m</math> のパターン <math>P</math> を最大 <math>k</math> 文字の不一致を許容した上で探すとき、<math>z</math> 個見つかる場合の時間が <math>O(k n + z)</math> となる（<ref name="Gus97"/> page 200）。
* 最長の[[回文]]を <math>\Theta(n)</math> 時間で探す（<ref name="Gus97"/> page 198）。長さ <math>g</math> のギャップを含む場合は <math>\Theta(g n)</math>、<math>k</math> 文字の不一致を許す場合は <math>\Theta(k n)</math> となる（<ref name="Gus97"/> page 201）。
* <math>z</math>個の連続の繰り返し（tandem repeats）を <math>O(n \log n + z)</math> 時間で探す。k文字の不一致を許容する場合 <math>O(k n \log (n/k) + z)</math> となる（<ref name="Gus97"/> page 204）。
* <math>D</math> 内の少なくとも <math>k</math> 個（<math>k=2..K</math>）の文字列にある[[最長共通部分文字列]]を <math>\Theta(n)</math> 時間で探す（<ref name="Gus97"/> page 205）。

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

== 実装 ==
各ノードまたは枝に要するメモリ空間を <math>\Theta(1)</math> で表すと、接尾辞木全体には <math>\Theta(n)</math> の空間が必要である。枝の長さ（対応する文字数）の総和は <math>O(n^2)</math> だが、各枝に対応する情報は ''S'' の部分文字列の位置と長さであり（部分文字列のコピーを枝ごとに持つ必要はない）、全体として必要なメモリ空間は <math>\Theta(n)</math> ワードとなる。最悪の場合の例として、[[フィボナッチ列]]を接尾辞木で表すと、<math>2n</math> 個のノードを要する。

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

文字のサイズ（種類）を <math>\sigma</math> としたとき、コストは以下のようになる。

{|
! 
! 参照
! 挿入
! 検索
|-
! 兄弟リスト/未ソート配列
| <math>O(\sigma)</math> 
| <math>\Theta(1)</math>
| <math>\Theta(1)</math>
|-
! ハッシュテーブル      
| <math>\Theta(1)</math>
| <math>\Theta(1)</math>
| <math>O(\sigma)</math>
|-
! 平衡探索木            
| <math>O(\log \sigma)</math>
| <math>O(\log \sigma)</math>
| <math>O(1)</math>
|-
! ソート済配列          
| <math>O(\log \sigma)</math>
| <math>O(\sigma)</math>
| <math>O(1)</math>
|-
! ハッシュ + 兄弟リスト 
| <math>O(1)</math>
| <math>O(1)</math>
| <math>O(1)</math>
|}

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

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

== 関連項目 ==
* [[接尾辞配列]] (Suffix Array)
* [[接尾辞トライ木]]

== 参考文献 ==
<references/>

== 外部リンク ==
* [http://www.hgc.jp/~tshibuya/classes/2007seq_04suffixtrees.pdf 接尾辞木について] (PDF) 渋谷哲朗（東京大学医科学研究所ヒトゲノム解析センター）
* [http://www.cise.ufl.edu/~sahni/dsaaj/enrich/c16/suffix.htm Suffix Trees] by Dr. Sartaj Sahni (CISE Department Chair at University of Florida)
* [http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Suffix Suffix Trees] by Lloyd Allison
* [http://datacompression.info/SuffixTrees.shtml Suffix Trees] Mark Nelson によるリンク集
* [http://www.nist.gov/dads/HTML/suffixtree.html NIST's Dictionary of Algorithms and Data Structures: Suffix Tree]
* [http://www.icir.org/christian/libstree/ libstree] C言語で書かれた汎用接尾辞木ライブラリ
* [http://search.cpan.org/dist/Tree-Suffix/ Tree::Suffix] libstree の Perl 版
* [http://www.cs.ucdavis.edu/~gusfield/strmat.html Strmat] C言語で書かれたより高速な汎用接尾辞木ライブラリ（配列で実装している）
* [http://hkn.eecs.berkeley.edu/~dyoo/python/suffix_trees/ SuffixTree] Strmat の Python 版

{{データ構造}}
{{デフォルトソート:せつひしき}}
[[Category:文字列データ構造]]
[[Category:アルゴリズム]]
[[Category:ツリー (データ構造)]]