技術/歴史/zip,gzip,zlib,bzip2

id: 495 所有者: msakamoto-sf 作成日: 2009-11-22 17:11:47
カテゴリ: Linux UNIX Windows

[ Prev ]
[ Next ]
[ 技術 ]

お仕事絡みで、ZIPファイルの歴史が気になったので調べてみた。
前々から何となく「gzipとzlibとzipってどう違うんだろう」とは思っていたのだけれど、WindowsでLhacaやLhaplusなどのアーカイブソフト、あるいはXP以降ならOSの機能としてデフォルトでzip圧縮できるし、Linux/UNIXでも2-3回コマンドラインオプションを試行錯誤してmanページ見ればtar.gz作ったり逆にWindows上で圧縮したzipを適当に解凍できるので「ま、いっか。」で済ませてた。
でもせっかくなので、技術的な詳細には突っ込まないが、ざっくりとした歴史や流れをWikipediaを中心に追ってみた。
※殆どの記述をWikipediaに依っている為、本記事自体の信頼性はWikipediaと同等かそれに劣るものとして下さい。正確性は無保証、Wikipediaの寄せ集め。自分用のメモです。

簡単に紹介：

ZIP : DOS発祥の圧縮アーカイブソフト向けファイルフォーマット。本家はPKZIPで、圧縮アルゴリズムとして採用され有名になった内の一つが"Deflate"アルゴリズム。UNIX/Linux上の実装として"Info-ZIP"プログラムが開発され、これが現在の"zip", "unzip"コマンドである。
gzip(GNU zip) : 元々compressというUNIX上の圧縮プログラムがあったが圧縮アルゴリズムの特許問題で普及しなかったため、代替として開発された。名前に"zip"が含まれているがファイルフォーマットとしては互換性のない独自路線。圧縮アルゴリズムとしてPKZIPの"Deflate"を採用しているのが共通点といえば共通点。
zlib : gzipのメイン開発者が、"Deflate"アルゴリズム処理部分だけを緩いライセンスで実装したライブラリ。Linux/UNIXだけでなく、Windowsなど幅広いプラットフォームに移植されている。

"Lempel-Ziv"可逆データ圧縮アルゴリズムの歴史とcompress哀史
ZIPファイルフォーマットの歴史
もう一つの流れ：gzip, zlib

"Lempel-Ziv"可逆データ圧縮アルゴリズムの歴史とcompress哀史

zipファイルの足取りを辿る前に、可逆圧縮アルゴリズムの一つ、"LZ"データ圧縮アルゴリズムの歴史を追ってみる。
"LZ77"( or LZ1)と呼ばれる1977年発表のアルゴリズムから様々な亜種が派生し現在に至っている。
その中の"LZW"圧縮の特許問題で大きく影響を受けたUNIXの圧縮コマンド、compressコマンドについても簡単に調べてみた。

"LZ77"に端を発する"LZ"ファミリーの系譜

まず Jacob Ziv, Abraham Lempelの二人が作ったデータ圧縮アルゴリズム、"LZ"ファミリーの系譜をまとめる。

