2段階ソート
バケットソートでは，Suffixをバケットというグループに分類ました． しかし，バケットに分けたところですべての Suffix をソートしなければいけないことには変わりがありません． なんとかソートしなければいけない Suffix を減らせないでしょうか． Suffix間の関係を上手く使うことでこれを実現するのが2段階ソートです．
S-typeとL-type
すべての Suffix を次の規則にしたがって L-type と S-type の2種類に分類します．
- S-type: Si<Si+1となるSuffix
- L-type: Si>Si+1となるSuffix
「abracadabra$」の Suffix を S-type と L-type に分類すると，次のようになります．
| No. | 開始位置 | Suffix | タイプ |
|---|---|---|---|
| 0 | 0 | abracadabra$ | S |
| 1 | 1 | bracadabra$ | S |
| 2 | 2 | racadabra$ | L |
| 3 | 3 | acadabra$ | S |
| 4 | 4 | cadabra$ | L |
| 5 | 5 | adabra$ | S |
| 6 | 6 | dabra$ | L |
| 7 | 7 | abra$ | S |
| 8 | 8 | bra$ | S |
| 9 | 9 | ra$ | L |
| 10 | 10 | a$ | L |
| 11 | 11 | $ | S |
S-type と L-type への分類は，文字列の後ろから決めていくと，線形時間で決定することができます．
S-typeとL-typeの性質
S-typeとL-typeに分類した Suffix をソートしてみましょう． すると，同じバケット内ではL-typenの Suffix がS-type のものよりも辞書順で小さくなっていることがわかります．
| No. | 開始位置 | Suffix | タイプ |
|---|---|---|---|
| 0 | 11 | $ | S |
| 1 | 10 | a$ | L |
| 2 | 7 | abra$ | S |
| 3 | 0 | abracadabra$ | S |
| 4 | 3 | acadabra$ | S |
| 5 | 5 | adabra$ | S |
| 6 | 8 | bra$ | S |
| 7 | 1 | bracadabra$ | S |
| 8 | 4 | cadabra$ | L |
| 9 | 6 | dabra$ | L |
| 10 | 2 | racadabra$ | L |
| 11 | 9 | ra$ | L |
これは偶然ではなく，どんな文字列に対しても成り立ちます． この理由はSi+1がSiの先頭1文字を取ったものであることと， その大小関係を考えるとわかります． 例えば，先頭の文字が「x」のバケットを考えてみましょう． L-type の2文字目以降には「x」を除けば「x」より小さい文字「a,b,...,w」が最初に出現します． 一方，S-type の2文字目以降には「x」より大きい文字「y, z」が現れます． 「a,b,...,w」<「x」<「y, z」なので，必ず L-type < S-type となることがわかりますね．
ソートをせずにソートする
2段階ソートの面白いところは， 「一方のタイプだけソートすれば，もう一方のタイプは『ソートしなくても』ソートできる」 という点です． ここでは S-type のみをソートした場合を考えてみましょう．
S-typeの Suffix が何らかの方法でソートできたとします． S-typeは各バケットの後ろのほうにくることがわかっているので， 次の表のように Suffix Array の S-type の部分のみをうめることができます．
| No. | 開始位置 | Suffix | タイプ |
|---|---|---|---|
| 0 | 11 | $ | S |
| 1 | L | ||
| 2 | 7 | abra$ | S |
| 3 | 0 | abracadabra$ | S |
| 4 | 3 | acadabra$ | S |
| 5 | 5 | adabra$ | S |
| 6 | 8 | bra$ | S |
| 7 | 1 | bracadabra$ | S |
| 8 | L | ||
| 9 | L | ||
| 10 | L | ||
| 11 | L |
この表を上から順に見ていきます． Suffix Siが埋まっているの見つけたら，Si-1をチェックします． もしSi-1が L-type であれば，該当するバケットの開いているマスの中でもっとも上に Si-1を入れます．
例えば，上の表で一番上にある Suffix は S11です． S11-1=S10=a$は L-type なので，この Suffix を表に入れます． 場所は「a」のバケットの一番上，No.1 です．
| No. | 開始位置 | Suffix | タイプ |
|---|---|---|---|
| 0 | 11 | $ | S |
| 1 | 10 | a$ | L |
| 2 | 7 | abra$ | S |
| 3 | 0 | abracadabra$ | S |
| 4 | 3 | acadabra$ | S |
| 5 | 5 | adabra$ | S |
| 6 | 8 | bra$ | S |
| 7 | 1 | bracadabra$ | S |
| 8 | L | ||
| 9 | L | ||
| 10 | L | ||
| 11 | L |
次に表が埋まっているのは S10 です(この操作の途中で埋まったものでもOK)． S10-1=S9=ra$ は L-type なので， 該当するバケット「r」の一番上，No.10を埋めます．
| No. | 開始位置 | Suffix | タイプ |
|---|---|---|---|
| 0 | 11 | $ | S |
| 1 | 10 | a$ | L |
| 2 | 7 | abra$ | S |
| 3 | 0 | abracadabra$ | S |
| 4 | 3 | acadabra$ | S |
| 5 | 5 | adabra$ | S |
| 6 | 8 | bra$ | S |
| 7 | 1 | bracadabra$ | S |
| 8 | L | ||
| 9 | L | ||
| 10 | 9 | ra$ | L |
| 11 | L |
この調子で表を埋めていくと最終的に Suffix Array が完了します．
ソートしなくていい理由
なぜソートをせず，順番に Suffix を埋めているだけなのに Suffix Array が得られるのでしょう． ここで重要になってくるのが，次の事実です．
- Suffix Si-1とSj-1の先頭の文字が等しければ，Si-1とSj-1の大小と，SiとSjの大小は一致する
- Suffix Si-1が L-type ならば，Si-1>Si
1番目は辞書順の比較の定義です． Suffix Siを小さいものから順番に処理しているので，同じバケットの中ではSi-1も小さいものから順番になっていることがわかります．
2番目は少し書き換えてありますが L-type の定義です． この定義から，Siを処理したときには， L-type の Suffix Si-1 は必ず Si の下に書き込まれることがわかります． これはつまり，新しく表に書き込んだ Suffix でも 上から順番に処理すれば全部処理される，ということを表しています． この定義のおかげですべての Suffix が表に書き込まれることが保証できるわけです．
問題点
2段階ソートにより L-typeのソートはしないで済むようになりました． しかし，S-type をソートする必要はまだ残っています． 元の文字列が長くなると S-type だけとはいえ，ソートするのは大変です． この部分がボトルネックとなる速度が上がりません．