サフィックスツリー

コンピュータサイエンスにおいて、サフィックスツリー（PATツリー、または以前の形式ではポジションツリーとも呼ばれる）は、指定されたテキストのすべてのサフィックスをキーとして、テキスト内の位置を値として含む圧縮トライです。サフィックスツリーを使用すると、多くの重要な文字列操作を特に高速に実装できます。

文字列 に対するこのようなツリーの構築には、の長さに線形の時間と空間がかかります。 一旦構築されると、内の部分文字列の検索、一定数の間違いが許容される場合の部分文字列の検索、正規表現パターンの一致の検索など、いくつかの操作を素早く実行できます。 サフィックスツリーは、最長共通部分文字列問題に対する最初の線形時間ソリューションの 1 つも提供しました。^[2]これらの高速化にはコストがかかり、文字列のサフィックスツリーを格納するには、通常、文字列自体を格納する場合よりも大幅に多くのスペースが必要です。 ${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$

この概念は、Weiner (1973) によって初めて導入されました。Weiner は、接尾辞 の代わりに、各位置の接頭辞識別子、つまり で始まり に一度だけ出現する最短の文字列をトライ^[3]に格納しました。彼のアルゴリズム D は、の非圧縮^[4]トライを取り、 のトライに拡張します。このようにして、 の自明なトライから始めて、 のトライはアルゴリズム D への連続的な呼び出しによって構築できますが、全体の実行時間は です。Weiner のアルゴリズム B は、構築されたトライのサイズに線形な全体の実行時間を実現するために、いくつかの補助データ構造を維持します。後者は、たとえば の場合にノードである可能性があります。Weiner のアルゴリズム C は、最終的に圧縮されたトライを使用して、線形の全体的なストレージ サイズと実行時間を実現します。^[5] Donald Knuth は、学生のVaughan Prattに従って、後者を「1973 年のアルゴリズム」と特徴付けました。^{[独自の研究? [6]教科書} Aho、Hopcroft & Ullman（1974、Sect.9.5）は、Weinerの結果をより簡略化された、よりエレガントな形で再現し、ポジションツリーという用語を導入した。 ${\displaystyle S[i..n]}$${\displaystyle i}$${\displaystyle S}$${\displaystyle S[k+1..n]}$${\displaystyle S[k..n]}$${\displaystyle S[n..n]}$${\displaystyle S[1..n]}$${\displaystyle n-1}$${\displaystyle O(n^{2})}$${\displaystyle O(n^{2})}$${\displaystyle S=a^{n}b^{n}a^{n}b^{n}\$.}$

McCreight (1976) は、 のすべての接尾辞の (圧縮された) トライを構築した最初の人物です。 で始まる接尾辞は通常、接頭辞識別子よりも長くなりますが、圧縮されたトライ内のパス表現のサイズは変わりません。一方、McCreight は Weiner の補助データ構造のほとんどを省略することができ、接尾辞リンクのみが残りました。 ${\displaystyle S}$${\displaystyle i}$

Ukkonen (1995) はさらに構築を簡素化した。^{[6]彼は、現在}Ukkonen のアルゴリズムとして知られる、当時最速のアルゴリズムに匹敵する実行時間で、接尾辞ツリーの最初のオンライン構築を提供した。これらのアルゴリズムはすべて、一定サイズのアルファベットに対して線形時間であり、一般に最悪の場合の実行時間は である。 ${\displaystyle O(n\log n)}$

Farach (1997) は、すべてのアルファベットに最適な最初のサフィックス ツリー構築アルゴリズムを発表しました。特に、これは多項式範囲の整数のアルファベットから抽出された文字列に対する最初の線形時間アルゴリズムです。Farach のアルゴリズムは、外部メモリ、圧縮、簡潔などの サフィックス ツリーとサフィックス配列の両方を構築するための新しいアルゴリズムの基礎となっています。

長さの文字列の接尾辞木は次のような木として定義される: ^[7]${\displaystyle S}$${\displaystyle n}$

1. この木には、 から まで番号が付けられた n 個の葉があります。${\displaystyle 1}$${\displaystyle n}$
2. ルートを除くすべての内部ノードには、少なくとも 2 つの子があります。
3. 各エッジには、 の空でない部分文字列がラベル付けされます。${\displaystyle S}$
4. ノードから始まる 2 つのエッジに、同じ文字で始まる文字列ラベルを設定することはできません。
5. ルートからリーフまでのパスで見つかったすべての文字列ラベルを連結して取得される文字列は、から までの場合はsuffix となります。${\displaystyle i}$${\displaystyle S[i..n]}$${\displaystyle i}$${\displaystyle 1}$${\displaystyle n}$

の接尾辞が別の接尾辞の接頭辞でもある場合、文字列にはそのようなツリーは存在しません。たとえば、文字列abcbcでは、接尾辞bcは接尾辞bcbcの接頭辞でもあります。このような場合、bcを綴るパスはリーフで終わらないため、5 番目のルールに違反します。この問題を修正するために、 は、文字列にない終端記号 (通常は と表記) でパディングされます。これにより、どの接尾辞も別の接尾辞にならないことが保証され、の接尾辞ごとに 1 つずつ、リーフ ノードが存在することになります。^[8]すべての内部非ルート ノードは分岐しているため、このようなノードは最大で 個、ノードは合計で (個のリーフ、内部非ルート ノード、1 個のルート) 個存在します。${\displaystyle S}$${\displaystyle S}$$${\displaystyle n}$${\displaystyle n}$${\displaystyle S}$${\displaystyle n-1}$${\displaystyle n+(n-1)+1=2n}$${\displaystyle n}$${\displaystyle n-1}$

サフィックス リンクは、古い線形時間構築アルゴリズムの重要な機能ですが、Farach のアルゴリズムに基づく新しいアルゴリズムのほとんどはサフィックス リンクを省略しています。完全なサフィックス ツリーでは、すべての内部非ルート ノードに、別の内部ノードへのサフィックス リンクがあります。ルートからノードへのパスが文字列 を表し、 が1 文字で が文字列 (空の場合もある) である場合、 を表す内部ノードへのサフィックス リンクがあります。たとえば、上の図で、 のノードから のノードへのサフィックス リンクを参照してください。サフィックス リンクは、ツリーで実行される一部のアルゴリズムでも使用されます。 ${\displaystyle \chi \alpha}$${\displaystyle \chi}$${\displaystyle \alpha}$${\displaystyle \alpha}$ANANA

一般化されたサフィックス ツリーは、単一の文字列ではなく文字列のセット用に作成されたサフィックス ツリーです。この文字列セットのすべてのサフィックスを表します。各文字列は、異なる終了記号で終了する必要があります。

長さ の文字列の接尾辞木は、文字が多項式範囲の整数のアルファベットから来ている場合（特に、これは定数サイズのアルファベットに当てはまります）、時間内に構築できます。 ^[9] より大きなアルファベットの場合、実行時間は、最初に文字をソートしてサイズの範囲に収めることによって支配されます。一般に、これには時間がかかります。以下のコストは、アルファベットが定数であるという仮定の下で与えられています。 ${\displaystyle S}$${\displaystyle n}$${\displaystyle \Theta (n)}$${\displaystyle O(n)}$${\displaystyle O(n\log n)}$

長さ の文字列に対してサフィックス ツリーが構築されているか、または合計の長さ の文字列のセットに対して一般化サフィックス ツリーが構築されていると仮定します。次の操作を実行できます。 ${\displaystyle S}$${\displaystyle n}$${\displaystyle D=\{S_{1},S_{2},\dots ,S_{K}\}}$${\displaystyle n=n_{1}+n_{2}+\cdots +n_{K}}$

• 文字列を検索:
  • 長さの文字列が時間内の部分文字列であるかどうかを確認します。^[10]${\displaystyle P}$${\displaystyle m}$${\displaystyle O(m)}$
  • 時間内に合計長さのパターンが部分文字列として最初に出現する場所を検索します。${\displaystyle P_{1},\dots ,P_{q}}$${\displaystyle m}$${\displaystyle O(m)}$
  • 時間内の部分文字列として、合計長さのパターンのすべての出現を検索します。^[11]${\displaystyle z}$${\displaystyle P_{1},\dots ,P_{q}}$${\displaystyle m}$${\displaystyle O(m+z)}$
  • 正規表現 Pを時間内に検索すると、線形以下の値になることが予想される。^[12]${\displaystyle n}$
  • パターンの各接尾辞について、 の接頭辞と 内の部分文字列との間の最長一致の長さを時間内で求めます。^[13]これはの一致統計と呼ばれます。${\displaystyle P}$${\displaystyle P[i\dots m]}$${\displaystyle D}$${\displaystyle \Theta (m)}$${\displaystyle P}$
• 文字列のプロパティを見つけます。
  • 文字列の最長共通部分文字列を時間内で見つける。[ ^14]${\displaystyle S_{i}}$${\displaystyle S_{j}}$${\displaystyle \Theta (n_{i}+n_{j})}$
  • 時間内に全ての最大ペア、最大繰り返し、超最大繰り返しを見つけます。^[15]${\displaystyle \Theta (n+z)}$
  • 時間におけるレンペル・ジフ分解を求めよ。^[16]${\displaystyle \Theta (n)}$
  • 時間内に最も長く繰り返される部分文字列を見つけます。${\displaystyle \Theta (n)}$
  • 時間内に最小の長さの最も頻繁に発生する部分文字列を検索します。${\displaystyle \Theta (n)}$
  • そのような文字列がある場合、から までの最短の文字列を、内に出現しない時間内に見つけます。${\displaystyle \Sigma }$${\displaystyle D}$${\displaystyle O(n+z)}$${\displaystyle z}$
  • 時間内に 1 回だけ発生する最短の部分文字列を検索します。${\displaystyle \Theta (n)}$
  • 各 について、 の時間内に他の場所に出現しないの最短の部分文字列を見つけます。${\displaystyle i}$${\displaystyle S_{i}}$${\displaystyle D}$${\displaystyle \Theta (n)}$

サフィックスツリーは、一定時間内にノード間の最小共通祖先を検索できるように準備することができます。^[17]また、次のことも可能です。 ${\displaystyle \Theta (n)}$

• における接尾辞と間の最長共通接頭辞を求めなさい。^[18]${\displaystyle S_{i}[p..n_{i}]}$${\displaystyle S_{j}[q..n_{j}]}$${\displaystyle \Theta (1)}$
• 長さmのパターンPを時間内に最大k個の不一致で探索する。ここでzはヒット数である。^[19]${\displaystyle O(kn+z)}$
• 、^[20]または長さのギャップが許容される場合、または不一致が許容される場合は時間内のすべての最大回文を見つけます。^[21]${\displaystyle z}$${\displaystyle \Theta (n)}$${\displaystyle \Theta (gn)}$${\displaystyle g}$${\displaystyle \Theta (kn)}$${\displaystyle k}$
• 内のすべてのタンデムリピートと、内のkミスマッチタンデムリピートを見つけます。^[22]${\displaystyle z}$ ${\displaystyle O(n\log n+z)}$${\displaystyle O(kn\log(n/k)+z)}$
• 時間内に、少なくとも文字列に対する最長共通部分文字列を見つける。^[23]${\displaystyle k}$${\displaystyle D}$${\displaystyle k=2,\dots ,K}$${\displaystyle \Theta (n)}$
• 与えられた文字列の最長回文部分文字列を（文字列の一般化接尾辞木とその逆を使用して）線形時間で検索します。 ^[24]

サフィックスツリーは、テキスト編集、フリーテキスト検索、計算生物学、その他の応用分野で発生する多数の文字列問題を解決するために使用できます。 ^[25]主なアプリケーションは次のとおりです。^[25]

• 文字列検索、O ( m ) の複雑度、ここでm は部分文字列の長さ（ただし、文字列の接尾辞ツリーを構築するのに必要な初期時間はO ( n ) です）
• 最も長い繰り返し部分文字列を見つける
• 最長共通部分文字列を見つける
• 文字列内の最長回文を見つける

サフィックスツリーはバイオインフォマティクスのアプリケーションでよく使用され、DNAやタンパク質配列（長い文字列として表示）のパターンを検索します。不一致を効率的に検索できることが、サフィックスツリーの最大の強みと言えるでしょう。サフィックスツリーはデータ圧縮にも使用され、重複データを検索したり、バローズ・ウィーラー変換のソート段階で使用したりできます。LZW圧縮方式のバリアントでは、サフィックスツリー（ LZSS ）が使用されます。サフィックスツリーは、一部の検索エンジンで使用されるデータクラスタリングアルゴリズムであるサフィックスツリークラスタリングでも使用されます。^[26]

各ノードとエッジを空間で表現できる場合、ツリー全体を空間で表現できます。ツリー内のすべてのエッジ上のすべての文字列の合計長は ですが、各エッジはSの部分文字列の位置と長さとして格納できるため、コンピュータワードの合計スペース使用量が得られます。サフィックスツリーの最悪のスペース使用量は、フィボナッチワードで見られ、完全なノードになります。 ${\displaystyle \Theta (1)}$${\displaystyle \Theta (n)}$${\displaystyle O(n^{2})}$${\displaystyle \Theta (n)}$${\displaystyle 2n}$

サフィックス ツリーの実装を行う際の重要な選択は、ノード間の親子関係です。最も一般的なのは、兄弟リストと呼ばれるリンク リストを使用することです。各ノードには、その最初の子へのポインタと、そのノードが属する子リスト内の次のノードへのポインタがあります。効率的な実行時間特性を持つその他の実装では、ハッシュ マップ、ソート済みまたはソートされていない配列(配列の倍増を使用)、またはバランス検索ツリーを使用します。私たちが関心を持っているのは、次のことです。

• 特定のキャラクターの子供を見つけるためのコスト。
• 子供を挿入するための費用。
• ノードのすべての子を登録するコスト (下の表の子の数で割った値)。

σ をアルファベットのサイズとすると、次のコストが得られます。 ^{[引用が必要]}

挿入コストは償却され、ハッシュのコストは完全なハッシュに対して与えられます。

各エッジとノードに含まれる情報量が多いため、サフィックス ツリーのコストは非常に高く、適切な実装ではソース テキストのメモリ サイズの約 10 ～ 20 倍を消費します。サフィックス配列を使用すると、この要件は 8 分の 1 に削減されます ( 32 ビット アドレス空間内で構築されたLCP値と 8 ビット文字を含む配列の場合)。この係数はプロパティに依存し、32 ビット システムで 4 バイト幅の文字 (一部のUNIX 系システムで任意のシンボルを格納するために必要、wchar_t を参照) を使用すると 2 に達する場合があります。^{[引用が必要]}研究者は、より小さなインデックス構造を見つけ続けています。

サフィックスツリーの構築を高速化するためのさまざまな並列アルゴリズムが提案されている。^{[27] [28] [29] [30] [31]最近、}作業（シーケンシャルタイム）とスパンを考慮した サフィックスツリー構築の実用的な並列アルゴリズムが開発されました。 このアルゴリズムは、共有メモリマルチコアマシン上で優れた並列スケーラビリティを実現し、40コアマシンを使用して3分以内にヒトゲノム（約3GB ）のインデックスを作成できます。 ^[32]${\displaystyle O(n)}$ ${\displaystyle O(\log ^{2}n)}$

線形ではありますが、サフィックス ツリーのメモリ使用量は、シーケンス コレクションの実際のサイズよりも大幅に高くなります。大きなテキストの場合、構築には外部メモリ アプローチが必要になる場合があります。

外部メモリにサフィックスツリーを構築する理論的な結果があります。Farach-Colton、Ferragina、Muthukrishnan (2000) によるアルゴリズムは理論的に最適であり、I/O の複雑さはソートの複雑さに等しいです。しかし、このアルゴリズムの全体的な複雑さのために、これまでのところ実用的な実装は妨げられています。^[33]

一方、数GB/時間にスケールするディスクベースのサフィックスツリーを構築するための実用的な研究が行われてきました。最先端の手法としては、TDD、^[34] TRELLIS、^[35] DiGeST、^[36] B ² STなどがあります。^[37]

TDDとTRELLISはヒトゲノム全体にスケールアップし、数十ギガバイトのサイズのディスクベースのサフィックスツリーを生成します。^{[34] [35]}しかし、これらの方法では3GBを超えるシーケンスのコレクションを効率的に処理することはできません。^[36] DiGeSTは大幅に優れたパフォーマンスを発揮し、約6時間で6GBのオーダーのシーケンスのコレクションを処理できます。^[36]

これらの方法はすべて、ツリーがメインメモリに収まらないが入力が収まる場合に、サフィックスツリーを効率的に構築できます。最新の方法である B ² ST ^{[37] は、}メインメモリに収まらない入力を処理できるように拡張されます。ERA は、大幅に高速化された最近の並列サフィックスツリー構築方法です。ERA は、16 GB RAM を搭載した 8 コアのデスクトップコンピューターで、19 分でヒトゲノム全体をインデックス化できます。16 ノード (ノードあたり 4 GB RAM) の単純な Linux クラスターでは、ERA は 9 分未満でヒトゲノム全体をインデックス化できます。^[38]

• サフィックスオートマトン

• アホ、アルフレッド V. ;ホップクロフト、ジョン E. ;ウルマン、ジェフリー D. (1974)、『コンピュータアルゴリズムの設計と分析』、Reading/MA: Addison-Wesley、ISBN 0-201-00029-6。
• Apostolico, A.; Iliopoulos, C.; Landau, GM; Schieber, B.; Vishkin, U. (1988)、「アプリケーションによるサフィックスツリーの並列構築」、Algorithmica、3 (1–4): 347–365、doi :10.1007/bf01762122、S2CID  5024136。
• Baeza-Yates, Ricardo A. ; Gonnet, Gaston H. (1996)、「正規表現による高速テキスト検索または試行によるオートマトン検索」、Journal of the ACM、43 (6): 915–936、doi : 10.1145/235809.235810、S2CID  1420298。
• Barsky, Marina; Stege, Ulrike; Thomo, Alex; Upton, Chris (2008)、「ディスク上のサフィックス ツリーを使用したゲノムのインデックス作成のための新しい方法」、CIKM '08: Proceedings of the 17th ACM Conference on Information and Knowledge Management (PDF)、ニューヨーク、ニューヨーク、米国: ACM、pp. 649–658。
• Barsky, Marina; Stege, Ulrike; Thomo, Alex; Upton, Chris (2009)、「非常に大きなゲノム配列の接尾辞ツリー」、CIKM '09: Proceedings of the 18th ACM Conference on Information and Knowledge Management (PDF)、ニューヨーク、ニューヨーク、米国: ACM。
• Farach, Martin (1997)、「大きなアルファベットによる最適なサフィックス ツリーの構築」(PDF)、第 38 回 IEEE コンピュータ サイエンスの基礎に関するシンポジウム (FOCS '97)、pp. 137–143。
• Farach, Martin ; Muthukrishnan, S. (1996)、「最適な対数時間ランダムサフィックスツリー構築」、国際オートマトン言語およびプログラミング会議(PDF)。
• マーティン・ファラック・コルトン;フェラジーナ、パオロ。Muthukrishnan, S. (2000)、「サフィックス ツリー構築のソートの複雑さについて」、Journal of the ACM、47 (6): 987–1011、doi : 10.1145/355541.355547、S2CID  8164822。
• Giegerich, R.; Kurtz, S. (1997)、「From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction」(PDF)、Algorithmica、19 (3​​): 331–353、doi :10.1007/PL00009177、S2CID 18039097、2016-03-03に オリジナル(PDF)からアーカイブ、 2012-07-13 に取得。
• ガスフィールド、ダン（1997）、文字列、木、シーケンスのアルゴリズム：コンピュータサイエンスと計算生物学、ケンブリッジ大学出版局、ISBN 0-521-58519-8。
• Hariharan, Ramesh (1994)、「最適並列サフィックス ツリー構築」、ACM コンピューティング理論シンポジウム(PDF)。
• Iliopoulos, Costas; Rytter, Wojciech (2004)、「サフィックス配列からサフィックスツリーへの並列変換について」、第 15 回オーストラリア 組み合わせアルゴリズム ワークショップ、CiteSeerX  10.1.1.62.6715。
• Mansour, Essam; Allam, Amin; Skiadopoulos, Spiros; Kalnis, Panos (2011)、「ERA: 非常に長い文字列に対する効率的なシリアルおよびパラレル サフィックス ツリーの構築」(PDF)、VLDB Endowment の議事録、5 (1): 49–60、arXiv : 1109.6884、Bibcode :2011arXiv1109.6884M、doi :10.14778/2047485.2047490、S2CID  7582116。
• McCreight, Edward M. (1976)、「スペースを節約したサフィックスツリー構築アルゴリズム」、Journal of the ACM、23 (2): 262–272、CiteSeerX  10.1.1.130.8022、doi :10.1145/321941.321946、S2CID  9250303。
• Phoophakdee, Benjarath; Zaki, Mohammed J. (2007)、「ゲノム規模のディスクベースのサフィックスツリーインデックス」、SIGMOD '07: ACM SIGMOD 国際データ管理会議の議事録、ニューヨーク、ニューヨーク、米国: ACM、pp. 833–844、CiteSeerX  10.1.1.81.6031。
• Sahinalp, Cenk; Vishkin, Uzi (1994)、「サフィックスツリー構築のための対称性の破れ」、ACM Symposium on Theory of Computing、pp. 300–309、doi : 10.1145/195058.195164、ISBN 0-89791-663-8、S2CID  5985171
• スミス、ウィリアム（2003）、文字列のパターンの計算、アディソン・ウェズリー。
• シュン、ジュリアン、ブレロック、ガイ E. (2014)、「単純な並列カルテシアン ツリー アルゴリズムと並列サフィックス ツリー構築への応用」、ACM Transactions on Parallel Computing、1 : 1–20、doi :10.1145/2661653、S2CID  1912378。
• Tata, Sandeep、Hankins, Richard A.、Patel, Jignesh M. (2003)、「実用的なサフィックス ツリーの構築」、VLDB '03: Proceedings of the 30th International Conference on Very Large Data Bases (PDF)、Morgan Kaufmann、pp. 36–47。
• Ukkonen, E. (1995)、「サフィックスツリーのオンライン構築」(PDF)、Algorithmica、14 (3): 249–260、doi :10.1007/BF01206331、S2CID  6027556。
• Weiner, P. (1973)、「線形パターンマッチングアルゴリズム」(PDF)、14th Annual IEEE Symposium on Switching and Automata Theory、pp. 1–11、doi :10.1109/SWAT.1973.13、2016-03-03にオリジナル(PDF)からアーカイブ、 2015-04-16に取得。
• Zamir, Oren; Etzioni, Oren (1998)、「Web ドキュメント クラスタリング: 実現可能性の実証」、SIGIR '98: 情報検索の研究開発に関する第 21 回国際 ACM SIGIR 会議の議事録、ニューヨーク、ニューヨーク、米国: ACM、pp. 46–54、CiteSeerX  10.1.1.36.4719。

• Sartaj Sahniによるサフィックス ツリー
• NIST のアルゴリズムとデータ構造の辞書: サフィックス ツリー
• Burrows-Wheeler変換に基づくユニバーサルデータ圧縮：理論と実践、BWTにおけるサフィックスツリーの応用
• 簡潔なデータ構造の理論と実践、圧縮サフィックスツリーの C++ 実装
• Ukkonen の C によるサフィックス ツリーの実装 パート 1 パート 2 パート 3 パート 4 パート 5 パート 6
• オンライン デモ: Ukkonen のサフィックス ツリーの視覚化