週末自己啓発！アルゴリズムの勉強。趣味の世界。

taku-ku 氏に教えてもらった論文。線形時間で Suffix Array を作る話。
Suffix Tree 方式だと O(n) でできるのだがこれは違うやり方。

Juha K¨arkk¨ainen and Peter Sanders:
"Simple Linear Work Suffix Array Construction",
ICALP 2003, LNCS 2719, pp. 943-955, 2003.
<http://www.cs.helsinki.fi/u/tpkarkka/publications/icalp03.pdf>

Abstract. [...]
1. recursively sort suffixes beginning at positions i mod 3 != 0.
2. sort the remaining suffixes using the information obtained in
step one.
3. merge the two sorted sequences obtained in steps one and two.

Step 1: 3 で割り切れない位置(mod 3≠0)から始まる文字列のそれぞれの
先頭 3 文字(triple)にlexicographic namesを付与する。
これには基数ソートを使う。ソート後、先頭からlexicographic namesを
1,2,3,...と付与する。同じtripleには同じname。
もし、全てのtripleがユニークならばソートは完了。
そうでなければ、mod 3 = 1 の triple 列と mod 3 = 2 の triple 列を
連結した配列に対して、再帰的に Step 1 を行う。

Step 2: 3 で割り切れる位置(i: i mod 3 = 0)から始まるsuffixでsuffix
arrayを作る。ソートは最初の1文字 s[i] とそれに続く S_{i+1}
(s[i+1,i+2,...]) で行うのだが、 後者は Step 1 ですでにソートされて
るので楽々。

Step 3: 上記 2 つのsuffix arrayをマージして最終的なsuffix arrayを
作る。マージの際の文字列比較：
i(i mod 3 = 0), j(j mod 3 = 1) のときは、
s[i]+S_{i+1} と s[j]+S_{j+1} を比較するわけだが、
S_{i+1} と S_{j+1} は Step 2 ですでにソートされているので楽々。
i(i mod 3 = 0), j(j mod 3 = 2) のときは、
s[i]+s[i+1]+S_{i+2} と s[j]+s[i+1]+S_{j+2} を比較するので同じく楽々。

- なぜ、線形時間かというと、基数ソート(radix sort)が線形だから。

- 論文の後ろに C++ のサンプルコードがついている。
  - テキストサイズのオーダーの配列をいくつか内部で使ってる。
    メモリ使用効率に問題がありそう。
  - つまり、実メモリを越えるサイズ（実際はそこまでいかなくても）の
    テキストを対象にする場合、かなーり嬉しくないかも。

- lexicographic namesの付与がネック。
  - 基数ソートはバケツデータ構造がいる。このあたりは実装レベルで
    かなり時間がかかりそう。
  - つか、日本語文字だとやばいんじゃない？

- 解説資料を発見：
  東大の情報生命科学基礎・演習の資料「Suffix Trees and Arrays」
  <http://www.hgc.jp/~tshibuya/classes/shibuya20040629.pdf>

- O(n) 時間で作る話があるといつも着目するのは「単語、行単位の
  ソートはどうするか」という点。SUFARY だとよく使うので。
  しかし、この手法を使うと文字単位以外では Step 2, 3 のうまみがな
  い。単語や行のID化はしたくない。

- 結局、DNA配列には適すけど...といった感じか。