Burrows-Wheeler変換とは？わかりやすく解説

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

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

実装はbzip2等。

Python言語による実装例が文献^[1]に出ている。

原理

長さ 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$ (元文字列とBTW系列とをハイライト、並べ替え前のインデックスも参考までに表示):

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

得られたBWT系列およびインデックス:

ccoaa, 3

これは行が昇順にソートされた後の行列の最終列(右端の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バイトである。