簡而言之，壓縮是如何實現的？

Question

所以我最近一直在想如何實現壓縮，以及我到目前爲止假設的是，它可能使用了一種具有內存位置值的'字節簽名'鍵的HashTable，其中'字節簽名'應在擴大壓縮物品時更換。

這是不是真相？

通常如何實現壓縮？不需要一個值得回答的頁面，只需簡單地說就可以。

Answer 1

壓縮算法試圖找到重複的子序列以用較短的表示來替換它們。

例如，我們以An Explanation of the Deflate Algorithm爲例，說明25字節長的字符串Blah blah blah blah blah!（200位）。

樸素方法

甲幼稚的方法將是每一個字符具有相同長度的碼字進行編碼。我們有7個不同的字符，因此需要代碼長度爲ceil(ld(7)) = 3。我們的碼字可以比像這些：

000 → "B" 
001 → "l" 
010 → "a" 
011 → "h" 
100 → " " 
101 → "b" 
110 → "!" 
111 → not used 

現在我們可以編碼我們的字符串如下：

000 001 010 011 100 101 001 010 011 100 101 001 010 011 100 101 001 010 110 
B l a h _ b l a h _ b l a h _ b l a ! 

這將只需要25·3位= 75位的編碼字加7· 8位= 56位的字典，從而131位（65.5％）

或爲序列：

00 → "lah b" 
01 → "B" 
10 → "lah!" 
11 → not used 

編碼字：

01 00 00 00 00 10 
B lah b lah b lah b lah b lah! 

現在我們只需要6·2位= 12位的編碼字和10·8位= 80位加3·8位= 24位用於每個字的長度，因此116位（58.0％）。

霍夫曼碼的方法

的Huffman code用於與短碼編碼更頻繁的字符/字符串比較不頻繁的：

5 × "l", "a", "h" 
4 × " ", "b" 
1 × "B", "!" 

// or for sequences 

4 × "lah b" 
1 × "B", "lah!" 

對於一種可能的Huffman碼是：

0  → "l" 
10  → "a" 
110 → "h" 
1110 → " " 
11110 → "b" 
111110 → "B" 
111111 → "!" 

或者對於序列：

0 → "lah b" 
10 → "B" 
11 → "lah!" 

現在，我們的Blah blah blah blah blah!可以被編碼到：

111110 0 10 110 1110 11110 0 10 110 1110 11110 0 10 110 1110 11110 0 10 110 1110 11110 0 10 110 111111 
B  l a h _ b  l a h _ b  l a h _ b  l a h _ b  l a h ! 

或爲序列：

10 0  0  0  0  11 
B lah b lah b lah b lah b lah! 

現在出第一碼只需要78位或8位，而不是25·8 = 200位像我們的初始字符串有。但是我們仍然需要添加存儲字符/序列的字典。對於我們的每個字符的例子，我們需要7個附加字節（7·8位= 56位），每個序列的例子需要7個字節加3個字節作爲每個序列的長度（因此爲59位）。這將導致：

56 + 78 = 134 bit (67.0%) 
59 + 8 = 67 bit (33.5%) 

實際的數字可能不正確。請隨時編輯/更正它。

Answer 2

檢查this維基頁面...

無損壓縮算法通常利用這樣的方式，以更簡明地表示發件人的數據沒有錯誤統計冗餘。無損壓縮是可能的，因爲大多數真實世界的數據具有統計冗餘。例如，在英文文本中，字母'e'比字母'z'更普遍，字母'q'後面跟着字母'z'的概率非常小。

如果某些保真度損失可以接受，另一種稱爲有損數據壓縮或感知編碼的壓縮是可能的。一般來說，有損數據壓縮將通過研究人們如何看待相關數據來指導。例如，人眼對亮度的細微變化比對顏色變化更敏感。 JPEG圖像壓縮部分地通過「舍入」一些不太重要的信息。有損數據壓縮提供了一種獲得給定壓縮量的最佳保真度的方法。在某些情況下，需要透明（不明顯）壓縮;在其他情況下，犧牲保真度以儘可能減少數據量。

無損壓縮方案是可逆的，因此可以重建原始數據，而有損方案接受一些數據丟失以實現更高的壓縮率。

但是，無損數據壓縮算法總是無法壓縮某些文件;事實上，任何壓縮算法都不能壓縮任何不包含可辨別模式的數據。試圖壓縮已被壓縮的數據通常會因此（通常由於較少的符號而被壓縮後文本文件可能被壓縮得更多）導致擴展，因爲試圖壓縮除最瑣碎加密的數據之外的所有數據。

實際上，有損數據壓縮也會到達壓縮再次不起作用的地步，儘管非常有損耗的算法（例如總是刪除文件的最後一個字節）將始終壓縮文件直到點它在哪裏是空的。

無損與有損壓縮的一個例子是以下字符串：

25.888888888 

作爲此字符串能夠被壓縮：

25.[9]8 

解釋爲「25點9個八分」，則原始字符串完全重新創建，只需以較小的格式寫入。在有損系統中，使用

26 

取而代之的是，原始數據丟失，而文件尺寸較小。

Answer 3

無損壓縮算法將每個可能的輸入轉換爲不同的輸出，以這種方式使更多的通用輸入轉換爲更短的輸出。在數學上，所有的都不可能被壓縮 - 否則，你會有多個輸入A和B壓縮成相同的形式，所以當你解壓時，你會回到A還是回到B？在實踐中，大多數有用的信息都有一定的冗餘，這種冗餘適合某些模式;因此數據可以被有效地壓縮，因爲當你壓縮它們時，自然不會出現這種情況。

例如，在JPEG或MP3壓縮中使用的有損壓縮通過以比原始位數少的位數來表示近似輸入數據來工作。當你解壓時，你不會得到原始的，但你通常得到足夠接近的東西。

Answer 4

簡而言之，常見的壓縮形式是http://en.wikipedia.org/wiki/Dictionary_coder。這涉及用較短的字符替換較長的重複字符串。

例如，如果你有一個看起來像這樣的文件：

"Monday Night","Baseball","7:00pm" 
"Tuesday Night","Baseball","7:00pm" 
"Monday Night","Softball","8:00pm" 
"Monday Night","Softball","8:00pm" 
"Monday Night","Baseball","5:00pm" 

這將是大約150個字符，但如果你在那裏做一個簡單的替換如下： A =「週一之夜」， B =「星期二晚上」，C =「棒球」，D =「壘球」，E =「7:00 pm」，F =「8:00 pm」，G = 5:00pm「

然後，編碼爲：

A,C,E 
B,C,E 
A,D,F 
A,D,F 
A,C,G 

使用on 25個字符！如果我們假設一些關於文件格式的更多信息，一個聰明的觀察者也可以看到如何輕鬆地將其進一步減少到15個字符。很顯然，替換鍵存在開銷，但通常非常大的文件有很多替換鍵。這可以是壓縮大型文件或數據結構的一種非常有效的方式，並且仍然可以讓它們「有點」人類可讀。

Answer 5

Rosetta Code在霍夫曼編碼上有一個entry，我的早期blog entry也是如此。