1977年：Jacob Ziv と Abraham Lempel によるデータ圧縮の論文、"A Universal Algorithm for Sequential Data Compression" が発表される。"LZ"で始まる名前のデータ圧縮アルゴリズムの源流である。この論文によるデータ圧縮アルゴリズムは "LZ1" または1977年の発表という事から "LZ77" と呼ばれる。
1978年：同じくこの二人によるIEEEの論文 "Compression of Individual Sequences via Variable Rate Coding" にて LZ77 の改良版が発表され、"LZ2" または1978年の発表という事から "LZ78" と呼ばれる。
1982年：LZ77の改良版である "LZSS"(Lempel-Ziv-Storer-Szymanski) が James Storer と Thomas Szymanski による "Data compression via textual substitution"(Journal of the ACM) で発表される。幾つかのアーカイブソフトやBIOSの世界で現在もサポートされている。
1984年：LZ78の改良版である "LZW"(Lempel-Ziv-Welch) 圧縮アルゴリズムが Terry Welch による " A Technique for High-Performance Data Compression"(IEEE) で発表される。
1993年：LZ77の改良版である "Deflate"圧縮が Phil Katz のPKZIP 2.0で実装される。
1995年：LZ77の改良版である "LZX"が Jonathan Forbes と Tomi Poutanen により、Amigaのファイルアーカイバとして公開される。後にForbesはMicrosoft社に移り、Microsoft Cabinetファイル(.CAB)の圧縮方式としてLZX圧縮をサポートすることになる。またMicrosoft Compressed HTML Helpファイル(.CHM)の圧縮にも採用される事になる。
1996年：LZ77の改良版である "LZO"(Lempel-Ziv-Oberhumer) 圧縮フォーマットの実装が Markus F.X.J. Oberhumer により始まる。
1996年：LZ77の改良版である "LZMA"(Lempel-Ziv-Markov chain-Algorithm) 圧縮フォーマットの実装がIgor Pavlov により始まる。"Markov"とは「マルコフ連鎖」「マルコフ過程」のマルコフであり、ロシア人数学者アンドレイ・マルコフにちなんで命名されたらしい。
- （すみません、LZMA自体の論文や出典は探し切れませんでした。御存知の方居たら教えて下さい）

LZファミリーについては他にも種類があるようだが、当記事の趣旨であるzipファイルフォーマットに関連しているものについてはおおよそ上記8種類だろう。

"LZMA"については、Igor Pavlov によるオープンソースのアーカイブソフト "7-Zip" の開発と共にリファレンス実装が進められている。
7-ZipのSourceForge.netからダウンロードしたlzmaのライブラリソースに、"history.txt"というファイルが入っている。その末尾に1996年からのLZMAと7-Zipの歩みが簡単にまとめられている。

HISTORY of the LZMA
-------------------
  2001-2008:  Improvements to LZMA compressing/decompressing code, 
              keeping compatibility with original LZMA format
  1996-2001:  Development of LZMA compression format

  Some milestones:

  2001-08-30: LZMA compression was added to 7-Zip
  1999-01-02: First version of 7-Zip was released

LZWアルゴリズムの特許問題とcompressツール

UNIXコマンドの一つ"compress"は、LZWアルゴリズムを採用したデータ圧縮ツールである。圧縮されたファイルの拡張子は".Z"であり、tarファイルを圧縮した場合は拡張子を".tar.Z"や".taz"とする習慣がある。
ところがLZWアルゴリズムが特許で保護されており、ロイヤリティを支払わないと使えない事が判明する。これにより、代替であり圧縮率も良いことからGNU zipなど他のzip圧縮がLinux/UNIX上で広まる事になる。

これはGIF特許問題としても有名であるが、compressツールとの関連部分についてまとめる。簡単に時系列に書いてみる。

1981年 : LZ78が U.S. Patent 4,464,650 として出願される。 → 1984年公開
- http://www.google.com/patents?vid=4464650
1983年 : LZWが U.S. Patent 4,558,302 として出願される。Sperry社保有。 → 1985年12月公開
- http://www.google.com/patents?vid=4558302
1984年 : LZWアルゴリズム発表, Spencer Thomasによりcompressツール実装開始
1985年 : compressがUSENETで公開、同時にU.S. Patent 4,558,302 公開

つまり論文発表の前に、特許出願を行っていたのだ。
ところが1984年発表の論文 "A Technique for High-Performance Data Compression" ではSperry社による特許出願に言及されていなかった。そのため Spencer Thomas が特許については気づかずに、論文を元にcompressを実装したのが1984年である。その後 Joseph M. Orost が Spencer とその他のチームを率いて compress ツールの"final"バージョン(4.0)を仕上げ "comp.sources.unix" USENETグループでフリーソフトとして公開したのが1985年。ところが同年12月、LZWの特許が公開され、このため折角フリーソフトとして公開されたcompressだが、実際に使うにはロイヤリティを支払わなければならない事になってしまった。そのため人々の人気はLinuxベースのOSなどで、代替アルゴリズムを使ったgzipやbzip2へとシフトしてしまう。
問題のLZWのアルゴリズムだが、米国では 1983年出願 → 1985年公開 → 2003年期限切れとなっている。日本では 1984年出願 → 1996年公開 → 2004年期限切れとなっている。

