本記事の内容
- 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法の２種類があるのですが、 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）を圧縮してみました。
| 圧縮方式 | Before | After |
|---|---|---|
| zip | 29KB | 12KB |
| gzip | 29KB | 12KB |
| compress | 29KB | 15KB |
| bzip2 | 29KB | 10KB |
このファイルについて4形式を比べた時、 bzip2の性能が最も良い という結果となっています。
なぜbzip2は性能が良いのか？
先ほどの繰り返しになりますが、
- 索引作成の前処理としてBWT（Burrows-Wheeler Transformation, バロウズ・ホイラー変換）、MTF (Move-To-Front) 法を行なっている
- 圧縮方式としてハフマン符号を用いており、入力テキストそれぞれに二分木（ハフマン木）を生成。最適な符号化を行なっている
といった理由が挙げられます。 上記キーワードの詳細は、すべて『高速文字列解析の世界』（岡野原，2012）に載っていますので（MTF法を除く）、よければご参照ください。 本記事はあくまで「歴史的経緯のまとめ」ですが、技術の深みの面白さについて伝えていくため、 今後、BWTやハフマン符号の概略を示す記事をAltus-Fiveブログで掲載したいと思っています。
参考記事
アルタスファイブのブログでは、データ構造に関する記事を定期的に執筆しております。 よろしければ、ご参照ください。
関連記事
- 2018/07/18 全文検索を自社サイト・社内サーバーに構築したいクライアントのための留意点 システム開発における「全文検索」の実装方式・コスト・性能に関して、クライアント企業の方にも腹落ち頂けるようまとめました。grep型と索引型の違いに関する平易な解説を記載しているので、これらをクライアントに解説されたい開発者にもオススメです。
- 2018/05/07 Rubyの配列(Array)を魔改造して、連想配列として使ってみた 連想配列をRubyで実装することを通じ、普段我々が使っている連想配列の性能について理解することを目指した記事です。Rubyの配列(Array)を連想配列に魔改造するための、30行ほどの短いコードをGitHubで公開しています。
- 2018/05/07 「ハッシュ」完全理解のための覚書 ハッシュテーブルをRubyで実装してみる 「ハッシュ関数」「ハッシュ値」「ハッシュテーブル」についてごまかしなく理解することを目的に、Rubyでハッシュテーブルクラスを自作してみました。ソースコードは100行に満たないので、コードリーディングを通じたデータ構造の理解にお役立てください。
- 2017/11/13 【Pythonでテキスト処理】Double arrayでTrieを実装してみた 今回はDouble Array（ダブル配列）というデータ構造で実際にTrieをPythonで構築し、共通接頭辞検索を行えるようにします。実装方法については[『日本語入力を支える技術』（徳永, 2012）に準拠。書籍をお持ちでない方にも理解できることを目指しています。
- 2017/09/06 テキスト処理に使われるTrie（トライ木）とLOUDSに関する概略 Trieはテキスト処理において必需品と言えるデータ構造です。辞書検索、日本語入力、サジェストの実装や、形態素辞書が主な用途と言えるでしょうか。Pythonの自然言語処理パッケージNLTKでも、形態素解析にトライ木を用いています。