接尾辞配列
接尾辞配列（せつびじはいれつ）やサフィックス・アレイ（英: suffix array）とは、文字列の接尾辞（開始位置を異にし終端位置を元の文字列と同じくする部分文字列）の文字列中の開始位置を要素とする配列を、接尾辞に関して辞書順に並べ替えて得られる配列である。接尾辞木の配列版。主に文字列探索、全文検索などに利用される。1990年に Udi Manber と Gene Myers が発表した[1]。
| 接尾辞配列 | ||
|---|---|---|
| 種類 | 配列 | |
| 考案者 | Udi Manber, Gene Myers | |
| 発表年 | 1990年 | |
| 計算量（ビッグ・オー記法） | ||
| 平均 | 最悪 | |
| 空間計算量 | ||
| 構築の時間計算量 | ||
概要
編集長さ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番目の接尾辞として空文字を考えることができる。しかし、これは常に先頭に配置されることになるので特に情報を持たないので、省略しても問題ない。
構築法
編集接尾辞配列を構築する最も容易な方法は、効率的な比較ソートを利用することである。この場合、 回の接尾辞の比較が必要になるが、接尾辞の比較は の時間が必要となる。従って全体的な計算時間は となる。より精巧なアルゴリズムでは、部分ソートの結果の重複した比較を避けることで に改善できる。接尾辞木から変換する事で で変換する事も出来る。
2009年に Ge Nong らが SA-IS 法を発表した[2]。これにより計算量は 、メモリ使用量は （kは文字の種類数）となり、100行程度のC言語のプログラムで実装できる。Yuta Mori が論文発表と同時に SA-IS 法の実装を公開しており[3]、論文でも言及されている。
検索方法
編集接尾辞配列を使えば検索対象文字列の出現位置を高速に検索することができる。接尾辞配列においては、文字列が出現する位置を求めることはつまり、その文字列で始まっている接尾辞を求めることと同じである。接尾辞配列は辞書順にソートされているので、検索対象となる文字列の検索には、高速な二分探索アルゴリズムが利用できる。 を検索文字列の長さとすると、単純な実装では二分探索で の計算時間になる。
直前の接尾辞と、接尾辞の先頭から何文字か共通する文字がある場合、その最大文字数を最長共通接頭辞（LCP, Longest Common Prefix）と呼ぶが、あらかじめ求めておいたLCPにより無駄な比較を省き検索を高速化することができる。このとき、 の時間で検索できる。
ブロックソート
編集接尾辞配列のソートアルゴリズムを利用して ブロックソート (Burrows-Wheeler 変換, BWT) を行うこともできる。技術的に、ブロックソートには接尾辞ではなく巡回シフトした文字列の辞書順のソートが要求される。このため、すべての文字列に番人としての文字"$"などを加えて巡回シフトを行うことで、接尾辞配列と同等の結果を得られる。
歴史
編集接尾辞配列は、接尾辞木と比べメモリ消費の少ない手法として、ジーン・マイヤーズとウディ・マンバーによって開発された。これにより圧縮された接尾辞配列とBWTベースの圧縮全文インデックスへの傾向が強まることとなった。
2000年に、圧縮全文インデックスとして、圧縮接尾辞配列やFM-Indexが登場する。
実装
編集接尾辞配列を利用した文字列検索ソフトウェアとして、山下達雄の「SUFARY」（最終更新2002年）[4]や、namazuの作者である高林哲の「Sary」（最終更新2005年）[5]がある。
関連項目
編集- 接尾辞木 (Suffix tree)
参照
編集- ^ Manber, Udi; Myers, Gene (1990). Suffix arrays: a new method for on-line string searches. First Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 319–327.
- ^ Nong, Ge; Zhang, Sen; Chan, Wai Hong (2009). Linear Suffix Array Construction by Almost Pure Induced-Sorting. 2009 Data Compression Conference. p. 193. doi:10.1109/DCC.2009.42. ISBN 978-0-7695-3592-0。
- ^ sais
- ^ SUFARY 臨時復旧ページ
- ^ sary: Suffix Arrayのライブラリとツール
- 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.