接尾辞配列のソースを表示

{| class="infobox" style="width: 22em"
! colspan="3" style="font-size: 125%; text-align: center;" | 接尾辞配列
|-
! 種類
| colspan="2" | [[配列]]
|-
! 考案者
{{!}} colspan="2" {{!}} Udi Manber, Gene Myers
|-
! 発表年
| colspan="2" | [[1990年]]
|-
! colspan="3" style="background-color: #ddddff; text-align: center;" | [[計算複雑性理論|計算量]]（[[ランダウの記号|ビッグ・オー記法]]）
|-
|
| 平均
| 最悪
|-
! 空間計算量
| <math>\mathcal{O}(n)</math>
| <math>\mathcal{O}(n)</math>
|-
! 構築の時間計算量
| <math>\mathcal{O}(n)</math>
| <math>\mathcal{O}(n)</math>
|}

'''接尾辞配列'''（せつびじはいれつ）や'''サフィックス・アレイ'''（{{lang-en-short|suffix array}}）とは、文字列の[[接尾辞]]（開始位置を異にし終端位置を元の文字列と同じくする部分文字列）の文字列中の開始位置を要素とする配列を、接尾辞に関して[[辞書順]]に並べ替えて得られる[[配列]]である。[[接尾辞木]]の配列版。主に[[文字列探索]]、[[全文検索]]などに利用される。1990年に Udi Manber と Gene Myers が発表した<ref>{{cite conference
 | title = Suffix arrays: a new method for on-line string searches
 | year = 1990
 | conference = First Annual ACM-SIAM Symposium on Discrete Algorithms
 | pages = 319–327
 | url = http://dl.acm.org/citation.cfm?id=320176.320218
 | last1 = Manber	 
 | first1 =  Udi
 | last2 = Myers	 
 | first2 =  Gene
}}</ref>。

== 概要 ==
長さ11の文字列
{| class="wikitable" border="1"
|-
!  1
!  2
!  3
!  4
!  5
!  6
!  7
!  8
!  9
! 10
! 11
|- align=center
| a
| b
| r
| a
| c
| a
| d
| a
| b
| r
| a
|}
を例に取って説明する。先頭から一文字ずつ削ってみればわかるように、この文字列は "abracadabra", "bracadabra", "racadabra", ……, "ra", "a" という11の接尾辞を持つと考えられる。この11の接尾辞を、それぞれの開始位置(1～11)とともに配列に順次格納し、接尾辞について辞書順に並べ替えると以下のようになる。表中の最長共通接頭辞（LCP）は、直前の接尾辞と、接尾辞の先頭から何文字か共通する文字がある場合の最大文字数。

{| class="wikitable" border="1"
|-
! 開始位置
! 接尾辞
! 最長共通接頭辞（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番目の接尾辞として空文字を考えることができる。しかし、これは常に先頭に配置されることになるので特に情報を持たないので、省略しても問題ない。

== 構築法 ==
接尾辞配列を構築する最も容易な方法は、効率的な比較[[ソート]]を利用することである。この場合、<math>O(n \log n)</math>回の接尾辞の比較が必要になるが、接尾辞の比較は <math>O(n)</math>の時間が必要となる。従って全体的な計算時間は <math>O(n^2 \log n)</math>となる。より精巧なアルゴリズムでは、部分ソートの結果の重複した比較を避けることで <math>O(n \log n)</math>に改善できる。[[接尾辞木]]から変換する事で <math>O(n)</math> で変換する事も出来る。

2009年に Ge Nong らが SA-IS 法を発表した<ref>{{cite conference
 | doi = 10.1109/DCC.2009.42
 |title=Linear Suffix Array Construction by Almost Pure Induced-Sorting
 |conference=2009 Data Compression Conference
 |year=2009
 |last1=Nong
 |first1=Ge
 |last2=Zhang
 |first2=Sen
 |last3=Chan
 |first3=Wai Hong
 |isbn=978-0-7695-3592-0
 |pages=193
}}</ref>。これにより計算量は <math>O(n)</math>、メモリ使用量は <math>\max\{2n, 4k\}</math> （kは文字の種類数）となり、100行程度のC言語のプログラムで実装できる。Yuta Mori が論文発表と同時に SA-IS 法の実装を公開しており<ref>[https://sites.google.com/site/yuta256/sais sais]</ref>、論文でも言及されている。

== 検索方法 ==
接尾辞配列を使えば検索対象文字列の出現位置を高速に検索することができる。接尾辞配列においては、文字列が出現する位置を求めることはつまり、その文字列で始まっている接尾辞を求めることと同じである。接尾辞配列は辞書順にソートされているので、検索対象となる文字列の検索には、高速な[[二分探索]]アルゴリズムが利用できる。<math>m</math>を検索文字列の長さとすると、単純な実装では二分探索で <math>O(m \log n)</math>の計算時間になる。

直前の接尾辞と、接尾辞の先頭から何文字か共通する文字がある場合、その最大文字数を最長共通接頭辞（LCP, Longest Common Prefix）と呼ぶが、あらかじめ求めておいたLCPにより無駄な比較を省き検索を高速化することができる。このとき、<math>O(m + \log n)</math> の時間で検索できる。

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

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

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

== 実装 ==
接尾辞配列を利用した文字列検索ソフトウェアとして、山下達雄の「SUFARY」（最終更新2002年）<ref>[http://nais.to/~yto/tools/sufary/ SUFARY 臨時復旧ページ]</ref>や、[[namazu]]の作者である高林哲の「Sary」（最終更新2005年）<ref>[https://sary.sourceforge.net/ sary: Suffix Arrayのライブラリとツール]</ref>がある。

== 関連項目 ==
* [[接尾辞木]] (Suffix tree)

== 参照 ==
{{reflist}}
* 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.

{{データ構造}}

{{DEFAULTSORT:せつひしはいれつ}}
[[Category:検索]]
[[Category:文字列データ構造]]
[[Category:アルゴリズム]]
[[Category:検索アルゴリズム]]