BW変換

読み:ビーダブリューへんかん
外語:BWT: Burrows-Wheeler transform 英語
品詞:固有名詞

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

目次

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

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

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

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

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

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

コメントなどを投稿するフォームは、日本語対応時のみ表示されます


KisoDic通信用語の基礎知識検索システム WDIC Explorer Version 7.04a (27-May-2022)
Search System : Copyright © Mirai corporation
Dictionary : Copyright © WDIC Creators club