データ圧縮のための効果的な前処理アルゴリズムの一つ。

目次 概要 特徴

概要

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

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

特徴

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

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

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

リンク

用語の所属
圧縮
BW
関連する用語
bzip2
gzip

[再検索] [戻る]