接尾辞配列

コンピュータサイエンスにおいて、接尾辞配列とは、文字列のすべての接尾辞をソートした配列のことである。これは、全文索引、データ圧縮アルゴリズム、書誌計量学などの分野で用いられるデータ構造である。

接尾辞配列は、接尾辞ツリーに代わるシンプルで省スペースな方法として、Manber & Myers (1990)によって導入されました。これらは、1987 年にGaston GonnetによってPAT 配列という名前で独自に発見されていました( Gonnet、Baeza-Yates & Snider 1992 )。

Li、Li 、 Huo（2016）は、最初のインプレイス${\displaystyle {\mathcal {O}}(n)}$時間および空間の両方で最適な時間サフィックス配列構築アルゴリズム。ここで、インプレースとは、アルゴリズムが必要とするのは だけであることを意味する。${\displaystyle {\mathcal {O}}(1)}$入力文字列と出力接尾辞配列の外側にある追加スペース。

拡張サフィックス配列 (ESA) は、サフィックスツリーの完全な機能を再現し、同じ時間とメモリの複雑さを維持する追加のテーブルを備えたサフィックス配列です。^{[ 1 ]} 文字列のすべてのサフィックスではなく、一部のサフィックスのみのソート済み配列は、スパースサフィックス配列と呼ばれます。^{[ 2 ]}

させて${\displaystyle S=S[1]S[2]...S[n]}$になる${\textstyle n}$-文字列にして${\displaystyle S[i,j]}$のサブストリングを表す${\displaystyle S}$範囲は${\displaystyle i}$に${\displaystyle j}$包括的。

接尾辞配列${\displaystyle A}$の${\displaystyle S}$は、接尾辞の開始位置を提供する整数の配列として定義されます。${\displaystyle S}$辞書順。つまり、エントリは${\displaystyle A[i]}$開始位置が含まれています${\displaystyle i}$-th 最小の接尾辞${\displaystyle S}$そしてすべての${\displaystyle 1\leq i\leq n}$:${\displaystyle S[A[i-1],n]<S[A[i],n]}$。

各接尾辞${\displaystyle S}$表示される${\displaystyle A}$正確に1回。接尾辞は単純な文字列です。これらの文字列は（紙の辞書のように）ソートされてから、開始位置（整数インデックス）が保存されます。${\displaystyle A}$。

テキストを検討してください${\displaystyle S}$=banana$インデックス化される:

テキストの末尾には、$他のどの文字よりも小さく、辞書的にも特別な番人文字が付けられています。テキストには以下の接尾辞が付いています。

これらの接尾辞は昇順に並べ替えることができます。

接尾辞配列${\displaystyle A}$ソートされたこれらの接尾辞の開始位置が含まれています。

接尾辞配列（分かりやすくするために、接尾辞を縦書きで下に表記）：

例えば、${\displaystyle A[3]}$値4を含み、したがって、位置4から始まる接尾辞を参照します。${\displaystyle S}$、これは接尾辞ですana$。

接尾辞配列は接尾辞木と密接に関連しています。

• 接尾辞配列は、接尾辞木を深さ優先探索することで構築できます。接尾辞配列は、探索中に訪問された葉ラベルに対応します。ただし、辺は最初の文字の辞書順で訪問されます。
• 接尾辞配列とLCP配列を組み合わせることで、接尾辞木を線形時間で構築できます。アルゴリズムの詳細については、LCP配列に関する記事の該当セクションを参照してください。

すべてのサフィックスツリーアルゴリズムは、追加情報（ LCP配列など）で強化されたサフィックス配列を使用するアルゴリズムに体系的に置き換えることができ、同じ問題を同じ時間計算量で解決できることが示されています。^{[ 1 ]} サフィックス配列のサフィックスツリーに対する利点には、スペース要件の改善、より単純な線形時間の構築アルゴリズム（例えば、ウッコネンのアルゴリズムと比較して）、およびキャッシュ局所性の改善などがあります。^{[ 3 ]}

サフィックス配列は、サフィックスツリーのスペース要件を改善するために、 Manber & Myers (1990)によって導入されました。サフィックス配列は、${\displaystyle n}$整数。整数を仮定すると、${\displaystyle 4}$バイト、サフィックス配列には${\displaystyle 4n}$合計バイト数。これは、${\displaystyle 20n}$慎重なサフィックスツリー実装に必要なバイト。^{[ 4 ]}

