LCP(Longest Common Prefix)を用いたSuffix Arrayの検索

計算機科学

Suffix Arrayは「インデックスの構築」と「キーワードの検索」からなる。それぞれ構築には文字列のsortが、検索には文字列の二分探索が必要になる。
以前にCompressed Suffix Arrayのライブラリtsubomiを実装したときにはsortについてはマルチキー・クイックソート(multikey-quicksort)というアルゴリズムを用いた。一方で二分探索については特に工夫をしていなかった。
さすがにこのまま放っておくのは気が引けたのでSuffix Array論文を読みなおしてみたらLCP(Longest Common Prefix)を用いた二分探索の方法が書いてあった。シンプルだが賢い方法だったのでメモしておく。これはすごい(というか今まで読み飛ばしてたことのほうが問題ですね。はい)。


さて。まずLCP(Longest Common Prefix)とは何かと言うとその名の通り2つの文字列の先頭から数えた共通部分のこと。具体的には

lcp(apple, application) = appl
lcp(orange, open) = o

という感じ。このLCPの長さを使うことで二分探索をO(MlogN)からO(M+logN)の時間計算量で行うことができる(M:入力キーワード長、N:インデックスサイズ)。
具体的には二分探索時に任意の2つのSuffix間のLCPの長さを使う。これにはO(N^2)の空間計算量が必要。が、これは工夫を入れるとO(N)で保持することができる。
どうするかというと、辞書順で隣接する2つのSuffixについてだけLCPの長さを計算しておく。これならO(N)ですむ。そして任意のLCPの長さを求めるには

h: LCPの長さ

h(s[i], s[j]) = min{ h(s[k], s[k+1]); k in [i, j - 1] }

をすれば良い。つまり辞書順で2つのSuffixの間にある全ての「隣接したSuffix間のLCP長」で最小のものが2つのSuffixのLCP長になる(隣接SuffixについてはLCP長が事前に計算してあったことに注意)。この範囲内で最小の値を探す問題はRMQ(Range Minimum Query)と呼ばれるものでアリ本(プログラミングコンテストチャレンジブック)とかにも書いてある。論文ではinterval treeというのをつかってRMQを解いていたが他に効率のよい方法があるかもしれない。
何故範囲内の最小のLCP長が2つのSuffixのLCP長なのかは具体例を見るとわかりやすい。

Suffix       LCP長
append       3
application  1
around       2
arrange

LCP長(append, arrange) = 1

というわけで最小のLCP長が両端のLCP長に一致している。この理由を解説する。
Suffixが辞書順に並んでいるので例えばSuffixの先頭部分がappからaroに切り替わったら、もう再度appが出てくることは無い。ということはappendはapplicationと3文字一致しているので、appではじまるapplicationと1文字しか一致しないaroundが出た時点で、それ以降1文字以上appendと一致するSuffixは出てこない。このように上から順番に見ていくとLCP長が減ることはあっても増えることはない、というわけ。直感的な解説で恐縮だがいくつか事例を手で試せばわかると思う(丸投げ)。


さて、これで任意の2つのSuffix間のLCP長が計算できることがわかった。このLCP長を使って本来の目的である二分探索を行う方法を解説する。
二分探索ではあるSuffixの範囲(L,R)が与えられたときに、範囲の真ん中(M = (L+R)/2)のSuffixと入力キーワードとの大小関係を調べて小さければ次の範囲が(L,M)に、そうでないなら(M,R)になり探索は(L > R)となるかMの位置のSuffixが入力キーワードと一致するまで続く、というもの。これを単純に実装すると毎回文字列比較が発生して遅い。これを改善するのにLCP長を使う。
まず最初のMの位置のSuffixと入力キーワードを比較する。このとき同時に両者のLCP長も計算しておく。そして比較結果によって範囲が(L,M)か(M,R)かのどちらかに移る。
ここで(L,M)に移った場合を考える。先ほどの比較でLと入力キーワード間のLCP長h1はわかっている。そして任意のSuffix同士のLCP長h2も事前に計算してある。
ここで、このh1とh2の大小関係を見るだけで入力キーワードとMの位置のSuffixの大小関係がわかる(つまりナイーブな比較が不要)というのがこの手法のポイント。
まず(h1 < h2)の場合。これは以下のような状況

入力キーワード: arrange

Suffix
L: apple
   append
M: application
   arrange
R: arround

h1: LCP長(arrange, apple) = 1
h2: LCP長(apple, application) = 3

つまりキーワードとLの位置のSuffixが1文字しか一致していないのにLとMのSuffixが3文字一致していたら、この範囲には当然キーワードがないことがわかる。つまり次に探索すべき範囲は(M,R)となる。
次に(h1 > h2)の場合。これは以下のような状況

入力キーワード: apple

Suffix
L: apple
   append
M: application
   arrange
R: arround

h1: LCP長(append, apple) = 4
h2: LCP長(apple, application) = 3

つまりキーワードとLの位置のSuffixが4文字一致しているのにLとMのSuffixが3文字しか一致していなかったら、この範囲にキーワードがあるか、さもなくばそういうSuffixがそもそも存在しないかのどちらか(LCP長が減ったら増えることが無いのは前述の解説の通り)。つまり次に探索すべき範囲は(L,M)となる。
で最後に(h1 = h2)の場合。この場合は通常通り比較を行うのだが、先頭のh1文字分(あるいはh2文字分)はすでに一致していることがわかっているので比較はh1+1文字目からで良くなる。このためすでに比較済みの(キーワード中の)文字は再度比較されずに時間計算量がO(MlogN)からO(M+logN)になる、というわけ。
これは賢い。もっとはやく論文読めば良かった。


なおSuffix Array論文では構築には基数ソート(radix sort)ベースの手法を使っていてこれも賢い方法だったのだが余分なデータを一時的にもつ必要があったのでマルチキー・クイックソートのままで良いと思った。
また構築のアルゴリズムとしてはSA-ISというものもあり線形時間で構築できるということなのだが、構築に関しては速度面で不満はないのでまあいいやと思っている。

マルチキー・クイックソート(multikey-quicksort)で高速に文字列ソート - EchizenBlog-Zwei
SAIS(Suffix Array - Induced Sorting) - EchizenBlog-Zwei
CSAを使った全文検索ライブラリtsubomiを公開してみる - EchizenBlog-Zwei
Suffix arrays: A new method for　on-line string searches (U. Manber & G. Myers, 1989)