　読み込み中...

接尾辞配列

接尾辞配列（せつびじはいれつ、Suffix Array）とは、検索アルゴリズムの1つで、文字列の接尾辞に添字を付与し、辞書順に並べ替えを行った配列構造である。主に文字列探索、全文検索などに利用される。和訳せずに単に「サフィックス・アレイ」ともいわれる。

概要

長さ11の文字列 "abracadabra" を例に取って説明する。この文字列は "abracadabra", "bracadabra", "racadabra", というように "a" まで11の接尾辞を持つと考えられる。この11の接尾辞を1～11の添字（インデックス）を持った配列に順次格納し、それを辞書順に並べ替えすると以下のようになる。

a abra abracadabra acadabra adabra bra bracadabra cadabra dabra ra racadabra

元の文字列が利用可能な場合、各接尾辞はその開始位置のインデックスによって完全に特定できる。このインデックスを辞書順に並べたものが接尾辞配列となる。

インデックスが1基点の場合、"abracadabra"に対する接尾辞配列は {11,8,1,4,6,9,2,5,7,10,3} となる。配列先頭の "a" は11文字目の "a" であり、"abra" は8番目からの接尾辞である。

"abracadabra"に対して、12番目の接尾辞として空文字を考えることが出来る。しかし、これは常に先頭に配置されることになるので特に情報を持たないので、省略しても問題ない。

アルゴリズム

接尾辞配列を構築する最も容易な方法は、効率的な比較ソートアルゴリズムを利用することである。この場合、 $O(n \log n)$ 回の接尾辞の比較が必要になるが、接尾辞の比較は $O(n)$ の時間が必要となる。従って全体的な計算時間は $O(n^2 \log n)$ となる。

より精巧なアルゴリズムでは、部分ソートの結果の重複した比較を避けることで $O(n \log n)$ に改善できる。 $\Theta(n)$ アルゴリズムもいくつか知られているが、構造が複雑であること、大量のメモリを消費すること、非効率性(計算時間に大きい定数係数がかかる)などの問題から利用されることはまれである。

応用

ある文字列に対して構築された接尾辞配列により、ある文字列の全ての出現位置を高速に検索することができる。ある文字列の出現位置を求めることは、その文字列で始まっている接尾辞の位置を求めることに相当する。検索対象となる文字列は辞書順にソートされた接尾辞配列によって、効率的な二分探索アルゴリズムを用いて容易に見つけることができる。 $m$ を検索文字列の長さとすると、単純な実装では二分探索で $O(m \log n)$ の計算時間になる。

LCP(Longest Common Prefix)と呼ばれる、接尾辞間の最大共通文字列を計算しておけば、比較のやり直しを避けることができ、 $O(m + \log n)$ の時間で検索できる。

接尾辞配列のソートアルゴリズムを利用して Burrows-Wheeler transform (BWT)を行うこともできる。技術的に、BWTには接尾辞ではなく巡回シフトした文字列の辞書順のソートが要求される。このため、すべての文字列に番人としての文字"$"などを加えて巡回シフトを行うことで、接尾辞配列と同等の結果を得られる。

なお、接尾辞配列を利用した文字列検索ソフトウェアとして、山下達雄の「SUFARY」や、namazuの作者である高林哲の「Sary」が有名である。

歴史

接尾辞木と比べメモリ消費の少ない手法として、ジーン・マイヤーズとUdi Manberによって開発された。これにより圧縮された接尾辞配列とBWTベースの圧縮全文インデックスへの傾向が強まることとなった。

2000年に、圧縮全文インデックスとして、圧縮接尾辞配列やFM-Indexが登場する。

参考文献

Udi Manber and Gene Myers (1991). "Suffix arrays: a new method for on-line string searches". SIAM Journal on Computing, Volume 22, Issue 5 (October 1993), pp. 935-948.
Pang Ko and Srinivas Aluru (2003). "Space efficient linear time construction of suffix arrays." In Combinatorial Pattern Matching (CPM 03). LNCS 2676, Springer, 2003, pp 203-210.
Juha Kärkkäinen and Peter Sanders (2003). "Simple linear work suffix array construction." In Proc. 30th International Colloquium on Automata, Languages and Programming (ICALP '03). LNCS 2719, Springer, 2003, pp. 943-955.
Klaus-Bernd Schürmann and Jens Stoye (2005). "An incomplex algorithm for fast suffix array construction". In Proceedings of the 7th Workshop on Algorithm Engineering and Experiments and the 2nd Workshop on Analytic Algorithmics and Combinatorics (ALENEX/ANALCO 2005), 2005, pp. 77-85.