ａｌｇｏｒｉｔｈｍ．ｄｏｃの日本語訳です。
----------------------------------------------------------------------------
1.アルゴリズム
zip と gzip によって使われている圧縮アルゴリズムは、LZ77（Lempel-Ziv 1977,
下記の参考文献を参照すること）のバリエーションである。それは、入力データの中
の重複している文字列を発見する。ある文字列が２度目に出てきた時には、以前の文
字列への（変位、長さ）という組の形式でのポインタに置き換えられる。変位は、
32K バイトに、長さは 258 バイトに制限されている。文字列が以前の 32K バイトの
中にまったく出てこなかったものならば、リテラルバイトの連続として出力される。
（この記述の中で、「文字列」はバイトの任意の連続として解釈されるべきものであ
り、表示可能なキャラクタに制限されるものではない。）
リテラル、あるいは一致した長さは、ひとつのハフマンツリーに圧縮され、一致場
所の変位は、別のツリーに圧縮される。それらのツリーは各ブロックの先頭に、コン
パクトな形式で格納される。ブロックはいかなるサイズもとることができる（ひとつ
のブロックの圧縮データが使用可能メモリギリギリになる場合を除く）。ひとつのブ
ロックは、zip が新しいツリーで別のブロックを始めた方がよいだろうと決定した時
に、終了する。（これは、compress にいくらか似ている。）
重複した文字列はハッシュテーブルを用いることによって発見される。長さが３の
すべての入力文字列は、ハッシュテーブルに挿入される。ハッシュインデックスは、
次の３バイトを計算する。もし、このインデックス用のハッシュチェーンが空ではな
かったならば、チェーンの中のすべての文字列は、現在の入力文字列と比較され、最
も長い一致文字列が選ばれる。
ハッシュチェーンは、最近の最も大きい文字列の開始場所をサーチする。それは、
変位を小さくするのに有利で、それゆえ、ハフマン符号化が有利になるようにするた
めである。ハッシュチェーンは単独にリンクされている。ハッシュチェーンからは、
いかなる削除もなく、このアルゴリズムは古すぎる一致文字列を単純に放棄するだけ
である。
最悪の場合の状況を避けるため、非常に長いハッシュチェーンは、ランタイムオプ
ション（zip -1 からzip -9 まで）によって決定される、ある程度の長さに勝手に切
り詰められる。それで、zip は常に１番長い可能な一致文字列を発見するわけではな
いが、一般に、十分に長い一致文字列を発見する。
zip はまた、怠惰な評価メカニズムによって一致文字列の選択を延期する。長さＮ
の一致文字列が見つかったあとで、zip は次の入力文字列の中からもっと長い一致文
字列をサーチする。もし、より長い一致文字列が見つかったならば、以前の一致文字
列は、切り詰めて１文字の長さにされ、（それゆえ、単独のリテラルバイトが生成さ
れる）それ以後は、そのより長い一致文字列が出力される。そうでなければ、元の一
致文字列が維持され、次の一致文字列サーチは、Ｎステップ後になってからのみ、試
みられる。
怠惰な一致文字列評価はまた、ランタイムパラメータに従属している。もし、現在
の一致文字列が十分に長かったならば、zip はより長い一致文字列のサーチを減らし、
それゆえ、プロセス全体がスピードアップする。もし、圧縮率が速度よりも重要なら
ば、zip は最初の一致文字列が既に十分長かったとしても、完全な２番目のサーチを
試みる。
怠惰な一致文字列評価は最高速圧縮モード（スピードオプション -1 から -3）で
は機能されない。これらの高速モードでは、新しい文字列は一致文字列が見つからな
い場合、あるいは一致文字列が長すぎない場合のみ、ハッシュテーブルに挿入される。
これは圧縮比を悪くしてしまうが、より少ない挿入とサーチの両方によって、時間を
節約する。
2. gzip ファイルのフォーマット
pkzip フォーマットは様々なヘッダの中で、多くのオーバーヘッドを課していて、
アーカイバにとっては便利であったが、１つのファイルだけを圧縮する時には、必要
ない。gzip はずっとシンプルな構造を使っている。数字はリトルエンディアンフォー
マットの中にあり、ビット 0 が最下位ビットである。１つの gzip ファイルは、圧
縮されたメンバーの連続である。各メンバーは以下の構造を持っている。
2 バイト マジックヘッダ 0x1f, 0x8b (\037 \213)
1 バイト 圧縮方法 (0..7 予約済み, 8 = 圧縮する)
1 バイト フラグ
bit 0 がセットされていたら : ファイルは多分アスキー文字のテキスト
bit 1 がセットされていたら : 複数部分からなる gzip ファイルの連続
bit 2 がセットされていたら : 特別な領域が存在する
bit 3 がセットされていたら : 元のファイル名が存在する
bit 4 がセットされていたら : ファイルのコメントが存在する
bit 5 がセットされていたら : ファイルは暗号化されている
bit 6,7 : 予約済み
4 バイト Unix フォーマットのファイル更新時刻
1 バイト 特別なフラグ（圧縮方法に依存する）
1 バイト 圧縮が実行されるところのオペレーティングシステム
2 バイト オプションによるパートナンバー（２番目のパートが１である）
2 バイト オプションによる特別な領域の長さ
? バイト オプションによる特別な領域
? バイト オプションによる元のファイル名、\0 で終っている
? バイト オプションによるファイルのコメント、\0 で終っている。
12 バイト オプションによる暗号化ヘッダ
? バイト 圧縮されたデータ
4 バイト CRC 32 ビット
4 バイト 非圧縮時の入力サイズを 2^32 で割った時の余り
このフォーマットはいかなる後方検索、非圧縮時のサイズに関する予備知識、出力
メディア上で利用可能なサイズに関する予備知識もなしに、単一パスでの圧縮を許す
ように設計されている。もし、入力が正規のディスクファイルから来なかったら、ファ
イルの更新時刻は、圧縮が始まった時の時刻にセットされる。
タイムスタンプは、１つの gzip ファイルがネットワークを越えて送られてきた時
に、主に、便利である。この場合、持ち主の属性は維持せざるを得ないだろう。局所
的な場合、持ち主の属性はファイルの圧縮、展開時に、gzip によって保存される。
0 のタイムスタンプは無視される。
フラグのビット 0 は単にオプションによる表示であり、入力データのちょっとし
た先読みによってセットされうるものである。疑わしい場合には、このフラグはクリ
アされ、バイナリデータであることを指し示す。アスキーテキストとバイナリデータ
に関して、異なったファイルフォーマットを持つシステムに対しては、展開ツールは、
適切なフォーマットを選ぶために、このフラグを利用することができる。
特別な領域は、もし存在するなら、各々が以下のフォーマットを持つ、１つ、ある
いはそれ以上のサブ領域から構成されなければならない。
サブ領域 ID : 2 バイト
サブ領域のサイズ : 2 バイト（リトルエンディアンフォーマット）
サブ領域のデータ
サブ領域 ID は記憶を助ける値を持つ２文字から構成されることができる。そのよ
うな ID （のアイデア）があったら、jloup@chorus.fr までメールを送って下さい。
2 バイト目が 0 の ID は将来の利用のために予約されている。以下の ID が定義さ
れている：
Ap (0x41, 0x70) : Apollo ファイルタイプ・インフォメーション
サブ領域のサイズは、サブ領域のデータのサイズであり、ID やサイズそのものは
含まない。"特別な領域の長さ" のフィールドは、特別な領域のトータルサイズであ
り、サブ領域の ID やサイズも含んでいる。
いかなる圧縮フォーマットであっても、圧縮されたデータの実際のサイズに関係な
く、圧縮されたデータの終わりを判別するのは可能に違いない。もし、圧縮されたデー
タがひとつのファイルに入り切らない（特にディスケットの場合）場合、上で述べた
ように各部分はヘッダを持って始まっているが、最後の部分しか CRC32 と非圧縮時
のサイズを持っていない。展開ツールは複数部分からなる圧縮ファイルの追加データ
を入力するように促す。複数部分が独立に展開できて、ひとつの部分が破損していて
も、部分的なデータは回復できるというのは望ましいことだが、強制ではない。これ
は、非圧縮状態がある部分からほかの部分まで保たれている時のみ、可能である。圧
縮タイプ依存フラグはこれを指し示している。
もし圧縮されたファイルが大文字／小文字を区別しないファイルシステム上のもの
だったならば、元の名前領域は強制的に小文字となる。もし、データが標準入力から
圧縮されたものならば、元のファイル名はない。
たとえ、圧縮ファイルの方が元のファイルより少々大きくなるとしても、圧縮は常
に実行される。最悪の場合、増加分は gzip ファイルのヘッダの数バイト + 32KB の
ブロックごとに 5 バイトであり、大きなファイルに対しては、増加率は 0.015% で
ある（訳者註:ヘッダの大きさは無視でき、5byte / 32KB ≒ 0.015%である）。した
がって、実際のディスクブロックの使用量は、ほとんどの場合、増加しない。
暗号化は、zip 1.9 のそれと同じである。暗号化のチェックには、デコードされた
暗号化ヘッダの最後のバイトが０かどうかを調べる。暗号化されたファイルのタイム
スタンプは、ランダムヘッダの構造についての手掛かりを与えるのを避けるために、
ゼロにセットされる。
Jean-loup Gailly
jloup@chorus.fr
参考文献 :
[LZ77] Ziv J., Lempel A., "A Universal Algorithm for Sequential Data
Compression", IEEE Transactions on Information Theory", Vol. 23, No. 3,
pp. 337-343.
APPNOTE.TXT documentation file in PKZIP 1.93a. It is available by
ftp in ftp.cso.uiuc.edu:/pc/exec-pc/pkz193a.exe [128.174.5.59]
展開には "unzip pkz193a.exe APPNOTE.TXT" を使うこと。
(註: unzip であって gunzip ではない。)
----------------------------------------------------------------------------
algorithm.doc を訳してみました。英語は苦手だし、圧縮にも詳しくないので、誤
訳や意味不明の珍訳があちこちにあります。(^_^;)
COPYRIGHT
本邦訳は、ArctanX こと田辺英昭が著作権を保持しますが、GPL に準拠した配
布を認めます。
★gzipのページに戻る
arctanx@hauN.org