接尾辞木
BANANA に $ を補った接尾辞木。根から葉（四角で表示）への6つの経路が6つの接尾辞 A$, NA$, ANA$, NANA$, ANANA$, BANANA$ に対応。四角の中の数字は対応する接尾辞の開始位置を示す。接尾辞リンクは破線の矢印で示されている。接尾辞木（せつびじき）またはサフィックス木（英: Suffix tree）は、与えられた文字列の接尾部を木構造(基数木)で表すデータ構造であり、多くの文字列操作の高速な実装に利用されている。
文字列 S の接尾辞木は木構造であり、その枝には文字列が対応し、木構造の根から葉までの経路ごとにそれぞれ S の接尾部の1つが対応している。従って、これは S の接尾部に関する基数木である。
文字列 S からそのような木構造を構築するには、S の長さに対して線形な時間と空間を要する。構築できれば、いくつかの操作が高速化される（S の部分文字列を探す、誤字をある程度許容した上での部分文字列特定、正規表現パターンとのマッチングなど）。接尾辞木は最長共通部分文字列問題の線形な解法の1つでもある。これらの高速化の代償として、接尾辞木に要するメモリ空間は文字列そのものを格納するのに要するメモリ空間よりもかなり大きくなる。
目次 |
[編集] 歴史
この概念は position tree として 1973年、Weiner が初めて紹介した[1]。ドナルド・クヌースはその論文を "Algorithm of the Year 1973" と評した。1976年、McCreight が構築法を大幅に単純化し[2]、1995年には Ukkonen がさらに洗練させた[3][4]。Ukkonen のアルゴリズムは接尾辞木を線形時間かつオンラインで構築する最初のアルゴリズム（文字列全体を入力する前から構築を開始できるアルゴリズム）であった。
[編集] 接尾部の例
ある文字列の接尾部とは、その文字列の先頭から1文字ずつ文字を除いていった残りの部分文字列全体を指す。例えば、"BANANA" の接尾部は次のようになる。
- BANANA
- ANANA
- NANA
- ANA
- NA
- A
従って、長さ n の文字列の接尾部としては、元の文字列も含めると n 個の文字列が存在することになる。
[編集] 定義
長さ n の文字列 S に関する接尾辞木は、木構造として次のように定義される ([5] page 90):
- 根から葉までのそれぞれの経路に S の接尾辞（接尾部）が一対一に対応する。
- 各枝には空でない文字列が対応する。
- 根と葉以外のノードには少なくとも2つの子ノードがある。
どのような文字列にもこういった構成の木構造を構築できるわけではないので、S には本来含まれない終端記号（一般に $ で表される）を補うことがある。これにより、ある接尾部が別の接尾部の接頭部とならないようにし、n 個の葉が必ず存在して、それぞれが S の n 個の接尾部のいずれかに対応するようにする。根以外の中間ノードは全て分岐を伴うので、中間ノードの最大個数は n − 1 個となり、全体としては最大 n + (n − 1) + 1 = 2n 個のノードが存在しうる。
接尾辞木の線形時間構築の鍵となるのは「接尾辞リンク（サフィックスリンク）」である。完全な接尾辞木では、根以外の内部ノードは全て他の内部ノードへの接尾辞リンクを持つ。根からあるノードまでの経路に対応する文字列が χα で χ が1つの文字、α が（空文字列を含む）文字列であるとき、そのノードから α を経路とするノードへの接尾辞リンクが存在する。図示された接尾辞木では、ANA に対応するノードから NA に対応するノードへ接尾辞リンクがある。接尾辞リンクは、接尾辞木を使ったアルゴリズムでも使われる場合がある。
[編集] 機能
文字のサイズが一定または整数の場合、長さ n の文字列 S に関する接尾辞木の構築には Θ(n) の時間がかかる[6]。文字サイズが一定でない場合、構築時間は実装に依存する。以下では文字サイズが一定という前提でコストを表示している。そうでない場合、コストは実装に依存する。
長さ n の文字列 S に関する接尾辞木があるとする。あるいは、長さの総和が n = | n1 | + | n2 | + ... + | nK | の文字列集合 D = {S1,S2,...,SK} の汎用接尾辞木があるとする。これについて、以下のような機能がある。
- 文字列検索:
- 長さ m の文字列 P が部分文字列かどうかを O(m) 時間で判定する（[5] page 92）。
- 長さの総和が m のパターン群 P1,...,Pq が最初に出現する位置を O(m) 時間で検出する（接尾辞木を Ukkonen のアルゴリズムで構築した場合）。
- 長さの総和が m の部分文字列群が z 回出現する全位置を O(m + z) 時間で検出する（[5] page 123）。
- 正規表現 P の検索を n の準線形時間で行うことが期待できる（[7]）。
- パターン P の各接尾部について、P[i...m] で表される接頭部と D の部分文字列との最長一致を Θ(m) 時間で探す（[5] page 132）。これを P の matching statistics と呼ぶ。
- 文字列の属性検出:
- 文字列 Si と Sj の最長共通部分文字列を Θ(ni + nj) 時間で探す（[5] page 125）。
- 全ての繰り返し出現する部分文字列（maximal repeats/supermaximal repeats）を Θ(n + z) 時間で探す（[5] page 144）。
- LZWなどの Lempel-Ziv 法の解凍を Θ(n) 時間で探す（[5] page 166）。
- 最長繰り返し部分文字列を Θ(n) 時間で探す。
- 最短でかつ最頻出する部分文字列を Θ(n) 時間で探す。
- D に現れない Σ 内の最短文字列が z 個あるとき、O(n + z) 時間でそれらを探す。
- 一度だけ出現する最短部分文字列を Θ(n) 時間で探す。
- 各 i について Si の部分文字列で D 内で他に出現しない最短なものを Θ(n) 時間で探す。
接尾辞木はノード間の最も近い共通先祖 (LCA) の検索を Θ(n) 時間でできる（[5] chapter 8）。また、以下のようなことも可能である。
- 接尾部 Si[p..ni] と Sj[q..nj] の最長共通接頭部 を Θ(1) 時間で探す（[5] page 196）、
- 長さ m のパターン P を最大 k 文字の不一致を許容した上で探すとき、z 個見つかる場合の時間が O(kn + z) となる（[5] page 200）。
- 最長の回文を Θ(n) 時間で探す（[5] page 198）。長さ g のギャップを含む場合は Θ(gn)、k 文字の不一致を許す場合は Θ(kn) となる（[5] page 201）。
- z個の連続の繰り返し（tandem repeats）を O(nlog n + z) 時間で探す。k文字の不一致を許容する場合 O(knlog(n / k) + z) となる（[5] page 204）。
- D 内の少なくとも k 個（k = 2..K）の文字列にある最長共通部分文字列を Θ(n) 時間で探す（[5] page 205）。
[編集] 応用
接尾辞木はバイオインフォマティクスで、DNAや蛋白質を長い文字列に見立てたパターン検索によく使われる。接尾辞木の最大の利点は、ミスマッチを許容した効率的な検索能力である。また、繰り返しのデータを検出できることからデータ圧縮にも使われ、ブロックソートのソート段階でも使われる。データ圧縮法のLZWの一種であるLZSSでも使われている。接尾辞木を使ったデータ・クラスタリングのアルゴリズムが一部の検索エンジンに使われている。
[編集] 実装
各ノードまたは枝に要するメモリ空間を Θ(1) で表すと、接尾辞木全体には Θ(n) の空間が必要である。枝の長さ（対応する文字数）の総和は O(n2) だが、各枝に対応する情報は S の部分文字列の位置と長さであり（部分文字列のコピーを枝ごとに持つ必要はない）、全体として必要なメモリ空間は Θ(n) ワードとなる。最悪の場合の例として、フィボナッチ文字列を接尾辞木で表すと、2n 個のノードを要する。
接尾辞木を実装する際の重要な問題として、親ノードと子ノードの関係の表し方がある。最も典型的な実装は「兄弟リスト; sibling list」と呼ばれる線形リストを使う方法である。各ノードが最初の子ノードへのポインタを持ち、子ノード同士を線形リストでつなぐ（子供同士のリストなので兄弟リスト）。ハッシュテーブル、ソート済み/未ソート配列（動的配列）、平衡2分探索木なども使われ、それぞれ実行時間特性が異なる。ここでは以下に注目する。
- ある文字に対応する子ノードを探すコスト
- 子ノードを挿入するコスト
- あるノードの全子ノードをリストアップするコスト（下表では子ノード数で割った値）
文字のサイズ（種類）を σ としたとき、コストは以下のようになる。
| 参照 | 挿入 | 検索 | |
|---|---|---|---|
| 兄弟リスト/未ソート配列 | O(σ) | Θ(1) | Θ(1) |
| ハッシュテーブル | Θ(1) | Θ(1) | O(σ) |
| 平衡探索木 | O(log σ) | O(log σ) | O(1) |
| ソート済配列 | O(log σ) | O(σ) | O(1) |
| ハッシュ + 兄弟リスト | O(1) | O(1) | O(1) |
なお、挿入コストは償却計算量（amortized complexity）であり、ハッシュ操作のコストは衝突が発生しない完全ハッシュを前提としている。
各ノードや枝に情報が分散するため、接尾辞木は効率が悪く、よい実装であっても元の文字列の約10倍から20倍のメモリを消費する。接尾辞配列はこれを4倍程度に削減でき、研究者はさらなるメモリ使用量削減方法を模索している。
[編集] 関連項目
[編集] 参考文献
- ^ P. Weiner (1973年). “Linear pattern matching algorithm”. 14th Annual IEEE Symposium on Switching and Automata Theory. pp. 1-11
- ^ Edward M. McCreight (1976年). “A Space-Economical Suffix Tree Construction Algorithm”. Journal of the ACM 23 (2): 262--272.
- ^ E. Ukkonen (1995年). “On-line construction of suffix trees”. Algorithmica 14 (3): 249--260.
- ^ R. Giegerich and S. Kurtz (1997年). “From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction”. Algorithmica 19 (3): 331--353.
- ^ a b c d e f g h i j k l m n Gusfield, Dan (1999年) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8.
- ^ Martin Farach (1997). “Optimal suffix tree construction with large alphabets”. Foundations of Computer Science, 38th Annual Symposium on. pp. 137--143
- ^ Ricardo A. Baeza-Yates and Gaston H. Gonnet (1996年). “Fast text searching for regular expressions or automaton searching on tries”. Journal of the ACM (ACM Press) 43 (6): 915--936. doi:10.1145/235809.235810. ISSN 0004-5411.
[編集] 外部リンク
- 接尾辞木について (PDF) 渋谷哲朗（東京大学医科学研究所ヒトゲノム解析センター）
- Suffix Trees by Dr. Sartaj Sahni (CISE Department Chair at University of Florida)
- Suffix Trees by Lloyd Allison
- Suffix Trees Mark Nelson によるリンク集
- NIST's Dictionary of Algorithms and Data Structures: Suffix Tree
- libstree C言語で書かれた汎用接尾辞木ライブラリ
- Tree::Suffix libstree の Perl 版
- Strmat C言語で書かれたより高速な汎用接尾辞木ライブラリ（配列で実装している）
- SuffixTree Strmat の Python 版
|
||||||||||||||||||||||||||||||||||||||||||||||
