SA-IS(Suffix Array - Induced Sorting)を実装した

  • 1
    Like
  • 0
    Comment
More than 1 year has passed since last update.

SA-ISとは

LMS-substringのrename

  • ちょっとだけ悩んだ。
  • 1回目の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.もあるらしいけど読んでない。