サフィックスツリー

テキスト の接尾辞ツリーBANANA。各部分文字列は特殊文字 で終端されます$。ルートからリーフ（四角で表示）までの6つのパスは、6つの接尾辞A$、NA$、ANA$、NANA$、に対応していますANANA$。BANANA$リーフ内の数字は、対応する接尾辞の開始位置を示します。破線で描かれた接尾辞リンクは、構築時に使用されます。

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

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

歴史

概念は、 Weiner (1973)によって初めて導入されました。Weiner は、接尾辞 ではなく、各位置の接頭辞識別子、つまり で始まりで一度だけ出現する最短の文字列をトライ^{[ 3 ]}に格納しました。彼のアルゴリズム D は、 の非圧縮^{[ 4 ]}トライを取り、それを のトライに拡張します。このようにして、 の自明なトライから始めて、 のトライはアルゴリズム D を連続的に呼び出すことによって構築できますが、全体の実行時間は です。Weiner のアルゴリズム Bは、構築されたトライのサイズに線形な全体の実行時間を実現するために、いくつかの補助データ構造を維持しています。後者は、例えば に対してノードになることができます。Weinerのアルゴリズム Cは最終的に圧縮されたトライを使用して、線形の全体的なストレージサイズと実行時間を実現します。^{[ 5 ]}ドナルド・クヌースはその後、学生のヴォーン・プラットの言葉を引用して、後者を「1973年のアルゴリズム」と評した。^{[ 6 ]} 教科書Aho、Hopcroft & Ullman（1974年、第9.5節）は、ウェイナーの結果を簡略化してより洗練された形で再現し、「ポジションツリー」という用語を導入した。 ${\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)}$
  • 時間内で最も長く繰り返される部分文字列を見つけます。^{[ 17 ]} ${\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)}$

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

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

アプリケーション

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

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

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

実装

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

サフィックスツリーの実装において重要な選択は、ノード間の親子関係です。最も一般的なのは、兄弟リストと呼ばれる連結リストを使用することです。各ノードは、その最初の子ノードへのポインタと、そのノードが属する子リスト内の次のノードへのポインタを持ちます。実行時間効率の高い他の実装では、ハッシュマップ、ソート済みまたはソートされていない配列（配列の倍増を使用）、またはバランス探索木が使用されます。私たちは以下の点に注目しています。

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

σをアルファベットのサイズとすると、以下のコストがかかります 。

	見上げる	挿入	トラバーサル
兄弟リスト / ソートされていない配列	O ( σ )	Θ(1)	Θ(1)
ビットワイズ兄弟木	O (log σ )	Θ(1)	Θ(1)
ハッシュマップ	Θ(1)	Θ(1)	O ( σ )
バランス探索木	O (log σ )	O (log σ )	O (1)
ソートされた配列	O (log σ )	O ( σ )	O (1)
ハッシュマップ + 兄弟リスト	O (1)	O (1)	O (1)

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

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

並列構築

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

外部工事

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

外部メモリに接尾辞木を構築する理論的な成果は既に存在する。Farach -Colton、Ferragina、Muthukrishnan (2000)によるアルゴリズム は理論的に最適であり、I/Oの複雑さはソートの複雑さと同等である。しかし、このアルゴリズム全体の複雑さが、これまでのところ実用化を妨げている。^{[ 34 ]}

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

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

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

参照

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

注記

