zip, compress, gzip, bzip2 - ファイル圧縮の形式に関する覚書

本記事の内容

  • zip, compress, gzip, bzip2の開発経緯と技術について
  • 圧縮とアーカイブの違い
  • zip, compress, gzip, bzip2の性能比較(デモ)
  • bzip2の圧縮性能を支える技術のキーワード(BWT、ハフマン符号)

zip, compress, gzip, bzip2の違い(それぞれの歴史)

zipとは?

zipは1989年にフィル・カッツによって提案された圧縮形式で、現在最も多く用いられている圧縮形式であると同時に、後述する多くの圧縮形式に名前を貸し与えています。

ファイルは辞書を用いて圧縮され、Lempel, Zivらによって1977年に提案されたLZ77法が使われています。 また、文字列の符号化にはハフマン符号が用いられています(上記まとめたアルゴリズム名は『Deflate』)。

zipはアーカイバとしての機能を持ち、複数ファイルをまとめつつ、ファイルサイズを下げることが出来ます。

compressとは

Lempel, Zivらによって提案されたアルゴリズムには、 1977年に提案されたLZ77法と1978年に提案されたLZ78法の2種類があるのですが、 compressでは、LZ88法の改良版として提案された、Lempel-Ziv-Welchのアルゴリズム(LZW)が用いられています。 (ちなみに、LZWの提案は1984年。)

gzipとは

gzipはGNU ZIPの略称で、オープンソースプロジェクトの走りとも言える(というと偉い人から怒られるのですが…)GNUプロジェクトの一環として開発された圧縮方式です。 当時広まっていたcompressの代替を目して開発された方式で、zipと同様に圧縮はDeflateによります。

zipとは異なりアーカイブ機能はありません。

bzip2とは

bzip2は1996年に公開されたファイル圧縮形式で、gzipに加えて下記の処理が加わっており、圧縮効率がなお高まっています。

  • BWT(Burrows-Wheeler Transformation, バロウズ・ホイラー変換)を用いた前処理
  • Move to Front法による前処理

またgzipと同様、ハフマン符号を用いている点もポイントです。

これらの処理を行う分、処理速度ではgzipに軍配が上がるとされています。 こちらも、zipとは異なりアーカイブ機能はありません。

補足:圧縮とアーカイブの違い

用語定義
圧縮ファイルサイズを小さくすること
アーカイブ複数ファイルを一つにまとめること

アーカイブを行うプログラムを アーカイバ とも呼び、 上述した形式には、アーカイバとしての機能があるものとないものが存在します。

辞書、BWT、ハフマン符号 - 圧縮にかかわる技術を学ぶには

さて、ここまでの内容にはいくつかの用語が登場してきました。

  • 辞書を用いた圧縮
    • LZ77法
  • BWT(Burrows-Wheeler Transformation, バロウズ・ホイラー変換)
  • ハフマン符号

実は上記はいずれも、『高速文字列解析の世界 データ圧縮・全文検索・テキストマイニング』(岡野原、2012)の中で詳細に解説されています。

Altus-Fiveブログでは本書を読み解きながら、今後 これら技術に関するデモ実装をPythonで行いたい と考えておりますので、ご興味のある方はぜひブックマーク、もしくははてブを押していって頂けると嬉しいです。

おまけ:テキスト圧縮の性能比較 - zip, gzip, compress, bzip2を比べてみた

今回はデモとして、青空文庫からダウンロードした相対性理論の論文(sotaisei_riron.txt)を圧縮してみました。

圧縮方式BeforeAfter
zip29KB12KB
gzip29KB12KB
compress29KB15KB
bzip229KB10KB

このファイルについて4形式を比べた時、 bzip2の性能が最も良い という結果となっています。

なぜbzip2は性能が良いのか?

先ほどの繰り返しになりますが、

  1. 索引作成の前処理としてBWT(Burrows-Wheeler Transformation, バロウズ・ホイラー変換)、MTF (Move-To-Front) 法を行なっている
  2. 圧縮方式としてハフマン符号を用いており、入力テキストそれぞれに二分木(ハフマン木)を生成。最適な符号化を行なっている

といった理由が挙げられます。 上記キーワードの詳細は、すべて『高速文字列解析の世界』(岡野原,2012)に載っていますので(MTF法を除く)、よければご参照ください。 本記事はあくまで「歴史的経緯のまとめ」ですが、技術の深みの面白さについて伝えていくため、 今後、BWTやハフマン符号の概略を示す記事をAltus-Fiveブログで掲載したいと思っています。

参考記事

アルタスファイブのブログでは、データ構造に関する記事を定期的に執筆しております。 よろしければ、ご参照ください。

\(^▽^*) 私たちと一緒に働いてみませんか? (*^▽^)/

少しでも興味をお持ちいただけたら、お気軽に、お問い合わせください。

採用応募受付へ

(採用応募じゃなく、ただ、会ってみたいという方も、大歓迎です。)