接尾辞配列 接尾辞配列の概要

ウィキペディア

接尾辞配列

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/19 15:57 UTC 版)

接尾辞配列
種類	配列
考案者	Udi Manber, Gene Myers
発表年	1990年
計算量（ビッグ・オー記法）
	平均	最悪
空間計算量	${\mathcal {O}}(n)$	${\mathcal {O}}(n)$
構築の時間計算量	${\mathcal {O}}(n)$	${\mathcal {O}}(n)$

概要

長さ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)$に改善できる。接尾辞木から変換する事で $O(n)$ で変換する事も出来る。

2009年に Ge Nong らが SA-IS 法を発表した。これにより計算量は $O(n)$、メモリ使用量は $\max\{2n,4k\}$ （kは文字の種類数）となり、100行程度のC言語のプログラムで実装できる。Yuta Mori が論文発表と同時に SA-IS 法の実装を公開しており、論文でも言及されている。