2段階ソート

HOME>>メモ>>アルゴリズム>>Suffix Array>>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
ここで Siは先頭からi番目の Suffix を表します. 一番最後の Suffix に関してはSi+1が存在しないので, S-type と約束しておきます.

「abracadabra$」の Suffix を S-type と L-type に分類すると,次のようになります.

No.開始位置Suffixタイプ
00abracadabra$S
11bracadabra$S
22racadabra$L
33acadabra$S
44cadabra$L
55adabra$S
66dabra$L
77abra$S
88bra$S
99ra$L
1010a$L
1111$S

S-type と L-type への分類は,文字列の後ろから決めていくと,線形時間で決定することができます.

S-typeとL-typeの性質

S-typeとL-typeに分類した Suffix をソートしてみましょう. すると,同じバケット内ではL-typenの Suffix がS-type のものよりも辞書順で小さくなっていることがわかります.

No.開始位置Suffixタイプ
011$S
110a$L
27abra$S
30abracadabra$S
43acadabra$S
55adabra$S
68bra$S
71bracadabra$S
84cadabra$L
96dabra$L
102racadabra$L
119ra$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タイプ
011$S
1L
27abra$S
30abracadabra$S
43acadabra$S
55adabra$S
68bra$S
71bracadabra$S
8L
9L
10L
11L

この表を上から順に見ていきます. Suffix Siが埋まっているの見つけたら,Si-1をチェックします. もしSi-1が L-type であれば,該当するバケットの開いているマスの中でもっとも上に Si-1を入れます.

例えば,上の表で一番上にある Suffix は S11です. S11-1=S10=a$は L-type なので,この Suffix を表に入れます. 場所は「a」のバケットの一番上,No.1 です.

No.開始位置Suffixタイプ
011$S
110a$L
27abra$S
30abracadabra$S
43acadabra$S
55adabra$S
68bra$S
71bracadabra$S
8L
9L
10L
11L

次に表が埋まっているのは S10 です(この操作の途中で埋まったものでもOK). S10-1=S9=ra$ は L-type なので, 該当するバケット「r」の一番上,No.10を埋めます.

No.開始位置Suffixタイプ
011$S
110a$L
27abra$S
30abracadabra$S
43acadabra$S
55adabra$S
68bra$S
71bracadabra$S
8L
9L
109ra$L
11L

この調子で表を埋めていくと最終的に Suffix Array が完了します.

ソートしなくていい理由

なぜソートをせず,順番に Suffix を埋めているだけなのに Suffix Array が得られるのでしょう. ここで重要になってくるのが,次の事実です.

  1. Suffix Si-1とSj-1の先頭の文字が等しければ,Si-1とSj-1の大小と,SiとSjの大小は一致する
  2. 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 だけとはいえ,ソートするのは大変です. この部分がボトルネックとなる速度が上がりません.