1993年にPhil KatzによるPKZIP-2.0の"Defelate"圧縮アルゴリズムが発表された後、LZWを使うcompressに代わり"Deflate"による圧縮を行う"gzip"(GNU zip)が開発されることになる。

参考資料

"LZ"ファミリー(ja)：

"LZ"ファミリー(en)：

"LZ"ファミリー関連：

"compress"ツール：

その他：

mixi Engineers’ Blog ≫ 圧縮データベースを使おう
- http://alpha.mixi.co.jp/blog/?p=191
Focus on Technology：静かな注目を集める圧縮アルゴリズム「LZMA」 - ITmedia エンタープライズ
- http://www.itmedia.co.jp/enterprise/articles/0906/19/news003.html
LZW特許問題で影響を受けたソフトウェアや対応の一覧
- http://www.frugalcorner.com/lzw/lzwfree.html

ZIPファイルフォーマットの歴史

ZIPは圧縮(or非圧縮)ファイルデータを格納する為のアーカイブファイル向けファイルフォーマットである。誤解しやすいが、圧縮アルゴリズムの名前では無い。
圧縮アルゴリズム自体はLZ77の改良版である"Deflate"アルゴリズムを標準でサポートする(PKZIP 2.0より)。

PKZIPの誕生

ZIPの誕生は1989年。Phil KatzによりDOS上のツール、PKZIPとして産声をあげた。

元々Phil KatzはAllen-Bradley社にプログラマとして雇われていた。1986年にWisconsin州はMilwaukee市にあったGraysoftで働く為にAllen-Bradley社を辞める。Graysotでは、Thom HendersonのARCというデータ圧縮アーカイバソフトの代替を開発している。
System Enhancement Associates(SEA)により開発されたARCは初期のBBSネットワークで人気があり、SEAのBBSでCのソースコードも入手できた。
Katzは一部をアセンブラで書き直し、最終的にPKARCという名前のシェアウェアとして公開する。
1986年にKatzは自分の会社であるPKWAREを興す。Graysoftには1987年まで在籍している。

PKARCはアセンブラで書かれている事もあり、速度面で有利で人気を博す。ところが拡張子が".ARC"のままであったり、ソースコード中にSEAが著作権を持つソースが混入していたりと、SEAにより商標・著作権の侵害で訴えられている。
1988年はPKWAREとSEAの対決の年で、KatzはPKARCの販売を止め、代わりに名前と拡張子が異なるだけの"PKPAK"という名前にしてリリースしている。PKWAREは1985年に公開してたPKXARCから始まるARC互換プログラムに対して、1989年の1月31日まで販売しても良いという条件でSEAにライセンス料金を支払っている。

そして1989年の2月1日、ちょうどARC互換プログラムの公開期限が終わった次の日にPKZIP-0.9が発表され、"ZIP File Format Specification"の初版がPKZIP-0.9のパッケージ中の"APPNOTE.TXT"として同梱される。なおやはりPKZIPはシェアウェアとして公開された。
ちなみに"zip"というのは、「素早い」とか「弾丸のように」という意味で、Katzの友人であるRobert Mahoneyによる提案らしい。

PKWARE社はその後紆余曲折があったようだが、2009年11月現在、ZIPファイルのセキュリティやZIPファイルフォーマットの本家として仕様をリードしていたりと健在である。Katz自身は1991年からアルコール中毒に悩まされていたようで、2000年4月14日に亡くなっている。

"ARC"ファイルフォーマット(Wikipedia)
- http://en.wikipedia.org/wiki/ARC_%28file_format%29
PKWARE社により現在もメンテナンスと更新が続けられている"APPNOTE.TXT"
- http://www.pkware.com/support/application-note-archives
- → http://www.pkware.com/documents/APPNOTE/APPNOTE_6.2.0.txt
Phil Katz

