ブロックソート

ウィキペディア

ブロックソート

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

ブロックソート、ブロックソーティング、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

辞書式順序で行同士を比較して、昇順となるように行を並べ替えて得られた行列${\displaystyle M}$

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

ブロックソート

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

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

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