qzakuqのブックマーク - はてなブックマーク

SA-IS: SuffixArray線形構築: 訂正 - sileのブログ
以前に書いたSA-ISの記事(及びソースコード)には明確な間違いがあったので訂正しておく。間違い確か以前の記事では「入力文字列の各LMS部分文字列が互いにユニークなら、初めのinduced-sortを終えた段階でSuffixArrayが求まる」というようことを何箇所かで書いていたように思うが、これは間違い。理由は簡単。一回目のinduced-sortのステップ一の段階では各LMS部分文字列の先頭位置がバケツに挿入されることになるが、もしそれらに重複する文字があった場合、同じ文字(で始まるsuffix)同士のバケツ内での位置は、それらの挿入順に依存することになる。そして、この挿入を、最終的なソート順に合わせた順番で行うことは、この段階では不可能なため、ここで挿入されたSタイプの文字(が表すsuffix)同士が適切な順で並んでいる保証はない。また、induced-sortのステップ
qzakuq 2010/12/26
suffixarray
リンク
SA-IS: SuffixArray線形構築 - sileのブログ
『Linear Suffix Array Construction by Almost Pure Induced-Sorting』*1という論文を参考にして、Induced-Sortingを用いたSuffixArrayの線形構築アルゴリズム(SA-IS)をCommon Lispで実装した。以下、そのソースコードとメモ書き。線形構築汎用ソートアルゴリズムと今回実装したSA-ISアルゴリズムでのSuffixArray構築時間の簡単な比較。百文字〜一千万文字の文字数のテキストを入力として与えて、その構築時間を計測。百文字千文字一万文字十万文字百万文字一千万文字汎用ソート*20.000 sec0.002 sec0.023 sec0.358 sec5.604 sec94.196 sec SA-IS0.031 sec0.120 sec0.135 sec0.335 sec2.580 sec2
qzakuq 2010/12/26
suffixarray
リンク
SA-IS: C++版 - sileのブログ
以前にcommon lispで実装したSA-ISアルゴリズムを、C++でも実装したのでその計時結果など。ソースコード(github): sais-0.0.1 計時対象データには以下のサイズのテキストファイル群を使用。 $ ls sa.txt.* -rw-r--r-- 1 user user 10000 2010-12-23 19:25 sa.txt.10000 # 約10KB -rw-r--r-- 1 user user 100000 2010-12-23 19:25 sa.txt.100000 # 約100KB -rw-r--r-- 1 user user 1000000 2010-12-23 19:25 sa.txt.1000000 # 約1MB -rw-r--r-- 1 user user 10000000 2010-12-23 19:25 sa.txt.10000000 # 約
qzakuq 2010/12/26
suffixarray
リンク
1