SA-IS

これは「データ構造とアルゴリズム Advent Calendar 2018」13日目の記事です．

はじめに

Suffix array¹ は便利なデータ構造です．Suffix array の基本事項については，4日前に紹介したので参照していただきたいです．が，忙しい人のためにここで復習すると，

• suffix array とは，文字列のすべての suffix を辞書順でソートし，その開始位置を保持した配列である
• suffix array は全文索引として使える

という内容でした．

Suffix array を作るには suffix をソートしなければなりません．そのため，たとえばクイックソートで作ろうとすると，文字列長 $n$ に対して平均 $O(n^2 \log n)$ 時間かかってしまいます²．しかしながら，世の中にはこの suffix array を $O(n)$ 時間で構築するアルゴリズムがいくつか存在します³⁴⁵⁶⁷．今回はこのうちのひとつである SA-IS⁶ を紹介したいと思います．

SA-IS

アルゴリズムの説明

わかりやすさを求めた結果，図が大量に必要になったため，スライドにしました．下のリンクからお願いします．
https://speakerdeck.com/flare/sa-is
決して過去のスライドを使い回して手抜きをしようとしたわけではありません．決して．

実験結果

せっかくなので，SA-IS を実装してみました（実装はここで公開しています）．Rust で実装したので，ついでに Rust の標準のソートを使った suffix array 構築も実装し，速度を比較しました．

	SA-IS (Rust)$^{①}$	sort (Rust)$^{①}$	SA-IS (C/C++)$^{②}$
alice29 (149KB)8	0.087 sec	0.041 sec	- sec
world192 (2.4MB)8	2.568 sec	1.260 sec	1.3 sec
bible (3.9MB)8	4.774 sec	2.146 sec	2.7 sec
E.coli (4.5MB)8	5.261 sec	2.749 sec	2.8 sec

① Rust (ver 1.30.1) で実装，実験環境は Intel® CoreTM i5-6267U CPU at 2.90GHz, 8GB RAM, Arch Linux (Kernel 4.18.16)．
② 論文⁶中の実験結果より引用（環境は Linux (Sabayon Linux distribution) with AMD Athlon(tm) 64x2 Dual Core Processor 4200+ 2.20GHz and 2.00GB RAM，実装は C/C++，g++ with the -O3 option でコンパイル，とある）．

最左列がデータセットとサイズ，2列目が SA-IS，3列目が Rust の標準のソートです．あれ？　標準のソートのほうが速いですね……．自分の実装がヘタクソなせいかもしれないと思い，SA-IS を提案した論文⁶から実験結果を引用して隣に並べてみました（4列目）．あれ？　Rust の標準のソートのほうが速いですね……．もちろん実験環境も実装言語も違うので一概に比較はできませんが……．
Rust のドキュメントにはこの標準のソートの説明として，

The current algorithm is an adaptive, iterative merge sort inspired by timsort.

と書いてあり，最悪時 $O(n \log n)$ 時間かかるとあります．今回は毎回 suffix 間の比較が発生するので，全体では最悪時 $O(n^2 \log n)$ 時間かかります．え〜〜ほんとに？　SA-IS，線形時間なんだけどな〜〜？

おわりに

今日は SA-IS を紹介してみました．
この記事の要点は以下の通りです．

• SA-IS という suffix array を線形時間で構築するアルゴリズムが存在する．

お疲れさまでした．

---

追記
@kgoto 氏から twitter で，

共通prefixが短ければ比較にO(n)かかることがないからそのせいかも。
全部aとか同じファイルを連結させたデータでやると標準ソートに勝てるかもしれない。

というコメントをいただき，たしかにそんな気がしたので追実験してみました．文字 a を100000個並べたテキストデータに対して，suffix array を作ってみます．結果は，SA-IS が 0.038sec，Rust の標準のソートが 2.335 sec となり，無事線形時間構築が勝利を収めました．よかったです．
とはいえ，なんかこう作為的なデータを用意しないと勝てないのはちょっとすっきりしないでもないですが……．

1. Udi Manber, Eugene W. Myers: Suffix Arrays: A New Method for On-Line String Searches. SIAM J. Comput. 22(5): 935-948 (1993) ↩

2. 文字列の比較は 1 文字ずつ行われます．suffix の長さは $O(n)$ なので 1 度の比較に $O(n)$ 時間かかり，クイックソートの平均 $O(n \log n)$ とあわせて $O(n^2 \log n)$ 時間です． ↩

3. Dong Kyue Kim, Jeong Seop Sim, Heejin Park, Kunsoo Park: Constructing suffix arrays in linear time. J. Discrete Algorithms 3(2-4): 126-142 (2005) ↩

4. Pang Ko, Srinivas Aluru: Space efficient linear time construction of suffix arrays. J. Discrete Algorithms, 3(2-4), 143-156, (2005) ↩

5. Juha Kärkkäinen, Peter Sanders, Stefan Burkhardt: Linear work suffix array construction. J. ACM 53(6): 918-936 (2006) ↩

6. Ge Nong, Sen Zhang, Wai Hong Chan: Linear Suffix Array Construction by Almost Pure Induced-Sorting. DCC 2009: 193-202 ↩ ↩² ↩³ ↩⁴

7. Uwe Baier: Linear-time Suffix Sorting - A New Approach for Suffix Array Construction. CPM 2016: 23:1-23:12 ↩

8. http://corpus.canterbury.ac.nz/descriptions//#large より． ↩ ↩² ↩³ ↩⁴