ブロック・ソート

ウィキペディア

ブロックソート

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/06/02 03:08 UTC 版)

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

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

実装はbzip2等。

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

原理

長さ 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バイトである。

圧縮のための後処理

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

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

外部リンク

• HP Labs のテクニカルレポートアーカイブ上にある論文
• Algorithms with Python:データ圧縮 (後編)ブロックソート (BlockSorting)(M.Hiroi's Home Page)

ウィキペディア小見出し辞書

ブロックソート

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/19 15:57 UTC 版)

「接尾辞配列」の記事における「ブロックソート」の解説

接尾辞配列のソートアルゴリズムを利用して ブロックソート (Burrows-Wheeler 変換, BWT) を行うこともできる。技術的に、ブロックソートには接尾辞ではなく巡回シフトした文字列の辞書順のソートが要求される。このため、すべての文字列に番人としての文字"$"などを加えて巡回シフトを行うことで、接尾辞配列と同等の結果を得られる。