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
http://cl-www.msi.co.jp/articles/lisp-talk.html
