接尾辞配列

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

接尾辞配列(せつびじはいれつ、Suffix Array)とは、文字列の接尾辞(開始位置を異にし終端位置を元の文字列と同じくする部分文字列)の文字列中の開始位置を要素とする配列を、接尾辞に関して辞書順に並べ替えて得られる配列である。主に文字列探索全文検索などに利用される。和訳せずに単に「サフィックス・アレイ」とも呼ばれる。

概要[編集]

長さ11の文字列

1 2 3 4 5 6 7 8 9 10 11
a b r a c a d a b r a

を例に取って説明する。先頭から一文字ずつ削ってみればわかるように、この文字列は "abracadabra", "bracadabra", "racadabra", ……, "ra", "a" という11の接尾辞を持つと考えられる。この11の接尾辞を、それぞれの開始位置(1~11)とともに配列に順次格納し、接尾辞について辞書順に並べ替えると以下のようになる。(なお、表中のLCPについては後述する。)

開始位置 接尾辞 LCP
11 a 0
8 abra 1
1 abracadabra 4
4 acadabra 1
6 adabra 1
9 bra 0
2 bracadabra 3
5 cadabra 0
7 dabra 0
10 ra 0
3 racadabra 2

元の文字列があれば、接尾辞の開始位置を指定することですべての接尾辞を余すことなく得ることができる。この接尾辞を辞書順に並べたときの開始位置の配列が接尾辞配列となる。

"abracadabra"に対する接尾辞配列は、表のように、 {11,8,1,4,6,9,2,5,7,10,3} となる。接尾辞 "a" の開始位置は11で、接尾辞 "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)と呼ぶが、あらかじめ求めておいたLCPにより無駄な比較を省き検索を高速化することができる。このとき、O(m + \log n) の時間で検索できる。

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

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

歴史[編集]

接尾辞配列は、接尾辞木と比べメモリ消費の少ない手法として、ジーン・マイヤーズウディ・マンバーによって開発された。これにより圧縮された接尾辞配列と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.

外部リンク[編集]