ブロックソート

ブロックソート、ブロックソーティング、Burrows-Wheeler変換 (Burrows-Wheeler Transform; BWT) は、1994年にマイケル・バローズ (Michael Burrows) とデビッド・ホイーラー (David Wheeler) が開発した可逆変換の方式で、データ圧縮の前処理に応用される。

ブロックソート自体はデータの大きさを変えない。しかし、データを整列することでデータ中に出現するパターンを、いくつかのよく知られている手法で圧縮し易いものにできる。後処理としてMove To Front (MTF)・連長圧縮 (RLE)・エントロピー符号と組み合わせて、データを圧縮する。

実装はbzip2等。

原理

長さ n のデータを巡回シフトし、得られるすべての文字列を辞書順にソートする。このようにしてできた n×n 行列の第 n 列を取り出したものが、BWT系列である。このBWT系列と、元の文字列がソートされた時行列の第何番目になったかを記憶しておくと、これから元の文字列を復号する事ができる。

符号化の手順

元の文字列:

cacao

生成された巡回行列:

	A	B	C	D	E
1	c	a	c	a	o
2	o	c	a	c	a
3	a	o	c	a	c
4	c	a	o	c	a
5	a	c	a	o	c

ソートされた行列$M$:

	A	B	C	D	E
5	a	c	a	o	c
3	a	o	c	a	c
1	c	a	c	a	o
4	c	a	o	c	a
2	o	c	a	c	a

得られたBWT系列:

ccoaa, 3

ソートされた5×5行列の第5列(右端のE列)を縦に取ったものと、元の文字列がソートした後に何番目の行にあったかを覚える。

復号の手順

復号は非常に単純かつ機械的に行えるが、「なぜ」きちんと復号されるかを直観的に理解するのは少し難しい。そこで理解のため、元の巡回行列を復元する事を考える。

まず、BWT系列の文字列「ccoaa」をソートすると行列$M$のA列が得られる。 (A列とE列に含まれるアルファベットは同一であり, A列はソートされているため)

初期状態：（表1）

	A	B	C	D	E
1	a	?	?	?	c
2	a	?	?	?	c
3	c	?	?	?	o
4	c	?	?	?	a
5	o	?	?	?	a

各行は元の文字列を巡回シフトしたものであるため、各行のE列、A列の文字は元の文字列で連続しているか、先頭と末尾の文字であったはずである。 この性質から、全列右シフトを行い、左端の列(ここではE列)をキーにソートすることでD列を得ることができる。このとき、左端の文字が同じ行については、他の列の文字によらず、元の表での順序を保ったままにする。すなわち、ソートは安定ソートでなければならない。

右シフトした状態:（表2）

	E	A	B	C	D
1	c	a	?	?	?
2	c	a	?	?	?
3	o	c	?	?	?
4	a	c	?	?	?
5	a	o	?	?	?

ソート後の状態:（表3）

	E	A	B	C	D
4	a	c	?	?	?
5	a	o	?	?	?
1	c	a	?	?	?
2	c	a	?	?	?
3	o	c	?	?	?

このときBWT系列の性質から、右端となったD列には表1の右端と同様にBWT系列の文字列「ccoaa」が順番に入ることになる。

右端を埋めた状態：（表4）

	E	A	B	C	D
4	a	c	?	?	c
5	a	o	?	?	c
1	c	a	?	?	o
2	c	a	?	?	a
3	o	c	?	?	a

この操作を繰り返し行い順次C、Bと求めていくことで、最終的に行列$M$を得ることができる。

復号の手順の効率化

しかし手順のたびにソートを行うのは非効率である。

このため、表2から表3への各行の移動が毎回固定的に一対一対応することに着目し、その対応を追うことで復元を行うのが一般的である。

表2から表3への各行の移動の対応表：

ソート前	ソート後
1	4
2	5
3	1
4	2
5	3

これを元の文字列であった3から追いかけると、3→1,4,2,5,3となる。

この位置の文字をBWT系列の文字列「ccoaa」から順番に取り出すと「cacao」となり、元の文字列が得られる。

アルゴリズム

ブロックソートをするには、巡回した文字列をソートする必要があるが、通常のソート方法(例えばクイックソートなど)を単純に適用すると文字列の長さ $n$ に対して $\mathrm {O} (n^{2}\log n)$ の時間が必要になってしまう。そこで通常は巡回文字列であることを利用して、より効率的なソートを行う。

このためのアルゴリズムは複数提案されており、 $\mathrm {O} (n)$ 、 $\mathrm {O} (n\log \log n)$ 、 $\mathrm {O} (n\log n)$ のアルゴリズムが知られているが、実用上は, 自然言語などのような一般的な入力データに対しては $\mathrm {O} (n\log n)$ のものが速度やメモリ効率の点で最適である。

bzip2では $\mathrm {O} (n\log \log n)$ と $\mathrm {O} (n\log n)$ のアルゴリズムを入力に応じて最適なものに切り替えて使用している。またブロックサイズは100kバイトから900kバイトまで、-1 ～ -9 オプションで選択でき、デフォルトは900kバイトである。

圧縮のための後処理

ブロックソートしただけでは、データは「圧縮しやすく」なるだけでサイズはほぼ変化しない。実際に圧縮に応用するには後処理が必要となる。実用上はMTF (Move-To-Front) 法、RLE、エントロピー符号が用いられる。

BWT系列は、同じ記号が連続しやすい性質を持つため、MTFを用いると小さい整数の値が大きく偏る。そのため、RLEとエントロピー符号を適用することで、圧縮が行える。

外部リンク

• HP Labs のテクニカルレポートアーカイブ上にある論文