ブロックソート
ブロックソート、ブロックソーティング、Burrows-Wheeler変換 (Burrows-Wheeler Transform; BWT) は、1994年にマイケル・バローズ (Michael Burrows) とデビッド・ホイーラー (David Wheeler) が開発した可逆変換の方式で、データ圧縮の前処理に応用される。
ブロックソート自体はデータの大きさを変えない。しかし、データを整列することでデータ中に出現するパターンを、いくつかのよく知られている手法で圧縮し易いものにできる。後処理としてMove To Front (MTF)・連長圧縮 (RLE)・エントロピー符号と組み合わせて、データを圧縮する。
実装はbzip2等。
原理
長さ n のデータを巡回シフトし、得られるすべての文字列を辞書順にソートする。このようにしてできた n×n 行列の第 n 列を取り出したものが、BWT系列である。このBWT系列と、元の文字列がソートされた時行列の第何番目になったかを記憶しておくと、これから元の文字列を復号する事ができる。
アルゴリズム
ブロックソートをするには、巡回した文字列をソートする必要があるが、通常のソート方法(例えばクイックソートなど)を単純に適用すると文字列の長さ  に対して  の時間が必要になってしまう。そこで通常は巡回文字列であることを利用して、より効率的なソートを行う。
このためのアルゴリズムは複数提案されており、  、  、  のアルゴリズムが知られているが、実用上は, 自然言語などのような一般的な入力データに対しては  のものが速度やメモリ効率の点で最適である。
bzip2では  と  のアルゴリズムを入力に応じて最適なものに切り替えて使用している。またブロックサイズは100kバイトから900kバイトまで、-1 ～ -9 オプションで選択でき、デフォルトは900kバイトである。
圧縮のための後処理
ブロックソートしただけでは、データは「圧縮しやすく」なるだけでサイズはほぼ変化しない。実際に圧縮に応用するには後処理が必要となる。実用上はMTF (Move-To-Front) 法、RLE、エントロピー符号が用いられる。
BWT系列は、同じ記号が連続しやすい性質を持つため、MTFを用いると小さい整数の値が大きく偏る。そのため、RLEとエントロピー符号を適用することで、圧縮が行える。