しかし、特定のアプリケーションでは、サフィックス配列のスペース要件が依然として問題となる場合があります。ビット単位で分析すると、サフィックス配列は${\displaystyle {\mathcal {O}}(n\log n)}$スペース、一方元のテキストはサイズのアルファベット上${\displaystyle \sigma }$必要なのは${\displaystyle {\mathcal {O}}(n\log \sigma )}$ビット。ヒトゲノムの場合${\displaystyle \sigma =4}$そして${\displaystyle n=3.4\times 10^{9}}$したがって、接尾辞配列はゲノム自体よりも約16倍のメモリを占有することになる。

こうした不一致が、圧縮接尾辞配列や、FMインデックスなどのBWTベースの圧縮全文インデックスへの流れを促した。これらのデータ構造は、テキストのサイズ内、あるいはそれ以下のスペースしか必要としない。

接尾辞ツリーは以下のように構築できます。${\displaystyle {\mathcal {O}}(n)}$また、深さ優先でツリーを走査することにより、接尾辞配列に変換することもできます。${\displaystyle {\mathcal {O}}(n)}$なので、接尾辞配列を構築できるアルゴリズムが存在する${\displaystyle {\mathcal {O}}(n)}$。

接尾辞配列を構築する素朴なアプローチは、比較ベースのソートアルゴリズムを使用することです。これらのアルゴリズムは、${\displaystyle {\mathcal {O}}(n\log n)}$接尾辞の比較ですが、接尾辞の比較は${\displaystyle {\mathcal {O}}(n)}$時間なので、このアプローチの全体的な実行時間は${\displaystyle {\mathcal {O}}(n^{2}\log n)}$。

より高度なアルゴリズムは、ソートされる接尾辞が任意の文字列ではなく、互いに関連しているという事実を利用します。これらのアルゴリズムは、次の目標を達成しようとします。^{[ 5 ]}

• 漸近的複雑性の最小値${\displaystyle \Theta (n)}$
• 軽量であるため、テキストと接尾辞配列自体以外に作業用メモリはほとんど、あるいは全く必要ありません。
• 実際には速い

すべての目標を達成した最初のアルゴリズムの 1 つは、Nong、Zhang 、 Chan (2009)の SA-IS アルゴリズムです。このアルゴリズムは比較的単純 ( 100 LOC未満) で、 LCP 配列を同時に構築するように拡張できます。^{[ 6 ] SA-IS アルゴリズムは、既知のサフィックス配列構築アルゴリズムの中で最も高速なものの 1 つは、Yuta Mori [ 7 ]}による慎重な実装により、他のほとんどの線形または超線形構築アプローチよりも優れたパフォーマンスを発揮します。

時間と空間の要件に加えて、接尾辞配列構築アルゴリズムは、サポートされるアルファベットによっても区別されます。 定数アルファベットではアルファベットのサイズが定数によって制限され、整数アルファベットでは文字が範囲に応じて整数になります。${\displaystyle n}$文字比較のみが許可される一般的なアルファベット。^{[ 8 ]}

ほとんどの接尾辞配列構築アルゴリズムは、次のアプローチのいずれかに基づいています。^{[ 5 ]}

• 接頭辞倍増アルゴリズムは、Karp、Miller 、 Rosenberg（1972）の戦略に基づいています。そのアイデアは、接尾辞の辞書順を尊重する接頭辞を見つけることです。評価された接頭辞の長さは、接頭辞が一意になり、関連する接尾辞のランクが示されるまで、アルゴリズムの各反復で倍増します。
• 再帰アルゴリズムは、Farach (1997)による接尾辞ツリー構築アルゴリズムのアプローチに従い、接尾辞のサブセットを再帰的にソートします。このサブセットを使用して、残りの接尾辞の接尾辞配列を推論します。これらの2つの接尾辞配列をマージして、最終的な接尾辞配列を計算します。
• 誘導コピーアルゴリズムは、既にソートされた部分集合を使用して残りの接尾辞を高速にソートするという点で、再帰アルゴリズムと似ています。違いは、これらのアルゴリズムは選択された接尾辞部分集合をソートするために再帰よりも反復を優先する点です。この多様なアルゴリズム群の調査は、Puglisi、Smyth 、 Turpin (2007)によってまとめられています。

