zip壓縮背後的概念是什麼？

Question

zip壓縮背後的概念是什麼？我可以理解刪除空白空間等概念，但可能需要添加一些內容來說明在解壓縮過程中需要添加多少/哪些空閒空間？

什麼是壓縮字節流的基本過程？

Answer 1

開始的一個好地方是查找Huffman壓縮方案。 huffman背後的基本思想是，在給定的文件中，某些字節出現得比較頻繁，其他字節（明文文件中很多字節根本不會出現）。而是花費8位來編碼每個字節，爲什麼不使用較短的位序列來編碼最常見的字符，而使用較長的序列來編碼較不常見的字符（這些序列由創建霍夫曼樹來確定）。

一旦您掌握瞭如何使用這些樹來根據字符頻率對文件進行編碼/解碼，想象一下，然後開始處理文字頻率 - 而不是將它們編碼爲4個字符的序列，爲什麼不考慮它由於其頻率而成爲單個字符，從而允許其在霍夫曼樹中分配其自己的葉。這或多或少是ZIP和其他無損類型壓縮的基礎 - 它們在文件中尋找常見的「字」（字節序列）（包括足夠常見的只有1字節的序列）並使用樹來編碼它們。然後，zip文件只需要包含樹信息（每個序列的副本和出現的次數），以允許重構樹並解碼文件的其餘部分。

追問：

爲了更好地回答原來的問題，背後無損壓縮的想法是不是要刪除空的空間，但除去redundent信息。

如果你創建了一個數據庫來存儲音樂歌詞，你會發現很多空間被用來存儲重複多次的合唱。你可以簡單地將CHORUS放在合唱線的第一個實例之前，而不是使用所有這些空間，然後每次重複合唱時，只需使用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

基本概念是，不是使用八位來表示每個字節，而是使用更短的表示來更頻繁地發生字節或字節序列。

例如，如果文件僅僅由字節的0x41的（A）重複16次，然後代替表示它作爲8位的序列01000001縮短到1比特序列0。然後該文件可以由0000000000000000（十六個0 s）表示。那麼重複十六次的字節0x41的文件可以由重複兩次的由字節0x00組成的文件來表示。

所以我們在這裏是這個文件（0x41重複十六次）01000001位不傳達任何額外的信息在0位。所以，在這種情況下，我們扔掉無關位來獲得更短的表示。

這是壓縮背後的核心思想。

再舉一個例子，考慮八個字節模式

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

，現在重複2048次。遵循上述方法的一種方式是使用三位來表示字節。

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

現在，我們可以通過00000101 00111001 01110111表示上述字節圖案（這是三字節圖案0x05 0x39 0x77）重複2048次。

但更好的方法是由單個位0代表字節模式

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

。然後我們可以通過0重複2048次來表示上述字節模式，這將成爲重複256次的字節0x00。現在，我們只需要存儲字典

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

和字節模式0x00重複256次，我們的壓縮文件從16,384字節（模字典）256個字節。

簡而言之，壓縮是如何工作的。整個業務歸結爲尋找給定文件中字節和字節序列的簡短高效表示。這是一個簡單的想法，但細節（找到代表）可能會非常具有挑戰性。

見例如：

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