少し寄り道：日本発祥のLHA形式, LZH形式

2009年現在もよく見かける".lzh"の拡張子だが、その源流は1988年に開発されたLHAというプログラムになる。
詳しくはWikipediaを参照して欲しいが、当事者である奥村晴彦氏による"データ圧縮の昔話"に1988年 - 1993年におけるPC-VANのSIG SCIENCEでの書き込みがまとめられている。
"LZ"ファミリーの圧縮アルゴリズムの話やLZWを初めとする"LZ"ファミリーの特許問題などがリアルタイムに取り上げられており、1980-1990年代のデータ圧縮の変遷を辿るための貴重な資料となっている。

LHAプログラム, LZH形式
- http://ja.wikipedia.org/wiki/LHA
"データ圧縮の昔話"
- http://oku.edu.mie-u.ac.jp/~okumura/compression/oldstory.html

ZIPファイルフォーマット

ZIPはあくまでも複数の圧縮 or 非圧縮ファイルデータをまとめ、一つのアーカイブファイルに格納する為の「ファイルフォーマット」である。基本思想として、「圧縮または非圧縮のファイルデータ１つ分」をヘッダとフッタで挟んだのを１単位とし、それをいくつも繋げ、その末尾にアーカイブ全体のメタ情報を含んだフッタ情報を置く。
APPNOTE_6.2.0.txtからの引用だが、"[local file header n][file data n][data descriptor n]"がファイルデータ１つ分を表す。

[local file header 1]
[file data 1]
[data descriptor 1]
...
[local file header n]
[file data n]
[data descriptor n]
[archive decryption header] (EFS)
[archive extra data record] (EFS)
[central directory]
[zip64 end of central directory record]
[zip64 end of central directory locator] 
[end of central directory record]

詳細は後掲のAPPNOTEやWikipedia, "ＴＮＫソフトウェア - 私的ZIPファイル研究所"を参照して貰うとして、ここでは興味深いポイントを二箇所紹介するに留める。

"local file header"の中に圧縮形式を選べるフィールドが存在する。
"cenntral directory"の中にエントリが格納されているが、各ファイルデータへのオフセットが「相対」で記録されている。

まず1番目の、圧縮形式を選べるフィールドが存在する点。これはつまり将来複数の圧縮形式をサポートする事が可能であり、事実、PKZIPはその後のバージョンアップでサポートする圧縮形式を増やしていく。
次に2番目の各ファイルデータへのオフセットが「相対」で記録されている点。これは最初のファイルデータがファイルの先頭から始まらなくも問題無い事を意味しており、ZIPデータの前後に任意のデータを繋げられる事を可能としている。これはやがて、自己解凍形式のzipファイルとして活用される事になる。

亜種の誕生と激動の1990年代前半, "Deflate"アルゴリズム

1989年2月1日にPKZIP-0.9としてZIPファイルフォーマットが公開され、早速互換ソフトが開発された。それがInfo-ZIPであり、1989年の5月に最初のバージョンが公開されている。同年の9月にはPKZIP 1.01で追加された"IMPLODE"メソッドに対応したInfo-ZIPバージョン2.0がリリースされ、さらに同年12月、UNIXへポーティングしたInfo-ZIPがリリースされた（PKZIP, Info-ZIPは当初DOS用のツールだった）。
間を空けて1993年、PKZIP-2.0で"LZ77"系列の"Deflate"圧縮アルゴリズムがKatzにより追加され、Info-ZIPも追随する。
1994-1995年はInfo-ZIPにとって重要な年となる。この年に、多数のミニコンやメインフレームにInfo-ZIPが移植され、PKZIPの機能を次々と取り込んでいく。結果として、多くのミニコン・メインフレームユーザにとってわざわざシェアウェアであるPKZIPを購入する動機が消えてしまい、代わりにInfo-ZIPが事実上の標準として君臨する事になった。
現在のLinux/UNIXに含まれる"zip", "unzip"コマンドはInfo-ZIPのプログラムである。