整数アルファベットに対するよく知られた再帰アルゴリズムは、Kärkkäinen & Sanders (2003)のDC3 / skewアルゴリズムです。これは線形時間で実行され、並列^{[ 9 ]}および外部メモリ^{[ 10 ]}のサフィックス配列構築アルゴリズムの基礎として成功裏に使用されています。

Salson ら (2010)による最近の研究では、編集されたテキストの接尾辞配列をゼロから再構築するのではなく更新するアルゴリズムが提案されています。理論上の最悪の場合の時間計算量は${\displaystyle {\mathcal {O}}(n\log n)}$実際にはうまく機能しているようです。著者らの実験結果によると、元のテキストに妥当な数の文字を挿入する場合、動的接尾辞配列の実装は再構築よりも一般的に効率的であることが示されています。

実際のオープンソース作業では、接尾辞配列の構築によく使われるルーチンは、1999 年の Larsson-Sadakane アルゴリズムに基づく qsufsort でした。^{[ 11 ]}このルーチンは、2017 年時点で「メインメモリで知られている最速の接尾辞ソートアルゴリズム」である Yuta Mori の DivSufSort に取って代わられました。これも LCP 配列を計算するように変更できます。これは、Itoh-Tanaka と組み合わせた誘導コピーを使用します。^{[ 12 ]} 2021 年に、Ilya Grebnov によってこのアルゴリズムのより高速な実装が発表されました。^{[ 13 ]}これは、平均してSilesia コーパスでの DivSufSort 実装よりも 65% のパフォーマンス向上を示しました。^{[ 14 ]}

