BW変換

Michael BurrowsとDavid John Wheelerによって、1994(平成6)年に提案された。

対象データ中には同じデータ列が集まりやすい性質を利用し、先頭移動法と統計的圧縮法とを組み合わせて高圧縮率を実現した。別名として「Block sorting」(ブロックソーティング、又はブロック整列法)とも呼ばれている。

BW変換では処理時間の殆どがソート処理に費やされるが、元のデータ列のDirected Acyclic Word Graph(DAWG)を構築すれば、ソートをしなくても変換データ列が生成可能で、ブロック整列法の高速化を図ることも可能。

また、この発明者が、そもそもアルゴリズム(算術)に対して特許をとるのはおかしいと考えるオープンソース陣営であったことから、特許が取られていないクリーンな存在となっている。

このアルゴリズムを用いた実装は幾つかあるが、最も有名な実装はbzip2である。gzip程ではないにしろ高速で、ある程度以上大きいファイルならgzipより高圧縮である。