| 1 | Introduction for Suffix Array |
| 2 | Larsson Sadakane Method |
| 3 | Two-Stage Sort（二段階ソート） |
| 4 | Copy Method |
| 5 | Deep Shallow Sorting |
Suffix Arrayの概念
まず、これからの話をスムーズにするために様々な定義をします。
ここでは、「abracadabra」というデータを例にして説明します。
まず、入力データにインデクスを次のように順番にふります。
| a | b | r | a | c | a | d | a | b | r | a |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Suffix（接頭辞） とは、データにおける部分列のことです。
Suffix : Si を インデクスi から始まる接頭辞とします。すると上のデータにおける各Suffixは次の通りになります。
| S0 | abracadabra |
| S1 | bracadabra |
| S2 | racadabra |
| S3 | acadabra |
| S4 | cadabra |
| S5 | adabra |
| S6 | dabra |
| S7 | abra |
| S8 | bra |
| S9 | ra |
| S10 | a |
次に、各Suffixにおける大小関係を定義します。この大小関係は辞書式順序です。辞書式順序とは、辞書に並んでいる通りの順番であり、簡単に言えば、
(1)両Suffixを頭（左）から順番に一文字ずつ比較していき、初めて違うところで、文字の大小関係で比較を行う
(2)もし、二つを比較していき、片方のSuffixが終わりに達してしまったら、そちらの方が小さいと定義する。
例えば、(1)は上の例でいえば、 S5 と S7を比較するとすると
S5 adabra
S7 abra
一文字目は両方ともaで、同じなので二文字目（赤い部分）を比較すると、dとbであり、文字の大小関係で d > b なので
S7 < S5
という大小関係がつきます。
(2)については、S0 と S7を比較すると
S0 abracadabra
S7 abra
で、頭から4文字は同じであり、S7はデータの最後に達しました。このとき S7 < S0とできます。
この大小関係で、全てのSuffix をソートしたもの、それがSuffix Arrayです。上の例でいえば、
| S10 | a |
| S7 | abra |
| S0 | abracadabra |
| S3 | acadabra |
| S5 | adabra |
| S8 | bra |
| S1 | bracadabra |
| S4 | cadabra |
| S6 | dabra |
| S9 | ra |
| S2 | racadabra |
とソートできました。これがSuffix Arrayです。この情報を全て持っておくにはいかないので、Suffix Arrayの順番をint型配列A[]に保存しておきます。
上の例でいえば、上から順に S10 S7 S0 S3 ・・ S9 S2 なので A[0] = 10 A[1] = 7 A[2] = 0・・A [9] = 9 A[10] = 2
となります。このA[]を求めることが Suffix Arrayを構築することといえます。
さて、辞書式順序ですが、実装の時に二つのSuffixを比較するとき、いちいち長さをチェックしていたら大変です。そこで入力文字列の最後に、出現するどの文字よりも小さい文字を加えるという工夫を行います。この文字を便宜上$とします。
すると、調べるデータは「abracadabra$」となり各Suffixは次の通りになります。
| S0 | abracadabra$ |
| S1 | bracadabra$ |
| S2 | racadabra$ |
| S3 | acadabra$ |
| S4 | cadabra$ |
| S5 | adabra$ |
| S6 | dabra$ |
| S7 | abra$ |
| S8 | bra$ |
| S9 | ra$ |
| S10 | a$ |
| S11 | $ |
すると、$がどの文字よりも小さいという定義から、必ず比較が最後に達する前に終了することがわかります。例えば先ほど最後まで比較が達した例でも
S0 abracadabra$
S7 abra$
赤の部分で比較が終わることがわかります。$が番人の役割を果たしていると思えばいいでしょう。また、この$を入れてもSuffix間の順序は変わることがありません。$がどの文字よりも小さいということなので、上のS3とS7の比較においてもS7 < S3は変わりません。
構築されたSuffix Arrayは次の通りになります。
| S11 | $ |
| S10 | a$ |
| S7 | abra$ |
| S0 | abracadabra$ |
| S3 | acadabra$ |
| S5 | adabra$ |
| S8 | bra$ |
| S1 | bracadabra$ |
| S4 | cadabra$ |
| S6 | dabra$ |
| S9 | ra$ |
| S2 | racadabra$ |
A[]の内容
| 11 | 10 | 7 | 0 | 3 | 5 | 8 | 1 | 4 | 6 | 9 | 2 |
以下では、入力データにはこの$が付けられていることを前提に話を進めます。
（実装上では、この$を明示的に使わなくても支障なくできます。よって、入力データが256種類あっても、$を表すために 入力データをintに保存するといったようなことはしなくても大丈夫です。）
さらに、入力データを buf[]と定義します。上のデータの例でいえば、
buf[0] = a
buf[1] = b
buf[2] = r
buf[3] = a
・
buf[10] = a
buf[11] = $
とできます（実際はbuf[11] はいらないですが、わかりやすくするために、この説明ではいれておきます）
また、各Suffix 、SiにはA[]が求まった後なら
buf[A[i]]
とやればそのSuffixの先頭を参照できることに注意してください。Suffix Siの3文字目を参照するならば、
buf[A[i] + 3]
とすれば参照できます。
------
Suffix Arrayは非常にシンプルな構造ですが、問題があります。それは構築、更新に時間がかかることです。
単純にソートすればよいのですが、そのまま行うと大変な時間がかかります。さらにソート対象のデータは数100MBから数十GBのオーダーであり、何か工夫をしなければとてもソートできそうにありません。
以下では、構築方法について最新の話題まで含めて紹介します。
Suffix Array構築の話の前に、このA[]を用いてどのようなことができるかというのを簡単に説明します。
例えば、BWTではblocksortng.htm で述べているように、このAから直接BWTの出力結果を求めることができます。
for (int i = 0; i < n; i++) if (a[i] == 0) putchar(buf[n - 1]); else putc( buf[a[i] - 1]); //bufに入力バッファが入っている
また、abraという単語が文書中に何回出現しているかを調べるには、abraはSuffix Arrayによって、集められているので、abraが出現している場所を調べ（Suffix と比較でbinary search O(logN) を行えばよい）そこから、何個abraがあるかをカウント （O(N)以下） すれば行えます。これはデータサイズNに対してO(logN)で行うことができます。
単純なアプローチ
以降ではSuffix Arrayの構築方法について述べます。
ここでは、私がblocksorting.htmで述べた方法を説明します。
まず、各Suffixをソートするのですが、大小関係は辞書式順序であり先頭から順番に比較していくので、先頭1文字目で比較して、小さい部分に区分けして、次に先頭から2文字目を比較する、次にさらに小さくなった各部分の3文字目を比較する・・
これを繰り返していくとSuffix Arrayが構築できます。
例えば、今までの例と同じように「abracadabra$」のSuffix Array構築を考えてみます。まず、一文字目（赤）でソートします。
| S0 | a | b | r | a | c | a | d | a | b | r | a | $ |
| S1 | b | r | a | c | a | d | a | b | r | a | $ | |
| S2 | r | a | c | a | d | a | b | r | a | $ | ||
| S3 | a | c | a | d | a | b | r | a | $ | |||
| S4 | c | a | d | a | b | r | a | $ | ||||
| S5 | a | d | a | b | r | a | $ | |||||
| S6 | d | a | b | r | a | $ | ||||||
| S7 | a | b | r | a | $ | |||||||
| S8 | b | r | a | $ | ||||||||
| S9 | r | a | $ | |||||||||
| S10 | a | $ | ||||||||||
| S11 | $ |
一文字目でソートすると、次の色づけで区分されたグループに分かれます。そのそれぞれで再帰的にソートを繰り返していきます。例えば、Suffix が aで始まるグループ（S0 3 5 7 10の緑のグループ）の二文字目を比較すると
| S11 | $ | |||||||||||
| S0 | a | b | r | a | c | a | d | a | b | r | a | $ |
| S3 | a | c | a | d | a | b | r | a | $ | |||
| S5 | a | d | a | b | r | a | $ | |||||
| S7 | a | b | r | a | $ | |||||||
| S10 | a | $ | ||||||||||
| S1 | b | r | a | c | a | d | a | b | r | a | $ | |
| S8 | b | r | a | $ | ||||||||
| S4 | c | a | d | a | b | r | a | $ | ||||
| S6 | d | a | b | r | a | $ | ||||||
| S2 | r | a | c | a | d | a | b | r | a | $ | ||
| S9 | r | a | $ |
| S11 | $ | |||||||||||
| S0 | a | b | r | a | c | a | d | a | b | r | a | $ |
| S7 | a | b | r | a | $ | |||||||
| S3 | a | c | a | d | a | b | r | a | $ | |||
| S5 | a | d | a | b | r | a | $ | |||||
| S10 | a | $ | ||||||||||
| S1 | b | r | a | c | a | d | a | b | r | a | $ | |
| S8 | b | r | a | $ | ||||||||
| S4 | c | a | d | a | b | r | a | $ | ||||
| S6 | d | a | b | r | a | $ | ||||||
| S2 | r | a | c | a | d | a | b | r | a | $ | ||
| S9 | r | a | $ |
とさらに分かれます。これを、各グループに所属するSuffixの数が1になるまで続けると、Suffix Arrayが完了します。
さらに細かく各部分に分ける部分のSortでは、例えばbucket sort（分布数えソート）、quick sort、insertion sortなどを用いて、ソートする部分のサイズに応じて、ソートを使い分けます。
ここで普通のquick sortではなく、pivotより、小さいもの、同じもの、大きいものの三つにわけるternary(multikey) quick sortを用いる方法は、[J.L.Bentley, R:Sedgewick "Fast algorithm for sorting and searching strings ", Proc, the 8th Annual ACM SIAM Symposium on Descrete Algorithm (1997), pp.360-369]で紹介されています。
このアルゴリズムは
partial_sort(int first, int last, int depth){
first <= i < lastについて buf[A[i] + depth] に基づいてA[i]のsortを行う
分けられた各block(first_i last_i)において last_i - first_i > 2なら
partial_sort(first_i, last_i, depth);
}
とかけます。
これでも十分な速度でsortできるのですが、各Suffix の一致長が長い場合、上の方法だとpartial_sortが深く呼び出されて速度が急速に低下します。
各Suffixの一致長が長い場合は、例えば、同じデータが並んでいる連長部分が挙げられ、通常あるデータにはよくある現象です。