1. Donald E. Knuth、James H. Morris、Vaughan R. Pratt (1977年6月). 「文字列における高速パターンマッチング」(PDF) . SIAM Journal on Computing . 6 (2): 323– 350. doi : 10.1137/0206024 .こちら：p.339 下。
2. クヌースは1970年にこの問題は線形時間では解けないと予想した。 ^{[ 1 ]} 1973年にこれはワイナーの接尾辞木アルゴリズムによって反証された。
3. この用語は、ここでは Weiner の先駆的なデータ構造を、上記で定義されMcCreight (1976)以前には考慮されてい。
4. つまり、各ブランチは1文字でラベル付けされます
5. 圧縮されていないサンプルツリーとその圧縮された対応物については、 File:WeinerB aaaabbbbbaaaabbbb.gifとFile:WeinerC aaaabbbbbaaaabbbb.gifを参照してください
6. ギーゲリッヒ＆クルツ（1997）。
7. ガスフィールド（1999）、90ページ。harvtxt エラー: ターゲットなし: CITEREFGusfield1999 (ヘルプ)
8. ガスフィールド（1999）、p.90-91。harvtxt エラー: ターゲットなし: CITEREFGusfield1999 (ヘルプ)
9. ファラハ（1997年）。
10. ガスフィールド（1999）、92ページ。harvtxt エラー: ターゲットなし: CITEREFGusfield1999 (ヘルプ)
11. ガスフィールド（1999）、123ページ。harvtxt エラー: ターゲットなし: CITEREFGusfield1999 (ヘルプ)
12. Baeza-Yates & Gonnet (1996)。
13. ガスフィールド（1999）、132ページ。harvtxt エラー: ターゲットなし: CITEREFGusfield1999 (ヘルプ)
14. ガスフィールド（1999）、125ページ。harvtxt エラー: ターゲットなし: CITEREFGusfield1999 (ヘルプ)
15. ガスフィールド（1999）、144ページ。harvtxt エラー: ターゲットなし: CITEREFGusfield1999 (ヘルプ)
16. ガスフィールド（1999）、166ページ。harvtxt エラー: ターゲットなし: CITEREFGusfield1999 (ヘルプ)
17. このような部分文字列は、サフィックスツリー内の最大深さの内部ノードに対応するため、深さ優先探索を使用して線形時間で見つけることができます。
18. ガスフィールド（1999）、第8章。harvtxt エラー: ターゲットなし: CITEREFGusfield1999 (ヘルプ)
19. ガスフィールド（1999）、196ページ。harvtxt エラー: ターゲットなし: CITEREFGusfield1999 (ヘルプ)
20. ガスフィールド（1999）、p.200。harvtxt エラー: ターゲットなし: CITEREFGusfield1999 (ヘルプ)
21. ガスフィールド（1999）、198ページ。harvtxt エラー: ターゲットなし: CITEREFGusfield1999 (ヘルプ)
22. ガスフィールド（1999）、p.201。harvtxt エラー: ターゲットなし: CITEREFGusfield1999 (ヘルプ)
23. ガスフィールド（1999）、p.204。harvtxt エラー: ターゲットなし: CITEREFGusfield1999 (ヘルプ)
24. ガスフィールド（1999）、205ページ。harvtxt エラー: ターゲットなし: CITEREFGusfield1999 (ヘルプ)
25. ガスフィールド（1999）、197–199頁。harvtxt エラー: ターゲットなし: CITEREFGusfield1999 (ヘルプ)
26. Allison, L. 「Suffix Trees」 . 2008年10月13日時点のオリジナルよりアーカイブ。 2008年10月14日閲覧。
27. 最初に紹介されたのはZamir & Etzioni (1998)です。
28. Apostolico et al. (1988) .
29. ハリハラン (1994) .
30. Sahinalp & Vishkin (1994) .
31. ファラックとムトゥクリシュナン (1996)。
32. イリオプロスとリッター (2004)。
33. Shun & Blelloch (2014) .
34. スミス（2003） .
35. タタ、ハンキンス、パテル（2003年）。
36. プーパクディー＆ザキ (2007)。
37. Barskyら。 (2008)。
38. Barsky et al. (2009) .
39. Mansour et al. (2011) .

参考文献

• Aho, Alfred V. ; Hopcroft, John E. ; Ullman, Jeffrey D. (1974), The Design and Analysis of Computer Algorithms , Reading/MA: Addison-Wesley, Bibcode : 1974daca.book.....A , 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年3月3日にオリジナル(PDF)からアーカイブ、 2012年7月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)、Proceedings of the 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: Proceedings of the ACM SIGMOD International Conference on Management of Data、ニューヨーク、ニューヨーク、米国: 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。
• タタ、サンディープ、ハンキンス、リチャード A.、パテル、ジグネシュ M. (2003)、「実用的なサフィックスツリー構築」、VLDB '03: 第30回国際超大規模データベース会議議事録(PDF)、モーガン・カウフマン、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年3月3日にオリジナル（PDF）からアーカイブ、2015年4月16日取得。
• Zamir, Oren; Etzioni, Oren (1998)、「Web document clustering: a feasibility demonstration」、SIGIR '98: Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval、ニューヨーク、ニューヨーク、米国: ACM、pp.  46– 54、CiteSeerX  10.1.1.36.4719。

外部リンク

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

「 https://en.wikipedia.org/w/index.php?title=Suffix_tree&oldid=1308257852」から取得