Suffix Array

これは「データ構造とアルゴリズム Advent Calendar 2018」9日目の記事です．

##はじめに

Suffix array¹ はよく知られたデータ構造のひとつです．1990年に提案²されて以来，その使われ方は多岐にわたります．本記事では，この suffix array の基本事項として，

• suffix array とは何か
• suffix array を全文索引として用いる方法

を紹介したいと思います．

##パターンマッチングと全文索引
パターンマッチング とは，文字列 $T$ から，パターンと呼ばれる文字列 $P$ を探す問題です．たとえば，

$T =$ 麒麟鼬蝙蝠駱駝蝦蟇鼈樹懶鼠膃肭臍羆狒狒鰐麒麟猩猩鼠鼠鼠鼠鼠蟒蛇鼈鼬羆蜥蜴駱駝羆麒麟鼈鼬狒狒狒狒羆蝙蝠膃肭臍麒麟蝙蝠鼬蜥蜴鼬狒狒蝮樹懶鼬羆蝮膃肭臍麒麟羆駱駝蝙蝠蟒蛇狒狒蝙蝠樹懶鼈蜥蜴駱駝羆鼬羆樹懶犀鰐蝙蝠鼠狒狒蝦蟇鼬蜥蜴鼠蝮蝦蟇蜥蜴龍麒麟駱駝犀鼠蝦蟇猩猩鼈蝙蝠鰐蝮蜥蜴魑魅魍魎

から，$P =$ 膃肭臍 を探すような問題は，パターンマッチングです．膃肭臍はオットセイと読みます．
このパターンマッチング問題には，3通りの回答方法があります：

1. $T$ 中に $P$ が出現する/しないを答える
2. $T$ 中に $P$ が何回出現するかを答える
3. $T$ 中の $P$ が出現する位置をすべて答える

下に行くほど，より高度な回答になります．上の例で見ると，

1. 出現する
2. 3回
3. 12文字目，49文字目，68文字目（先頭は 0文字目とする）

となります．

パターンマッチングを解くには，大きく分けて２通りの方法があります．ひとつは，パターンマッチングをしたくなったら，その度に文字列 $T$ を先頭から調べ，パターン $P$ が出現していないか探索する方法です（逐次走査型）．この方法でパターンマッチングをするアルゴリズムはいにしえの時代から盛んに研究されており，ある調査報告によれば，これまでに実に120種類以上ものアルゴリズムが提案されているそうです．
もうひとつは，あらかじめ文字列 $T$ に対してその索引として使えるようなデータ構造を作っておき，パターンマッチングをしたくなったら，その索引からパターン $P$ を検索する方法です（索引構築型）．今回扱うのはこちら側の話です．
逐次走査型では，パターンマッチングの度に $T$ を先頭から末尾にかけて調べていく時間が原理的にどうしても必要になりますが，索引構築型では，一度索引を作ってしまえば効率よくパターンを探索することができ，高速に検索できるという利点があります．一方で，索引となるデータ構造を構築・保持するための時間やメモリが必要である，文字列 $T$ があとから編集されるとデータ構造を作り直さなければならない，などといったデメリットもあります．どちらにも長所・短所がありますが，$T$ が編集されることが少なく，パターンマッチングの機会が多いような状況では，索引構築型は非常に有用です．
全文索引 は，対象となる文字列について，その中に現れるすべての部分文字列（厳密な定義は後述）を検索できるような索引です．パターンマッチングに用いる索引は全文索引で，suffix array はこの全文索引として利用できます³．

尚，上で用いた「逐次走査型」「索引構築型」という用語は，説明のためにいまここで用意した造語であり，特に業界一般に知られたテクニカルタームというわけではありません（通じるとは思いますが……）．

##Suffix array
###Suffix，Prefix，Substring

長さ $n$ の文字列 $T$ について，その先頭 $x$ 文字（$0 \le x \le n - 1$）を削った文字列を，$T$ の **suffix（接尾辞）**といいます．反対に，$T$ の末尾 $x$ 文字（$0 \le x \le n - 1$）を削った文字列を，$T$ の **prefix（接頭辞）**といいます．また，$T$ の先頭を $x$ 文字，末尾を $y$ 文字（$0 \le x,~ 0 \le y,~ 0 \le x+y \le n-1$）削った文字列を $T$ の **substring（部分文字列）**といいます．

【例】
$T =$ banana について，そのすべての suffix を書き出してみると，
　　banana，anana，nana，ana，na，a
となります．一方 prefix は，
　　banana，banan，bana，ban，ba，b
となります．Substring は，
　　banana，banan，anana，bana，anan，nana，ban，ana，nan，ba，an，na，b，a，n
です．

以降 suffix に関して，$T$ の $i$ 文字目からはじまる suffix（これは先頭から $i$ 文字削ってできる suffix です）のことを「 $i$ 番目の suffix 」と呼び，$i$ をその suffix の開始位置と呼びます．$T$ は 0文字目からはじまるとします．たとえば，ana は banana の 3番目の suffix，banana は banana の 0番目の suffix です．

###Suffix array

Suffix array¹ は，文字列のすべての suffix を辞書順⁴ でソートし，その開始位置を保持した配列です．

【例】
$T =$ abracadabra の suffix array を作ってみます．$T$ のすべての suffix とその開始位置は，

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

です．これらを辞書順でソートすると，

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

となります．この順で開始位置を保持すればよいので，suffix array は [10, 7, 0, 3, 5, 8, 1, 4, 6, 9, 2] になります．

