BW変換
読み：ビーダブリューへんかん
外語：BWT: Burrows-Wheeler transform
データ圧縮のための効果的な前処理アルゴリズムの一つ。
概要
Michael BurrowsとDavid John Wheelerによって、1994(平成6)年に提案された。
対象データ中には同じデータ列が集まりやすい性質を利用し、先頭移動法と統計的圧縮法とを組み合わせて高圧縮率を実現した。別名として「Block sorting」(ブロックソーティング、又はブロック整列法)とも呼ばれている。
特徴
BW変換では処理時間の殆どがソート処理に費やされるが、元のデータ列のDirected Acyclic Word Graph(DAWG)を構築すれば、ソートをしなくても変換データ列が生成可能で、ブロック整列法の高速化を図ることも可能。
また、この発明者が、そもそもアルゴリズム(算術)に対して特許をとるのはおかしいと考えるオープンソース陣営であったことから、特許が取られていないクリーンな存在となっている。
このアルゴリズムを用いた実装は幾つかあるが、最も有名な実装はbzip2である。gzip程ではないにしろ高速で、ある程度以上大きいファイルならgzipより高圧縮である。
再検索