Unix compress と LZW

歴史的な Unix compress ユーティリティは、慣例的に .Z という名前のファイルを書き出します。これは DEFLATE ではなく、LZW 系の辞書符号化方式を使用します。uncompress と zcat は、この形式を提供するシステム上で互換性のあるコマンドラインインターフェースを公開しています。

LZW の初期化と同期 #

LZW エンコーダーは、1 バイトのアルファベット用エントリから開始します。現在のフレーズ w を保持し、次のバイト k を読み取り、そのフレーズが w + k 辞書に存在する間は処理を続けます。そのフレーズが存在しない場合は、w のコードを出力し、w + k を追加して、k から開始します。デコーダーは各コードに対応する文字列を出力し、最初のコードの後は、直前に復号した文字列と現在の文字列の先頭バイトを連結したエントリを追加します。入力を使い果たした後、エンコーダーは最後のフレーズを出力します。したがって、エンコーダーとデコーダーは、1 コード遅れて同じエントリを追加します。

よく知られた KwKwK のケースは、コードが次の辞書インデックスと等しい場合に発生します。このときデコーダーはそれを previous + first(previous) として展開します。このケースを拒否すると有効なストリームを拒否することになり、次のインデックスを超えるコードを受け入れると辞書の同期が失われます。

.Z ビットストリーム #

.Z ストリームは 1f 9d とフラグバイトで始まります。下位 5 ビットは最大コード幅を指定し、通常は 9 ～ 16 ビットです。ビット 7 はブロックモードを有効にします。残りの予約ビットは、実装の互換性規則に従って処理する必要があります。コードは 9 ビットから始まり、辞書が現在の幅の容量に達すると幅が広がります。ブロックモードでは、コード 256 は CLEAR です。エンコーダーはこのコードを出力してエントリを破棄し、初期アルファベットで再開できます。デコーダーは同じ時点でリセットし、その後 9 ビットのコードを再開する必要があります。非ブロックモードのストリームには、そのリセットコードはありません。

コード幅の遷移規則は .Z 方言の一部であるため、読み取り側は次のコードから推測するのではなく、形式で指定されたタイミングに従う必要があります。歴史的な実装はエッジケースで異なるため、対象の compress 実装との相互運用性テストが適切です。

互換性と運用 #

LZW の特許は compress の導入に影響を与えました。関連する特許は失効していますが、古いアーカイブやプラットフォーム固有のデコーダーは、依然として互換性上の制約になります。新しいデータには、プロトコルによって選択された形式を使用してください。tar はファイル名とメタデータを格納し、コンプレッサーはバイトストリームを変換するため、.tar.Z は .Z で圧縮された tar アーカイブを意味します。

file backup.tar.Z
uncompress -c backup.tar.Z | tar -tvf -
compress -c source.bin > source.bin.Z
zcat source.bin.Z | sha256sum

.Z 形式には、gzip のトレーラーに相当する必須のエンドツーエンドチェックサムがありません。デコーダーは、切り詰められたストリームや破損したストリームから、もっともらしいバイト列を生成する可能性があります。そのため、変換後も元のアーカイブを保持し、外部ダイジェストまたは既知のファイル長を検証してください。gzip は DEFLATE を使用し、各メンバーに CRC-32 と非圧縮サイズを記録するため、通常のファイル転送では破損の報告能力が高くなります。ただし、gzip と .Z は相互に置き換え可能なストリームではありません。

参考資料 #

• FreeBSD compress(1) マニュアル（.Z オプションとブロックモードを含む）。
• T. A. Welch、「A Technique for High-Performance Data Compression」、Computer、1984 年。
• RFC 1952: gzip ファイル形式