SA-ISとは
- SA-ISは接尾辞配列を文字列長の線形時間で求めるアルゴリズム。
- 元論文：Two Efficient Algorithms for Linear Time Suffix
Array Construction [G Nong, et.al.] - 以下個人的に悩んだところ。
LMS-substringのrename
- ちょっとだけ悩んだ。
- １回目のinduced sortingの後にLMS-substringがsortされていることを利用して辞書順で小さいLMS-substringから比較していけば良いだけだった。
- renameで得られた新しいアルファベットでLMS-substringがuniqueかどうかの判定ができる。
renameしたLMS-substringを格納する場所
- $n$ を文字列長、$l$ をLMS-substringの数とする。
- 上のrename処理が辞書順に見ていくので適当に格納すると出現順が崩れて再帰する際の文字列が得られない。配列をもう一つ用意すれば簡単だがメモリ的にうれしくない。
- うまくやるために、以下の性質を使う。
- $l$ は$\lfloor n/2 \rfloor$以下。
- LMS-characterの隣はLMS-characterにならない。
- LMS-substringの辞書順が求まったら作業用配列の先頭に辞書順情報だけ格納して、それ以外の値を初期化する。
- rename処理の中で、元の文字列での出現位置が$p$となるLMS-substringに対して、renameした値を作業用配列の($l$+$\lfloor p/2 \rfloor$)の位置に格納する。上記の性質から格納位置は被らないし溢れない。
- 配列の$l$ 以降で初期化されていない値は元の文字列の出現順にLMS-substringがrenameされた値となっているので、ここから新しい文字列を生成して再帰的にinduced sortする。
ソースコード
実行速度
- 上記のtest.cppに書いてあるLS(Larsson-Sadakane)もどきとの比較
- 条件：文字列長$10^7$、アルファベットサイズ$2$、g++ 4.4.7、i5-4440 3.10GHz
| 手法 | 実行時間 |
|---|---|
| SA-IS | 2.92 [s] |
| LS | 14.74 [s] |
まとめ
- 速いし、アルゴリズムも理解に苦しむ感じではないので良い。
- データの置き方とかで悩んだので省メモリコーディングの技術が必要。
その他
- 最初のアルファベットサイズ求めるのにsetとか使っているのでその内直す。
- メモリの使用量を減らしたver.もあるらしいけど読んでない。