ジップ圧縮のコンセプトは何ですか？

Question

ジップ圧縮のコンセプトは何ですか？私は空き領域などを取り除くという概念を理解することができますが、圧縮解除中に空き領域をどれくらい増やす必要があるかを言うために何かを追加する必要があります。

バイトストリームを圧縮する基本的なプロセスは何ですか？

Answer 1

開始するには、Huffmanの圧縮スキームを参照するのがよいでしょう。ハフマンの背後にある基本的な考え方は、あるファイルではいくつかのバイトが頻繁に出現し、他のバイトは平文ファイルでは何も出現しないということです。むしろ、8ビットを使ってすべてのバイトをエンコードし、最も一般的な文字をエンコードするために短いビットシーケンスを使用し、あまり一般的でない文字をエンコードするために長いシーケンスを使用してください（これらのシーケンスはハフマンツリーを作成することによって決定されます）。

キャラクタの頻度に基づいてファイルをエンコード/デコードするためのハンドルを取得したら、単語「周波数」で作業を開始すると想像してください。「それら」を4文字のシーケンスとしてエンコードするのではなく、その頻度のために単一の文字になるようにし、それをハフマンツリー内のそれ自身の葉に割り当てることを可能にする。これは、ZIPやその他のロスレスタイプの圧縮の基礎になります。ファイル内の一般的な「単語」（バイトのシーケンス）（1バイトだけのシーケンスを含む）を検索し、ツリーを使用してそれらをエンコードします。 zipファイルはツリーの再構成とファイルの残りの部分のデコードを許可するツリー情報（各シーケンスのコピーとそれが現れる回数）を含める必要があります。

はフォローアップ：

をより良い元の質問に答えるために、可逆圧縮の背後にある考え方は、空きスペースを削除することはあまりありませんが、redundent情報を削除します。

音楽の歌詞を保存するデータベースを作成した場合、複数回繰り返されるコーラスの保存に多くのスペースが使用されていることがわかります。そのスペースをすべて使用するのではなく、コーラスの最初のインスタンスの前に単にCHORUSという単語を置き、コーラスを繰り返すたびにコーラスをプレースホルダとして使用するだけです（実際はこれはかなりアイデアですLZW圧縮の後ろ - LZWの曲の各行の前に番号が表示されます。曲が後で繰り返される場合は、番号だけが表示されます）

Answer 2

圧縮の概念は基本的には統計的です。一連のバイトがある場合、実際にはバイトNがXになる可能性は、以前のバイト0.N-1の値の分布に依存します。圧縮を行わない場合、可能な値Xごとに8ビットを割り当てます。圧縮すると、各値Xに割り当てられるバイト数は、推定される確率p（N、X）に依存します。

たとえば、シーケンス「aaaa」を指定すると、圧縮アルゴリズムはp（5、a）に高い値を割り当て、p（5、b）には低い値を割り当てることができます。 p（X）がハイのとき、Xに割り当てられたビットストリングは短くなります.p（X）がローのとき、長いビットストリングが使用されます。このようにして、p（N、X）が良好な推定値である場合、平均ビットストリングは8ビットより短くなる。

Answer 3

基本的な考え方は、8ビットを使用して各バイトを表現するのではなく、より頻繁に発生するバイトまたは一連のバイトに対して短い表現を使用することです。例えば

、あなたのファイルは、バイト0×41（A）でのみ構成されている場合は、代わりに8ビットのシーケンスとしてそれを表すの1ビット列0にそれを短縮01000001、16回繰り返します。ファイルは0000000000000000（16個の0）で表すことができます。従って、バイト0x41が16回繰り返されたファイルは、バイト0x00が2回繰り返されたファイルで表すことができます。

ここでは、このファイル（0x41を16回繰り返したもの）のビット01000001は、ビット0を超える追加情報を伝えていません。したがって、この場合、余分なビットを捨ててより短い表現を得る。

これは、圧縮の背後にあるコアアイデアです。別の例として

、8つのバイトパターン

0x41 0x42 0x43 0x44 0x45 0x46 0x47 0x48 

を考えると、今それを2048回繰り返します。上記の方法に従う一つの方法は、3ビットを用いてバイトを表現することである。

000 0x41 
001 0x42 
010 0x43 
011 0x44 
100 0x45 
101 0x46 
110 0x47 
111 0x48 

今、私たちは、2048回繰り返し（これは3バイトパターン0x05 0x39 0x77ある）00000101 00111001 01110111により上記バイトパターンを表すことができます。

しかし、より良いアプローチは、単一のビット0でバイトパターン

0x41 0x42 0x43 0x44 0x45 0x46 0x47 0x48 

を表現することです。上記のバイトパターンを0で2048回繰り返すと、0x00が256回繰り返されます。今、私たちは唯一の

0 -> 0x41 0x42 0x43 0x44 0x45 0x46 0x47 0x48 

辞書を保存する必要があり、バイトパターン0x00は256回繰り返し、我々は（辞書を法）256バイトに16,384バイトのファイルを圧縮しました。

これは、圧縮の仕組みを簡単に示しています。ビジネス全体は、与えられたファイル内のバイトシーケンスとバイトシーケンスの簡潔で効率的な表現を見つけることにまで至ります。それは簡単な考えですが、詳細（表現を見つけること）はかなり難しいものです。

例を参照してください：あなたがwikipに行く必要があるよう

1. Data compression
2. Run length encoding
3. Huffman compression
4. Shannon-Fano coding
5. LZW