SA-IS

Suffix Arrayを空間・時間計算量共に線形で構築出来るというアルゴリズムSA-ISを, 以前ふわっと読んだことはあったけれど真面目に読みなおしました. よく出来過ぎだと思う. 細かいところの理解が間違っていたら教えて下さい. ざっくりとした流れしか書きません. ちゃんとした証明とかは元論文を見てください. というかこんな記事よりiwiさんのブログとかがわかりやすいと思うけど自分で忘れないために書きました.

(元論文: Linear Suffix Array Construction by Almost Pure Induced-Sorting)

文字列の最後には最小の番兵を置いておく.

記号を色々定義しておくと,まず
Suf(S,i):=Sのi文字目以降のsuffix
Suf(S,i)がS-type...Suf(S,i)Suf(S,i+1)
Suf(S,i+1)とはSuf(S,i)の先頭を除いたものであることに注意(当たり前だけどはっきり意識した方がわかりやすいと思った)

LMS...Suf(S,i)がS-typeかつSuf(S,i-1)がL-type
LMS-substring...LMSから次のLMSまでの部分文字列(両端含む) また最後の番兵はそれだけでLMS-substringということにする

ここで,LMSたちのsuffix arrayが求まっていたら全体のsuffix arrayが計算出来ることがわかる(Induced-sorting)
まず,考えると出来上がったsuffix arrayでは(先頭の文字,type)でブロックに分けることが出来るのがわかる(L-typeがS-typeの前に来る)

とりあえずLMSたちをその小さい順にブロックに入れていく. LMSの順番だけが重要だとわかるので場所は確定出来なくてよい.
次に,SA[i]を小さい方から見ていって,SA[i]が埋まっていてSA[i]-1がL-typeならばS[SA[i]-1]のブロックの後ろにSA[i]-1を入れる.
というのもSA[i]-1がL-typeならばSA[i]はL-typeまたはLMSで,いずれの場合もSA[i-1]はSA[i]より大きく,またs < tの時'x'+s < 'x'+tであるから小さい方からやるとうまくいく. これでL-typeのsuffix arrayが求まる.
次に,S-typeを埋める.これは今度はSA[i]を大きい方から見てほぼ同じことをする.LMSを入れた場所は上書きしていいことに注意.

以上より,LMSがソート出来ていればsuffix arrayが求まる.

次に,上の手順を行うためにLMSたちをソートする方法を考える.
これは上で定義したLMS-substringたちのランクを文字として扱って(LMS-substringを比較する時には文字にtypeの属性も含める), suffix arrayを求めれば(ここで再帰が呼ばれる)出来ることがわかる.
よってLMS-substringの順位付けを考える. ここにもInduced-sortingが使えるというのがSA-ISのすごいところらしい.

実はこれは,LMSたちの先頭でとりあえずバケットに分けて(同じバケットの中では開始位置が後ろのやつから入れる) induced-sortingすればよい.
これはその文字列のk文字目までソートしてあるとk+1文字目までの情報が...という感じになるのでLMS-substringたちが正しい順番で並んでくれるため
は?という感じだがよく考えると上手く出来ている
sortされたLMS-substringたちのrenameは,まあLMS-substringの和はN未満なので愚直にやってよい(1つ前と同じかどうか調べる)

おしまい

参考:
SA-IS - (iwi) { 反省します - TopCoder部
SA-IS - Shogo Computing Laboratory