Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

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

More than 5 years have 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.もあるらしいけど読んでない。
nel215
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away