接尾辞配列

接尾辞配列（サフィックスアレイ）とは

接尾辞配列（Suffix Array）とは、文字列の接尾辞（文字列の末尾から始まる部分文字列）を辞書順にソートし、その開始位置を格納した配列のことです。これは、接尾辞木を配列で表現したものであり、主に文字列検索や全文検索などの分野で活用されています。

例えば、文字列 "abracadabra" を考えてみましょう。この文字列の接尾辞は、"abracadabra"、"bracadabra"、"racadabra"、…、"ra"、"a" の11個です。これらの接尾辞を辞書順に並べ替えると、"a"、"abra"、"abracadabra"、…の順になります。接尾辞配列は、この並びに対応する各接尾辞の開始位置を保持します。この例では、接尾辞配列は (11, 8, 1, 4, 6, 9, 2, 5, 7, 10, 3) となります。

接尾辞配列の構築法

接尾辞配列を構築する最も簡単な方法は、接尾辞を比較しながらソートすることです。この方法は、最悪の場合 `O(n^2 log n)` の計算時間を要しますが、より効率的なアルゴリズムを用いることで `O(n log n)` や `O(n)` にまで計算量を削減できます。

• - 単純なソート: 接尾辞を比較ソートする場合、各接尾辞の比較に `O(n)` の時間を要するため、全体の計算量は `O(n^2 log n)` となります。
• - 効率的なソート: 部分的なソート結果を再利用することで、計算量を `O(n log n)` に改善することができます。
• - 接尾辞木からの変換: 接尾辞木を構築後、それを利用して接尾辞配列を生成することで、`O(n)` の時間で構築可能です。
• - SA-IS法: 2009年に発表されたSA-IS法を用いると、`O(n)` の計算量と `max{2n, 4k}` のメモリ使用量で接尾辞配列を構築できます。SA-IS法は実装が比較的容易であり、高速に動作するため、広く利用されています。

接尾辞配列の検索方法

接尾辞配列を用いると、検索対象の文字列がテキスト中に出現する位置を高速に見つけることができます。検索文字列で始まる接尾辞を接尾辞配列上で特定することで、出現位置を特定します。接尾辞配列は辞書順にソートされているため、二分探索を適用できます。

• - 二分探索: 検索文字列の長さを m とすると、単純な二分探索では `O(m log n)` の計算時間を要します。
• - LCP（最長共通接頭辞）の利用: 最長共通接頭辞（LCP）を事前に計算しておけば、二分探索の際の無駄な比較を削減でき、`O(m + log n)` の時間で検索が可能です。LCPとは、隣り合う接尾辞間で共通する先頭の文字数を表します。

ブロックソートとの関連

接尾辞配列のソートアルゴリズムは、ブロックソート（Burrows-Wheeler変換, BWT）にも応用できます。ブロックソートでは、文字列を巡回シフトさせたものを辞書順にソートしますが、接尾辞配列のソートと類似しています。番兵文字を追加することで、接尾辞配列のソート結果をブロックソートに適用できます。

歴史

接尾辞配列は、接尾辞木と比較してメモリ使用量が少ない手法として、Udi ManberとGene Myersによって1990年に開発されました。その後、圧縮接尾辞配列やFM-Indexなどの圧縮全文インデックスが登場し、より効率的な検索技術へと発展しています。

実装例

接尾辞配列を用いた文字列検索ソフトウェアとして、SUFARY（山下達雄氏）やSary（高林哲氏）などが存在します。これらのソフトウェアは、高速な文字列検索を実現するために、接尾辞配列が活用されています。

関連項目

• - 接尾辞木（Suffix Tree）

参考文献

• - Pang Ko and Srinivas Aluru (2003). "Space efficient linear time construction of suffix arrays."
• - Juha Kärkkäinen and Peter Sanders (2003). "Simple linear work suffix array construction."
• - Klaus-Bernd Schürmann and Jens Stoye (2005). "An incomplex algorithm for fast suffix array construction".

もう一度検索