c - LZW 圧縮を使用して ZIP ファイルを圧縮すると、サイズが大きすぎる圧縮ファイルが作成される

Question

LZW圧縮方法（次のリンクで提供されるコード）を使用してzipファイルを圧縮しようとしましたが、

http://rosettacode.org/wiki/LZW_compression#C

エンコードされたファイルの長さが元のファイル サイズよりも長すぎますが、その理由は何ですか? リアルタイムで何が起こっているのかを理解するのを手伝ってください。

Answer 1

可逆圧縮ですべてのファイルを短いファイルに圧縮することは不可能です。

これは、長さがNバイトのファイルが 256 ^{N 個}ありますが、 Nバイトよりも短い(256 ^N -1)/255 ファイルがあるためです。したがって、すべてのファイルを短いファイルにマップできるわけではありません。

それ以上に、ファイルが短くなった場合、それを可能にするために、一部の短いファイルはその場所をあきらめなければなりませんでした。そのため、一部のファイルは大きくなる必要があります。

可逆圧縮は、人間が作成した一般的なファイルの一般的なパターンを認識し、可能性の高い長いバイト シーケンスを短いシーケンスに変換することによって機能します。これの代償は、一部のシーケンスが長くなることです。設計の目標は、典型的なファイルを圧縮することですが、非典型的なファイルは長くする必要があります。

圧縮が機能すると、冗長な情報がファイルから削除され、出力はランダム データに似たものになります。その後、出力をさらに圧縮することはできません。