Suffix array を作るには suffix をソートしなければなりません．そのため，たとえばクイックソートで作ろうとすると，文字列長 $n$ に対して平均 $O(n^2 \log n)$ 時間かかってしまいます⁵．しかしながら，世の中にはこの suffix array を $O(n)$ 時間で構築するアルゴリズムがいくつか存在します⁶⁷⁸⁹¹⁰．いずれも簡単ではないのでここでは説明しませんが，このうちのひとつである SA-IS⁹ については「データ構造とアルゴリズム Advent Calendar 2018」13日目の記事として紹介したいと思います（書きました）．

##Suffix array でパターンマッチング

Suffix を利用した全文索引について考えるにあたって，はじめにおさえておきたい重要な基本原理があります．それは，「文字列 $T$ 中に出現する部分文字列は，その出現位置を開始位置とする $T$ の suffix の prefix である」ということです．たとえば，br は $T =$ abracadabra 中の 1文字目と 8文字目を出現位置とする部分文字列ですが，これは $T$ の 1番目の suffix である bracadabra の prefix，および 8番目の suffix である bra の prefix です．あまりにも当然ですね．しかしこの当然の観察によって，いまパターンマッチングは「パターン $P$ を prefix としてもつような，$T$ の suffix を探す」問題と見ることができるようになりました．
ところで，suffix array は文字列 $T$ のすべての suffix をソートし，その開始位置を保持しているのでした．したがって，文字列 $T$ の長さ（$=$ suffix array のサイズ）を $n$，パターン $P$ の長さを $m$ とすると，先頭 $m$ 文字が $P$ に一致するような suffix は二分探索を用いて $O(m \log n)$ 時間で求めることができます．求めた suffix の開始位置が，すなわち探していたパターンの文字列中における出現位置です．
パターンマッチングの説明をしたときに，パターンマッチングには 3通りの回答方法があると述べました．Suffix array を使ったパターンマッチングでは，最も高度な回答である「出現する位置をすべて答える」が得られます．
逐次走査型によるパターンマッチングでは，文字列 $T$ を先頭から末尾まで走査するという性質上，パターンの検索に $O(n)$ 程度の時間が必要になります¹¹．それに比べると，suffix array は $O(m\log n)$ 時間でパターンの検索ができるので，たしかに高速になっています．うれしいです．ここでは扱いませんが，LCP というデータ構造を使ってさらに高速に検索を行う方法もあります¹²．

##おわりに

今日は suffix array の基本的な事柄を紹介してみました．
この記事の要点は以下の通りです．

• suffix array は，文字列のすべての suffix を辞書順でソートし，その開始位置を保持した配列である
• suffix array は全文索引として利用でき，文字列長 $n$，パターン長 $m$ に対して，$O(m \log n)$ 時間でパターンマッチングができる

お疲れさまでした．

1. Udi Manber, Eugene W. Myers: Suffix Arrays: A New Method for On-Line String Searches. SIAM J. Comput. 22(5): 935-948 (1993) ↩ ↩²

2. Udi Manber, Gene Myers: Suffix Arrays: A New Method for On-Line String Searches. SODA 1990: 319-327 ↩

3. Suffix array 以外の全文索引として使えるデータ構造については，たとえば昨年の「文字列アルゴリズム Advent Calendar 2017」 の記事「Compact Directed Acyclic Word Graphを定義する」などが参考になります． ↩

4. 2つの文字列 $T = t_0t_1...t_n$ と $S=s_0s_1...s_m$（$t, s \in \Sigma $，$\Sigma$ は順序付きアルファベット）について，$T$ が $S$ より辞書順で小さいとは，次の (a) (b) のいずれかが成り立つことを言います：(a) ある整数 $i$（ $0 \le i \le \min (n, m)$ ）について，$0 \le j \le i-1$ である任意の整数 $j$ に関して $t_j = s_j$ が成り立つ，かつ，$t_i < s_i$ ．(b) 任意の整数 $i$（ $0 \le i \le \min (n, m)$ ）について $t_i < s_i$ が成り立つ，かつ，$n < m$ ． ↩

5. 文字列の比較は 1 文字ずつ行われます．suffix の長さは $O(n)$ なので 1 度の比較に $O(n)$ 時間かかり，クイックソートの平均 $O(n \log n)$ とあわせて $O(n^2 \log n)$ 時間です． ↩

6. Dong Kyue Kim, Jeong Seop Sim, Heejin Park, Kunsoo Park: Constructing suffix arrays in linear time. J. Discrete Algorithms 3(2-4): 126-142 (2005) ↩

7. Pang Ko, Srinivas Aluru: Space efficient linear time construction of suffix arrays. J. Discrete Algorithms, 3(2-4), 143-156, (2005) ↩

8. Juha Kärkkäinen, Peter Sanders, Stefan Burkhardt: Linear work suffix array construction. J. ACM 53(6): 918-936 (2006) ↩

9. Ge Nong, Sen Zhang, Wai Hong Chan: Linear Suffix Array Construction by Almost Pure Induced-Sorting. DCC 2009: 193-202 ↩ ↩²

10. Uwe Baier: Linear-time Suffix Sorting - A New Approach for Suffix Array Construction. CPM 2016: 23:1-23:12 ↩

11. もちろんアルゴリズムによって異なります．たとえば，有名な KMP アルゴリズムでは $O(n+m)$ 時間必要です． ↩

12. これについては，わかりやすい解説記事として「LCP(Longest Common Prefix)を用いたSuffix Arrayの検索」などがあります． ↩