(CentOS 5.2)
$ rpm -qi zip
Name        : zip                          Relocations: (not relocatable)
Version     : 2.31                              Vendor: CentOS
...
URL         : http://www.info-zip.org/pub/infozip/Zip.html
Summary     : PKZIP と互換性があるファイル圧縮/パッケージ作成ユーティリティ

PKZIP本家の方は1990年-1999年までは大きな動きが無い。GUIフロントエンドのWinZip(シェアウェア)が1990年前半に開発されたりしている。
2000年には"7-zip"の開発が始まるが、こちらは独自の"7z"という書庫形式を使っており、PKZIPとは直接の関係はない。ただしZIPを含む多数のアーカイブ・圧縮形式に対応していたり、また開発者のIgor Pavlov自身がLZMAという"LZ77"由来の圧縮アルゴリズムを先行開発しているなど、"LZ"ファミリー由来のアーカイブソフトである事は間違いない。

まとめと参考資料

ZIPは圧縮ファイルデータやファイルアーカイブの為の柔軟なファイルフォーマットの一つであり、1989年にPKZIPとして、Phil Katzにより誕生した。
PKZIPはMS-DOS用のシェアウェアだったが、ZIPファイルフォーマット自体は公開された為Info-ZIPのような互換フリーソフトが開発され、Info-ZIPはミニコンやメインフレームの世界で広がっていった。
PKZIP自体はシェアウェアであり、Windowsプラットフォームに乗り遅れた事もあり標準の地位は確保できなかったが、今日様々なアーカイブソフトやOSレベルでZIPがサポートされている。

PKZIP, WinZIP:

ZIPファイルフォーマット:

"ＴＮＫソフトウェア - 私的ZIPファイル研究所"
- http://www.tnksoft.com/reading/zipfile/index.php
http://ja.wikipedia.org/wiki/ZIP_%28%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB%E3%83%95%E3%82%A9%E3%83%BC%E3%83%9E%E3%83%83%E3%83%88%29
http://en.wikipedia.org/wiki/ZIP_%28file_format%29

Info-ZIP:

http://www.info-zip.org/
- http://en.wikipedia.org/wiki/Info-ZIP

7-Zip:

http://www.7-zip.org/

もう一つの流れ：gzip, zlib

1985年、LZWの特許公開とLZWを使ったcompressツールの開発がぶつかり、compressツールを使うにはロイヤリティを支払う必要が生じた。このため折角開発されたcompressであったが、普及しない状態が続いていた。
しかし、1993年のPhil Katzによる"Deflate"圧縮アルゴリズムの発表によりcompressツールの代替プログラムの開発が始まる。

gzip

gzipは"GNU zip"の略称であり、"Deflate"圧縮アルゴリズムを使ったファイルフォーマットである。アーカイブフォーマットとしても利用できるZIPに対し、アーカイブファイル自体はar/shar/tarなどの既存のUNIXツールで作成し、gzipはそれを圧縮するだけのツールという位置づけだった。
フォーマットとしては

ヘッダ + メタ情報(ファイル名, コメントなど) + 圧縮ファイル本体 + フッタ

が一つの圧縮ファイルデータを構成する。
複数のファイルを圧縮する場合は、上記のデータ単位が単純に連続するだけ、というフォーマットである。ZIPフォーマットとは違い、連続するデータの先頭や末尾に好きなデータを加える事は出来ない。
gzipとzipは"Deflate"圧縮アルゴリズムをサポートしている点は共通だが、フォーマットとしては完全に別物でありプログラムが開発されたプラットフォーム・背景も異なる。

http://www.gzip.org/
- http://en.wikipedia.org/wiki/Gzip
- http://ja.wikipedia.org/wiki/Gzip

gzipが生まれたのは1992年10月のVersion 0.1, アルファ版リリースである。Jean-Loup Gailly と Mark Adler らによる。Mark Adlerは前掲のInfo-ZIPの開発者でもあった。

