第5回 2019/5/16

• 講師：森下 真一

Suffix Array Induced Sorting

Suffix Array を線形時間で構築するアルゴリズム（略称：SA-IS）

Step1

定義：L/S type

i番目のsuffixが(i+1)番目のsuffixより辞書式順序で

• 小さい（S[i,n) < S[i+1, n)）とき、S-type
• 大きい（S[i,n) > S[i+1, n)）とき、L-type

なお、文字 "＄" は最小の文字であり、suffix "＄" をS-typeと定義する。 この時、以下が成り立つことは自明。

これから、各suffixのtypeを \(\mathrm{O}(n)\) 時間で決定することができる。

i=5	i=4	i=3

Step2

定義：LMS

S-type文字S[i]の１つ前の文字S[i-1]がL-typeなら、LMSとする。（S-type文字の塊の左端だから。）

Step3

Suffix Array を用意し、-1で初期化する。

Step4

頭文字が同じsuffixを固めたBucketsを作成。

idea

induce sortingの基本アイデア：既知の順番から、suffixの順番を誘導する。

有力な定理

Step5

LMSをソートする。

※あとでこのソートの説明を行う。ここでは、説明の流れ的にソートできたものとする。

Step6

SAを正順に走査して L-type のsuffixを埋めていく。 この時、S[(注目している番号)-1]がL-typeならば、相当するバケットの小さい順に入れていく。この作業が"induced"の由来。LMSを利用して順番を推測している。

頭文字が同じで、

• L-type：S-typeよりは小さい
• １つ右側が残りの中で最小

なので、この作業で正しい場所に入れられることがわかる。

Step 7

SAを逆順に走査して S-type のsuffixを埋めていく。 なお、この時もちろん最初に入れた(大小関係だけ決めて置いたLMSは更新する。)

この作業を同様に繰り返し、結果以下を得る。

Step5 LMS suffix のソートは？？

Step5で「LMSが正しくソートされて入れば全体も正しくソートされる」ことがわかった。 では、どのようにしてLMSをソートするのか？という話になるが、実はこの答えは「ソートしないでソートする」である。 以下で、詳しく見ていく。

SA-IS法の再帰

先ほどの Step6, Step7 を再帰的に行う。先に例を見せる。

Step4'

Step5'

ここでは、LMSの順序がわからないので、等号で結ぶ。

Step6'

SAを正順に走査して L-type のsuffixを埋めていく。 この時、等号の情報も随時受け継いでいく。

Step7'

SAを逆順に走査して S-type のsuffixを埋めていく。 なお、今回も、最初に入れた(大小関係だけ決めて置いたLMSは更新する。)

Recursion

ここまでの操作で、LMSのソートは完了していない。そこで、上で得た情報を元にLMS(正確にはLMS部分列)に順位を付与する。

step5 (Recursion)

step6 (Recursion)

SAを正順に走査して L-type のsuffixを埋めていく。終了時には以下のようになっている。

step7 (Recursion)

SAを逆順に走査して S-type のsuffixを埋めていく。

before	after

これで、LMSのソートが完了した！！

計算量

LMS部分列に順位を付与して生成した文字列は、長さが元の1/2以下になることが保証されている。（LMSの数は最大でも1/2） したがって、\(\mathrm{O}(n+n/2+n/4+...) = \mathrm{O}(2n)\) ということで、線形時間が保たれる。

参考論文

Two Efficient Algorithms for Linear Time Suffix Array Construction この論文の Appendix に C で実装したプログラムがある。

実装例

Python で実装したプログラムがここにおいてあります。