接尾辞配列の概念は、複数の文字列に拡張できます。これは一般化接尾辞配列 (GSA) と呼ばれ、一連の文字列のすべての接尾辞 (たとえば、${\displaystyle S=S_{1},S_{2},S_{3},...,S_{k}}$そして、各文字列のすべての接尾辞とともに辞書式順序でソートされます。^{[ 15 ]}

文字列の接尾辞配列は、部分文字列パターンのすべての出現箇所を素早く見つけるためのインデックスとして使用できます。${\displaystyle P}$文字列内で${\displaystyle S}$パターンのすべての出現箇所を見つけることは、部分文字列で始まるすべての接尾辞を見つけることと同等です。辞書順のおかげで、これらの接尾辞は接尾辞配列にグループ化され、2つの二分探索で効率的に見つけることができます。最初の探索で区間の開始位置を特定し、2番目の探索で終了位置を決定します。

n = len ( S )def search ( P : str ) -> tuple [ int , int ]: """パターン P で始まる S のすべての接尾辞を表す 区間 A[s:r] (終了インデックスを除く) となるようなインデックス (s, r) を返します。  """ # 区間の開始位置を見つけるl = 0 # Python では、配列のインデックスは 0 から始まりますr = n while l < r : mid = ( l + r ) // 2 # 除算は最も近い整数に切り捨てます# suffixAt(A[i]) は i 番目に小さい接尾辞ですif P > suffixAt ( A [ mid ]): l = mid + 1 else : r = mid s = l# 区間の終了位置を見つけるr = n while l < r : mid = ( l + r ) // 2 if suffixAt ( A [ mid ]) . startswith ( P ): l = mid + 1 else : r = mid return ( s , r )

部分文字列パターンを見つける${\displaystyle P}$長さ${\displaystyle m}$文字列の中で${\displaystyle S}$長さ${\displaystyle n}$取る${\displaystyle {\mathcal {O}}(m\log n)}$時間、単一の接尾辞の比較には比較する必要がある${\displaystyle m}$文字。マンバーとマイヤーズ（1990）は、この境界をどのように改善できるかを説明しています。${\displaystyle {\mathcal {O}}(m+\log n)}$LCP情報を使用した時間。このアイデアは、パターンと現在の検索区間の最長共通接頭辞の一部であることがすでにわかっている場合、パターン比較で特定の文字を再比較する必要がないというものです。Abouelhoda 、Kurtz 、 Ohlebusch（2004）は、この上限をさらに改善し、検索時間を達成しました。${\displaystyle {\mathcal {O}}(m)}$接尾辞木から知られているように、一定のアルファベットサイズの場合。

接尾辞ソートアルゴリズムは、バロウズ・ウィーラー変換（BWT）の計算に使用できます。BWTでは、文字列のすべての巡回順列をソートする必要があります。文字列が、他のすべての文字よりも辞書順で小さい特別な文字列末尾文字（つまり、$）で終わる場合、ソートされた回転BWT行列の順序は、接尾辞配列内の接尾辞の順序に対応します。したがって、 BWTは、まずテキストの接尾辞配列を作成し、次にBWT文字列を推論することで、線形時間で計算できます。${\displaystyle BWT[i]=S[A[i]-1]}$。

接尾辞配列は、例文ベースの機械翻訳で部分文字列を検索するためにも使用でき、統計的機械翻訳で使用される完全なフレーズテーブルよりもはるかに少ないストレージを必要とします。

接尾辞配列の多くの追加的な応用には、LCP配列が必要です。これらのいくつかは、 LCP配列の応用セクションで詳しく説明されています。

接尾辞木は、パターンマッチング、文字列マッチング、インデックス作成、テキスト統計などの分野で幅広く応用されている強力なデータ構造です。しかし、かなりのスペースを占有するため、ゲノム解析のように大量のデータを処理する必要がある多くのリアルタイムアプリケーションでは欠点となります。この欠点を克服するために、拡張接尾辞配列が開発されました。これは、接尾辞配列と、接尾辞木内のノード間の親子関係に関する情報を含む子テーブルと呼ばれる追加のテーブルで構成されるデータ構造です。この木のノード分岐データ構造はリンクリストです。拡張接尾辞配列は、スペース効率と時間計算量の両面で接尾辞木よりも優れており、実装も容易です。さらに、LCP-区間木と呼ばれる抽象概念を用いることで、接尾辞木を使用するあらゆるアルゴリズムに適用できます。長さのパターンを検索する時間計算量は${\displaystyle m}$拡張サフィックス配列では${\displaystyle {\mathcal {O}}(m|\Sigma |)}$。

拡張接尾辞配列は、2つの配列で構成されています。

1. pos配列 pos[1,...n]: これは、すべてのS接尾辞のソート済みリストを表します。接尾辞が大きすぎるため、スペースの複雑さを軽減するために、配列には接尾辞の最初の位置のみが格納されます。
2. lcp配​​列 lcp[1,...n]: これはn個の整数の配列で、pos配列に格納されている2つの連続する接尾辞の最長共通接頭辞の長さを保持します。

• Manber, Udi ; Myers, Gene (1990).接尾辞配列: オンライン文字列検索のための新しい方法. 第 1 回 ACM-SIAM 離散アルゴリズムシンポジウム. pp. 319–327 . 
• Manber, Udi ; Myers, Gene (1993). "接尾辞配列: オンライン文字列検索のための新しい方法" . SIAM Journal on Computing . 22 (5): 935– 948. doi : 10.1137/0222058 . S2CID 5074629 . 
• Li, Zhize; Li, Jian; Huo, Hongwei (2016). Optimal In-Place Suffix Sorting . Proceedings of the 25th International Symposium on String Processing and Information Retrieval (SPIRE). Lecture Notes in Computer Science. Vol.  11147. Springer. pp. 268–284 . arXiv : 1610.08305 . doi : 10.1007/978-3-030-00479-8_22 . ISBN  978-3-030-00478-1。
• Shi, Fei (1996). 「複数文字列のための接尾辞配列：オンライン複数文字列検索手法」『並行性と並列性、プログラミング、ネットワーク、セキュリティ』Lecture Notes in Computer Science、第 1179巻、Springer Berlin Heidelberg、pp . 11–22。doi : 10.1007 / BFb0027775。ISBN  978-3-540-62031-0。
• Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2002).拡張サフィックス配列とそのゲノム解析への応用. バイオインフォマティクスにおけるアルゴリズム.コンピュータサイエンス講義ノート. Vol.  2452. doi : 10.1007/3-540-45784-4_35 . ISBN 978-3-540-44211-0。
• Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2004 年 3 月). 「拡張サフィックス配列によるサフィックスツリーの置き換え」 . Journal of Discrete Algorithms . 2 (1): 53– 86. doi : 10.1016/S1570-8667(03)00065-0 . ISSN 1570-8667 . 
• Gonnet, GH; Baeza-Yates, RA; Snider, T. (1992). "テキストのための新しいインデックス: PAT ツリーと PAT アレイ" .情報検索: データ構造とアルゴリズム.
• Kurtz, S (1999). "サフィックスツリーのスペース要件の削減". Software: Practice and Experience . 29 (13): 1149– 1171. doi : 10.1002/(SICI)1097-024X(199911)29:13 < 1149::AID-SPE274 > 3.0.CO ; 2-O . hdl : 10338.dmlcz/135448 .
• Puglisi, Simon J.; Smyth, WF; Turpin, Andrew H. (2007). "接尾辞配列構築アルゴリズムの分類" . ACM Computing Surveys . 39 (2): 4. doi : 10.1145/1242471.1242472 . S2CID 2653529 . 
• Nong, Ge; Zhang, Sen; Chan, Wai Hong (2009).ほぼ純粋な誘導ソートによる線形サフィックス配列の構築. 2009 データ圧縮会議. p.  193. doi : 10.1109/DCC.2009.42 . ISBN 978-0-7695-3592-0。
• Fischer, Johannes (2011). LCP配列の誘導. アルゴリズムとデータ構造. コンピュータサイエンス講義ノート. 第6844巻. 374–385 頁. arXiv : 1101.3448 . doi : 10.1007 /978-3-642-22300-6_32 . ISBN  978-3-642-22299-3。
• Salson, M.; Lecroq, T.; Léonard, M.; Mouchard, L. (2010). "動的拡張サフィックス配列" . Journal of Discrete Algorithms . 8 (2): 241. doi : 10.1016/j.jda.2009.02.007 .
• Burkhardt, Stefan; Kärkkäinen, Juha (2003).高速軽量接尾辞配列の構築と検証. 組み合わせパターンマッチング. コンピュータサイエンス講義ノート. 第 2676巻. 55–69ページ. doi : 10.1007/3-540-44888-8_5 . ISBN  978-3-540-40311-1。
• Karp, Richard M.; Miller, Raymond E.; Rosenberg, Arnold L. (1972).文字列、木、配列における繰り返しパターンの迅速な識別. 第4回ACM理論計算シンポジウム（STOC '72）議事録. pp. 125–136 . doi : 10.1145/800152.804905 . 
• Farach, M. (1997).大規模アルファベットを用いた最適な接尾辞木構築. 第38回コンピュータサイエンス基礎に関する年次シンポジウム論文集. doi : 10.1109/SFCS.1997.646102 . ISBN 0-8186-8197-7。
• 私、トモヒロです。ケルカイネン、ユハ。ケンパ、ドミニク (2014)。スパースサフィックスソートの高速化。ライプニッツ国際情報学会議 (LIPIcs)。 Vol.  25. ダグシュトゥール城 – ライプニッツ中央情報局。 pp. 386–396 . doi : 10.4230/LIPIcs.STACS.2014.386。ISBN  978-3-939897-65-1。
• Kärkkäinen, Juha; Sanders, Peter (2003).単純な線形作業接尾辞配列の構築. Automata, Languages and Programming. Lecture Notes in Computer Science. Vol.  2719. doi : 10.1007/3-540-45061-0_73 . ISBN 978-3-540-40493-4。
• デメンティエフ、ローマ人。ケルカイネン、ユハ。メーナート、イェンス。サンダース、ピーター(2008)。「外部メモリのサフィックス配列構造の改善」。実験アルゴリズムのジャーナル。12 : 1–24 .土井: 10.1145/1227161.1402296。S2CID 12296500。 
• Kulla, Fabian; Sanders, Peter (2007). "スケーラブルな並列サフィックス配列の構築". Parallel Computing . 33 (9): 605–612 . doi : 10.1016/j.parco.2007.06.004 .
• Mohamed Ibrahim Abouelhoda、Stefan Kurtz、Enno Ohlebusch。「拡張サフィックス配列によるサフィックスツリーの置き換え」。Journal of Discrete Algorithms、2(1):53–86、2004年。
• Dong Kyue Kim、Jeong Eun Jeon、Heejin Park。「無視できないサイズのアルファベットに対応する接尾辞木と接尾辞配列の機能を備えた効率的なインデックスデータ構造」。String Processing and Information Retrieval Lecture Notes in Computer Science、138～149ページ、2004年。

• Javaにおける接尾辞配列
• BWT 用の接尾辞ソートモジュール (C コード)
• Rubyにおける接尾辞配列の実装
• 接尾辞配列ライブラリとツール
• 統一されたインターフェースを備えた、さまざまなサフィックス配列のC/C++実装を含むプロジェクト
• 接尾辞配列を構築するための、高速で軽量かつ堅牢なC APIライブラリ
• Pythonにおける接尾辞配列の実装
• 接尾辞木を用いたC言語による線形時間接尾辞配列の実装