・・・少し疑問なのだけど、PKZIP-2.0 with "Deflate"は1993年発表、とen.wikipediaでは記載されている。一方でCentOS5.2に入っているgzipのChangeLogでは1992年10月31日がgzipのファーストリリースとされている。
/usr/share/doc/gzip-1.3.5/ChangeLog:

Sat Oct 31 12:46:00 1992  Jean-loup Gailly  (jloup@chorus.fr)

    * Alpha version 0.1 released (under time pressure), so it's not
      much tested, sorry.

どちらが先だったのか、それかPhil KatzとJean-Loup Gailly, Mark Adlerの間で何らかのやりとりがあり、ある程度"Deflate"アルゴリズムが共有されていたかのか、そこだけ謎である。

とまれ、1993年2月にはgzipのVersion 1.0 がリリースされる。"GNU zip"の名の通り、ライセンスはGPLである。

zlib

その後、gzipの主要開発者であるJean-Loup Gailly と Mark Adler らは"Deflate"圧縮アルゴリズム処理だけをライブラリとして実装し、"zlib"として商用利用も可能な緩いライセンスで公開する。

http://zlib.net/
- http://en.wikipedia.org/wiki/Zlib
- http://ja.wikipedia.org/wiki/Zlib

1995年5月に zlib の最初の公開バージョンである 0.9 がリリースされる。開発自体はその前から行われていたようだが、正確な日付は不明。CentOS 5.2の /usr/share/doc/zlib-devel-1.2.3/ChangeLog を確認しても、ChangeLogのVersion 0.3 - 0.5までは日付が振られていない。0.6になって初めて、"(11 April 95)"として1995年4月11日の日付があらわれている。
最終的には1996年の5月に以下の3つのRFCとしてzlib, "Deflate"圧縮アルゴリズム, gzipファイルフォーマットが公開される。

zlibの圧縮データフォーマット : RFC1950, http://tools.ietf.org/html/rfc1950
"Deflate"圧縮アルゴリズム : RFC1951, http://tools.ietf.org/html/rfc1951
gzipファイルフォーマット : RFC1952, http://tools.ietf.org/html/rfc1952

gzip, zlib, zipは独立してシステムにインストール出来る

CentOS5.2の場合のパッケージ依存状況と、lddによる共有ライブラリリンク状況を確認する。結論として、gzip/zlib/zip(unzip)間のパッケージ依存は存在せず、それぞれ独立してインストール可能。

なおFreeBSD/OpenBSDのmanページを調べたところ、gzipは標準で入っている(FreeBSD 5.4, OpenBSD 4.6)。ただしzlibが標準で入っているかは不明。また、Info-ZIPのzip/unzipについてはFreeBSD/OpenBSDともにPortsからインストールすることになっていて、2009/11現在、FreeBSDの場合は "archivers/zip"(3.0), "archivers/unzip"(6.0) としてInfo-ZIPのものが登録されている。
余談だがFreeBSDのPortsの"security"カテゴリに"find_zlib"というのが登録されており、説明には"zlibコードが静的リンクされたファイルを探す為のシェルスクリプト"とある。以前、zlibでfree()を二重で行っていたための脆弱性が見つかった事がありそれに関連していると思われる。

CentOS5.2上のgzipのパッケージ依存状況と、lddによる共有ライブラリリンク状況:

$ which gzip
/bin/gzip
$ ldd /bin/gzip
        linux-gate.so.1 =>  (0x0041b000)
        libc.so.6 => /lib/libc.so.6 (0x00b45000)
        /lib/ld-linux.so.2 (0x00a83000)
        # zlibへのリンクはされていない
$ rpm -qR gzip
/bin/sh
/bin/sh
/bin/sh
/sbin/install-info
less
libc.so.6
libc.so.6(GLIBC_2.0)
libc.so.6(GLIBC_2.1)
libc.so.6(GLIBC_2.2)
libc.so.6(GLIBC_2.3)
libc.so.6(GLIBC_2.3.4)
libc.so.6(GLIBC_2.4)
mktemp
rpmlib(CompressedFileNames) <= 3.0.4-1
rpmlib(PartialHardlinkSets) <= 4.0.4-1
rpmlib(PayloadFilesHavePrefix) <= 4.0-1
rtld(GNU_HASH)

