ブロックソート(BlockSorting/BWT)のアルゴリズム(^o^)

abraca
この文字列をブロックソートし、復元してみる。

■１．　エンコード手順
まず、巡回シフトしたデータを全て含む文字列テーブルを作成する。

1:abraca
2:aabrac
3:caabra
4:acaabr
5:racaab
6:bracaa

これを辞書順に並べ替えると。

1:aabrac
2:abraca
3:acaabr
4:bracaa
5:caabra
6:racaab

このようになる。このときの一番右の列を縦に並べた物がエンコードしたデータになる。
ここでは、

caraab(2)

これがエンコードデータになる。(2)は、元データ"abraca"が並べ替え後の何番目のデータであるかを表す。

■２．　デコード手順
まず、caraabが一番右端のデータであることは分かっている。

1:?????c
2:?????a　←元データ
3:?????r
4:?????a
5:?????a
6:?????b

また、辞書順に並べ替えたので、一番左端は"caraab"を辞書順に並べた物と同じはずである。

1:a????c
2:a????a　←元データ
3:a????r
4:b????a
5:c????a
6:r????b

これを右シフトしてみる。
もともとシフトで生成したものなので、この2文字で始まる文字列がユニークに存在するはずである。

?:ca????
?:aa????
?:ra????
?:ab????
?:ac????
?:br????

これをソートしてみる。

1:aa????
2:ab????
3:ac????
4:br????
5:ca????
6:ra????

これは、ソート後のテーブルと一致しているはずである。
この右列にまたエンコードデータを追加してみる。

1:aa???c
2:ab???a
3:ac???r
4:br???a
5:ca???a
6:ra???b

ソート済みのテーブルに追加したので、問題ないはずである。
あとは繰り返し。
まずは右シフト。

?:caa???
?:aab???
?:rac???
?:abr???
?:aca???
?:bra???

ソート。

1:aab???
2:abr???
3:aca???
4:bra???
5:caa???
6:rac???

右列に追加

1:aab??c
2:abr??a　←元データ
3:aca??r
4:bra??a
5:caa??a
6:rac??b

右シフト。

?:caab??
?:aabr??
?:raca??
?:abra??
?:acaa??
?:brac??

ソート＆右列に追加。

1:aabr?c
2:abra?a　←元データ
3:acaa?r
4:brac?a
5:caab?a
6:raca?b

右シフト。

?:caabr?
?:aabra?
?:racaa?
?:abrac?
?:acaab?
?:braca?

ソート＆右列に追加。

1:aabrac
2:abraca　←元データ
3:acaabr
4:bracaa
5:caabra
6:racaab

これで、デコードデータ"abraca"が求められた。
以上が基本的な考え方である。

しかし、シフトするたびにソートしていたのでは重すぎる。
エンコード時にソート1回やるだけでも結構な負荷である。

そこで、巡回していることを利用してデコードを行う。

まず、1列目をソートしたデータがある。

1:a.....
2:a.....
3:a.....
4:b.....
5:c.....
6:r.....

これに番号を振る。

1:a1.....
2:a2.....
3:a3.....
4:b1.....
5:c1.....
6:r1.....

左シフトする。

1:.....a1
2:.....a2
3:.....a3
4:.....b1
5:.....c1
6:.....r1

これをソートすると。

1:a1.....c1
2:a2.....a?
3:a3.....r1
4:b1.....a?
5:c1.....a?
6:r1.....b1

このようになるはずである。
ここで、右の列のaは、ソートでどのように並び替えられたか分からないので、どの番号か分からなくなってしまう。
しかし実は、以下のように確定しているのである。

1:a1.....c1
2:a2.....a1
3:a3.....r1
4:b1.....a2
5:c1.....a3
6:r1.....b1

なぜか？
右シフトして考えてみる。

1:c1a1.....
2:a1a2.....
3:r1a3.....
4:a2b1.....
5:a3c1.....
6:b1r1.....

これをソートした場合、a1,a2,a3の順に並ばなければならないが、どうだろうか。
1列目a1の右にはa、1列目a2の右にはb、1列目a3の右にはcが来ている。
したがって、ソートすればa1,a2,a3の順に並ぶ。
これは偶然だろうか。
ここで2列目に着目する。
ソートしてから右シフトしたので、2列目はソートされている。
したがって、1列目が同じ文字に関しては2列目に従ってソートされるが、その際、元の順番は維持されたままになることが分かる。

よって

1:a1.....c1
2:a2.....a1　←元データ
3:a3.....r1
4:b1.....a2
5:c1.....a3
6:r1.....b1

これを元にデコードをすることを考えると。
a2の次はなにかというと、4行目の右端にa2がある。4行目の左端はb1だがこれはサイクリックにつながっているので、

a2→b1

というのがわかる。
同様に続けていくと、

a2→b1→r1→a3→c1→a1

となる。
これにより、デコードデータ"abraca"が求められた。

以上の内容は下記ページを参照し、自分なりに分かりやすくまとめたつもり。

http://homepage3.nifty.com/DO/blocksorting.htm
http://wiki.osdev.info/?BlockSorting