SA-ISを気軽に実装するための話
SA-ISを実装しようなという話です。
SA-ISとは
接尾辞配列(Suffix Array, SA)を線形時間で構築するアルゴリズムです。
SAとは
接尾辞配列 - Wikipedia
わざわざ言うほどのことじゃないのでこれ読んでください。
問題
長さSの文字列が与えられるのでSAを構築せよ。
何も考えないでSAを求めるアルゴリズム
長さが1~Sの文字列があると思ってソートを行います。
しかし、文字列の大小比較は線形時間かかるので、ソートと合わせて計算量はです。
程度なら実装も楽だしこの方法でよいです。
頭のいいアルゴリズム(Manber&Myers algorithm)
蟻本に詳しいことは書いてあるので持っている人はそちらを参考にしてください。ダブリングというテクニックを使います。
簡単に言うと、先頭1文字でソートして、それを用いて先頭2文字でソートして、それを用いて先頭4文字でソートして・・というのを繰り返します。この繰り返す回数はであり、一回のソートに
かかるので計算量は
です*1。
程度なら多分大丈夫です。というか、多くの問題においてはこの方法で十分です。
超頭のいいアルゴリズム(SA-IS)
文字列をソートするのに線形時間しかかからないという頭のおかしいアルゴリズムです。有名なアルゴリズムなので解説記事がネット上にたくさん転がっていますが、僕がもっともわかりやすいと思ったのは以下の記事です。アルゴリズムを理解したいなら以下の記事を繰り返し読むといいと思います。
shogo82148.github.io
S-type, L-type, LMS, LMS-substring, induced sort, bucketなどの意味は上記のサイトを読んでください。アルゴリズムの内容も上記のサイトを読んでください（）。アルゴリズムの核（だと僕が思うの）は、LMSをbucketの下から*2いれてinduced sortを実行するとLMS-substringがソートされるということです。実際に手を動かしてみれば証明するのは簡単です。
SA-ISの実装の流れ（あくまで僕の実装）
アルゴリズムを理解しても実装の流れがつかみにくいということがあると思う（僕はそうだった）ので、僕の実装の流れを書きます。これはあくまで僕の実装なのでもっとよい実装はいくらでもあることに注意してください。
- char型だと後々扱いにくいのでint型に変換する。後で優先度最小のダミー値0を挿入したいので、それ以外の部分は1-indexedにする
- 数列と文字の種類数を受け取る関数用意する（以下関数内の処理）
- ダミー値を最後尾に挿入する
- 各数字のバケットの始まりと終わりを保持する
- 数列の各数字のS-type, L-typeを分類する
- 数列のLMSを求め、該当するバケットの下からLMSを挿入していく
- induced sortを実行する
- LMS-substringが昇順になるような順でLMSが出現するのでその順にLMS-substringに数値を割り当てる
- LMS-substringが一致していたら数値を同じにする必要があるのでそのチェック&更新を行う
- 元の文字列でのLMSの出現順に各LMS-substringに割り当てた数値を並べる
- 8で作った数列のSAを求めるため、この関数にその数列を投げる（再帰的）
- 9の返り値で得られたSAの逆順で該当するバケットの下からLMSを挿入していく
- induced sortを実行する
- 先頭にあるダミー値を削除する
- 得られた数列を返す
こうしてみるとどれも簡単なものばかりで楽そうなのですが、僕の場合は0-indexedと1-indexedが混ざったり、7の処理を抜かしていてバグらせまくったりしました。
おわりに
実はSA-ISを使う問題に実際に出会ったことはないのですが、イマドキの人はSA-ISは持っているものという認識が広まりつつあるので実装しました。こうして見ると言うほど複雑ではないので実装してみるといいと思います（hogehuga木のpiyoとかのほうが全然難しそう）。
一応僕の実装を載せておきますが、とりあえず線形時間でSAを求めたというだけで定数倍が非常に重いですし、無駄な処理も多いのであまり参考にしないほうがよいです（ただ、一応上記の方針の通りに実装しています）。ライブラリ化したいならvectorにこんな頻繁にpush_backしてはいけませんし、もっと洗練させたほうがいいです（僕は今はそのモチベーションがないのでとりあえずこれで）。
gist.github.com