→ zlibが無くてもインストール可能。

CentOS5.2上のzlibのパッケージ依存状況と、lddによる共有ライブラリリンク状況:

$ rpm -qR zlib
/sbin/ldconfig
/sbin/ldconfig
libc.so.6
libc.so.6(GLIBC_2.0)
libc.so.6(GLIBC_2.1)
libc.so.6(GLIBC_2.1.3)
libc.so.6(GLIBC_2.3.4)
libc.so.6(GLIBC_2.4)
libz.so.1
rpmlib(CompressedFileNames) <= 3.0.4-1
rpmlib(PayloadFilesHavePrefix) <= 4.0-1
rtld(GNU_HASH)
$ rpm -qR zlib-devel
libz.so.1
rpmlib(CompressedFileNames) <= 3.0.4-1
rpmlib(PayloadFilesHavePrefix) <= 4.0-1
zlib = 1.2.3
$ ldd /usr/lib/libz.so.1.2.3
        linux-gate.so.1 =>  (0x005b8000)
        libc.so.6 => /lib/libc.so.6 (0x00b45000)
        /lib/ld-linux.so.2 (0x00a83000)

→ 単独でインストール可能

CentOS5.2上のzip(Info-ZIP)のパッケージ依存状況と、lddによる共有ライブラリリンク状況:
※圧縮(zip)と解凍(unzip)でSRPMの段階から独立している

$ ldd /usr/bin/zip
        linux-gate.so.1 =>  (0x00eab000)
        libc.so.6 => /lib/libc.so.6 (0x00b45000)
        /lib/ld-linux.so.2 (0x00a83000)
$ rpm -qR zip
libc.so.6
libc.so.6(GLIBC_2.0)
libc.so.6(GLIBC_2.1)
libc.so.6(GLIBC_2.2)
libc.so.6(GLIBC_2.3)
libc.so.6(GLIBC_2.3.4)
libc.so.6(GLIBC_2.4)
rpmlib(CompressedFileNames) <= 3.0.4-1
rpmlib(PayloadFilesHavePrefix) <= 4.0-1
rtld(GNU_HASH)

$ ldd /usr/bin/unzip
        linux-gate.so.1 =>  (0x00c41000)
        libc.so.6 => /lib/libc.so.6 (0x00110000)
        /lib/ld-linux.so.2 (0x00a83000)
$ rpm -qR unzip
/bin/sh
libc.so.6
libc.so.6(GLIBC_2.0)
libc.so.6(GLIBC_2.1)
libc.so.6(GLIBC_2.2)
libc.so.6(GLIBC_2.3)
libc.so.6(GLIBC_2.3.4)
libc.so.6(GLIBC_2.4)
rpmlib(CompressedFileNames) <= 3.0.4-1
rpmlib(PartialHardlinkSets) <= 4.0.4-1
rpmlib(PayloadFilesHavePrefix) <= 4.0-1
rtld(GNU_HASH)

bzip2について

Linux kernelのアーカイブファイルでも使われている("*.tar.bz2")圧縮ツール、bzip2について、簡単にWikipediaを元に抜き書きしておく。圧縮性能や速度についての評価や詳細は踏み込まない。

作者は Julian Seward 。名前に"zip"が含まれているが、"LZ"ファミリーの圧縮アルゴリズムを使っているわけではない。ブロックソート法（バロウズ-ホイラー変換）、MTF (Move-To-Front) 法、ハフマン符号化法を活用している。また"gzip"と同様にあくまでも圧縮ツールの位置づけであり、ar/tar/sharなどにより作成されたアーカイブファイル１つ分を処理する事を目的としている。
"bzip2"という名前から、"bzip1"or"bzip"があるのではと推測されるが、実際に"bzip"という名前で開発されていた時期がある。しかし"bzip"で圧縮アルゴリズムに使っていた算術符号化の基本アルゴリズムがIBM系の企業により保有されていた為、特許問題を避ける為にハフマン符号化に置き換えたものが現在の"bzip2"である。

FreeBSDのPortsで"bzip"時代のパッケージを見つける事が出来る。"bzip"の最後のバージョンは"bzip-0.21"となっており、説明を要約すると"米国の幾つかの算術符号化に関する特許を侵害している可能性があるので、bzip2の方を使って下さい"とある。

http://www.freebsd.org/cgi/url.cgi?ports/archivers/bzip/pkg-descr

なおbzip時代のソースが、Portsが生きている以上は入手可能となっているようだ：

http://www.freebsd.org/cgi/pds.cgi?ports/archivers/bzip

実際にダウンロードしてREADMEを確認してみたところ、末尾にbzip時代のバージョンとリリース日らしきものが見つかった。

Julian Seward
Manchester, UK
18 July 1996 (version 0.15)
25 August 1996 (version 0.21)

英語版のWikipediaでは、"bzip"のページに「Seward made the first public release of bzip2, version 0.15, in July 1996.」とある。その後"bzip"は0.21の1996/8月で開発が停まり、同じ作者により"bzip2"として、同じく1996年に生まれ変わる事になる。
"bzip2"のCHANGESファイルを見ると、"bzip2"の最初のバージョンは"0.9.0"だった事が確認できた。

 ------------------------------------------------------------------
 This file is part of bzip2/libbzip2, a program and library for
 lossless, block-sorting data compression.

 bzip2/libbzip2 version 1.0.5 of 10 December 2007
 Copyright (C) 1996-2007 Julian Seward <jseward@bzip.org>

 Please read the WARNING, DISCLAIMER and PATENTS sections in the 
 README file.

 This program is released under the terms of the license contained
 in the file LICENSE.
 ------------------------------------------------------------------


0.9.0
~~~~~
First version.
...

参考：

http://www.bzip.org/
- http://en.wikipedia.org/wiki/Bzip
- http://ja.wikipedia.org/wiki/Bzip2
"bzip"の時に使われていた算術符号化について
- http://en.wikipedia.org/wiki/Arithmetic_coding
- http://ja.wikipedia.org/wiki/%E7%AE%97%E8%A1%93%E7%AC%A6%E5%8F%B7

gzipファイルフォーマットについての極々簡単な確認

gzipは1ファイル単位で圧縮するのが基本で、複数ファイルを操作する時は単純に圧縮された1ファイル分のレコードをつなげるだけとなる。簡単なファイルで確認してみる。実際にファイルのヘッダーを解析したりはせずに、単純にMD5ハッシュを見てバイナリレベルで差分がない事を確認するに留める。

１．適当なファイルを２つ用意する。

$ echo "Hello, World AAA." > file1.txt
$ echo "Hello, World BBB." > file2.txt

２．ファイルをまとめて指定して圧縮したのと、分けて圧縮したのをcatでつなげたものを作る。

$ gzip -c file1.txt > file1.gz
$ gzip -c file2.txt > file2.gz
$ gzip -c file1.txt file2.txt > files.gz
$ cat file1.gz file2.gz > files2.gz

３．MD5値を確認する。同じなので、圧縮したのをcatしても、ファイルをまとめて引数で指定しても同じファイルが出来る事を確認した。

$ md5sum files.gz
f19efc7a16e6a273925d8be91b5d7176  files.gz
$ md5sum files2.gz
f19efc7a16e6a273925d8be91b5d7176  files2.gz

後書き：

zip/gzip/zlibの区別をはっきりさせたいというのが最初の目的で、それは完全に達成できたと思う。それにしても、Wikipediaの内容を抜き書きしてまとめるだけでも一苦労だった。Wikipediaやそれぞれのソフトに付随するドキュメントに目を通しても、当然ながら自身の担当範囲しか書いていない為、PKZIPとARC形式、LZファミリーの関係、LZWの特許とcompressの関係からgzip/zlibへの流れなど全体の関連や大雑把な歴史を理解するのに手間取る。

zip/gzip/zlib/bzip2についての頭の中のもやもやを、この記事ですっきり整理できたなら幸いです。