高壓縮文件是如何實現的？

11-26

在網上下載一個十幾兆或幾百兆的文件，解壓後達到幾 G，這是怎麼做到的？

簡要概述原理：
每個文件都由各種不同代碼組成，比如01代碼。這類文件只有數字0與1組合。
壓縮原理就是【通過尋找其中的規律，簡化數字的排列】。
比如
00000110001111111111
可以簡化成
5個0,2個1,3個0,10個1的排列
100000000000
可以簡化成數學的
10^10

至於@yskin 說沒見過2G壓縮到十幾兆的。
實際上在極限壓縮方式下其實28.1G壓到25.8M都可以。

附下載
2^31-1 [AviSynth 16x16 60.000fps AVC-Lossless-yuv420p8]

打開看後基本都能理解這個壓縮的大概原理了。

下面是幾種常見文件壓縮演算法原理介紹：

字典演算法

字典演算法是最為簡單的壓縮演算法之一。它是把文本中出現頻率比較多的單詞或辭彙組合做成一個對應的字典列表，並用特殊代碼來表示這個單詞或辭彙。例如：
有字典列表：
00=Chinese
01=People
02=China
源文本：I am a Chinese people,I am from China 壓縮後的編碼為：I am a 00 01,I am from 02。壓縮編碼後的長度顯著縮小，這樣的編碼在SLG遊戲等專有名詞比較多的遊戲中比較容易出現，比如《SD高達》。
----------------------------------------------------------------------------------------------------------------------
固定位長演算法（Fixed Bit Length Packing）

這種演算法是把文本用需要的最少的位來進行壓縮編碼。
比如八個十六進位數：1，2，3，4，5，6，7，8。轉換為二進位為：00000001，00000010，00000011，00000100， 00000101，00000110，00000111，00001000。每個數只用到了低4位，而高4位沒有用到（全為0），因此對低4位進行壓縮編碼後得到：0001，0010，0011，0100，0101，0110，0111，1000。然後補充為位元組得到：00010010， 00110100，01010110，01111000。所以原來的八個十六進位數縮短了一半，得到4個十六進位數：12，34，56，78。
這也是比較常見的壓縮演算法之一。
------------------------------------------------------------------------------------------------------------
RLE（Run Length Encoding）

是一個針對無損壓縮的非常簡單的演算法。它用重複位元組和重複的次數來簡單描述來代替重複的位元組。儘管簡單並且對於通常的壓縮非常低效，但它有的時候卻非常有用（例如，JPEG就使用它）。

原理圖2.1顯示了一個如何使用RLE演算法來對一個數據流編碼的例子，其中出現六次的符號『93』已經用3個位元組來代替：一個標記位元組（『0』在本例中）重複的次數（『6』）和符號本身（『93』）。RLE解碼器遇到符號『0』的時候，它表明後面的兩個位元組決定了需要輸出哪個符號以及輸出多少次。

這種壓縮編碼是一種變長的編碼，RLE根據文本不同的具體情況會有不同的壓縮編碼變體與之相適應，以產生更大的壓縮比率。

　　變體1：重複次數+字元
文本字元串：A A A B B B C C C C D D D D，編碼後得到：3 A 3 B 4 C 4 D。

　　變體2：特殊字元+重複次數+字元
文本字元串：A A A A A B C C C C B C C C，編碼後得到：B B 5 A B B 4 C B B 3 C。編碼串的最開始說明特殊字元B，以後B後面跟著的數字就表示出重複的次數。

　　變體3：把文本每個位元組分組成塊，每個字元最多重複 127 次。每個塊以一個特殊位元組開頭。那個特殊位元組的第 7 位如果被置位，那麼剩下的7位數值就是後面的字元的重複次數。如果第 7 位沒有被置位，那麼剩下 7 位就是後面沒有被壓縮的字元的數量。例如：文本字元串：A A A A A B C D E F F F。編碼後得到：85 A 4 B C D E 83 F（85H= 10000101B、4H= 00000100B、83H= 10000011B）

實現RLE可以使用很多不同的方法。基本壓縮庫中詳細實現的方式是非常有效的一個。一個特殊的標記位元組用來指示重複節的開始，而不是對於重複非重複節都coding run。
因此非重複節可以有任意長度而不被控制位元組打斷，除非指定的標記位元組出現在非重複節（頂多以兩個位元組來編碼）的稀有情況下。為了最優化效率，標記位元組應該是輸入流中最少出現的符號（或許就不存在）。
重複runs能夠在32768位元組的時候運轉。少於129位元組的要求3個位元組編碼（標記+次數+符號），而大雨128位元組要求四個位元組（標記+次數的高4位|0x80+次數的低4位）。這是通常所有採用的壓縮的做法，並且也是相比較三個位元組固定編碼（允許使用3個位元組來編碼256個位元組）而言非常少見的有損壓縮率的方法。
在這種模式下，最壞的壓縮結果是：
輸出大小=257/256*輸入大小+1

其他還有很多很多變體演算法，這些演算法在Winzip Winrar這些軟體中也是經常用到的。
----------------------------------------------------------------------------------------------------------------
霍夫曼編碼（Huffman Encoding）

哈夫曼編碼是無損壓縮當中最好的方法。它使用預先二進位描述來替換每個符號，長度由特殊符號出現的頻率決定。常見的符號需要很少的位來表示，而不常見的符號需要很多為來表示。
哈夫曼演算法在改變任何符號二進位編碼引起少量密集表現方面是最佳的。然而，它並不處理符號的順序和重複或序號的序列。

原理我不打算探究哈夫曼編碼的所有實際的細節，但基本的原理是為每個符號找到新的二進位表示，從而通常符號使用很少的位，不常見的符號使用較多的位。
簡短的說，這個問題的解決方案是為了查找每個符號的通用程度，我們建立一個未壓縮數據的柱狀圖；通過遞歸拆分這個柱狀圖為兩部分來創建一個二叉樹，每個遞歸的一半應該和另一半具有同樣的權（權是∑NK =1符號數k, N是分之中符號的數量，符號數k是符號k出現的次數）
這棵樹有兩個目的：
1．編碼器使用這棵樹來找到每個符號最優的表示方法
2．解碼器使用這棵樹唯一的標識在壓縮流中每個編碼的開始和結束，其通過在讀壓縮數據位的時候自頂向底的遍歷樹，選擇基於數據流中的每個獨立位的分支，一旦一個到達葉子節點，解碼器知道一個完整的編碼已經讀出來了。

我們來看一個例子會讓我們更清楚。圖2.2顯示了一個10個位元組的未壓縮的數據。
根據符號頻率，哈夫曼編碼器生成哈夫曼樹（圖2.4）和相應的編碼表示（圖2.3）。

你可以看到，常見的符號接近根，因此只要少數位來表示。於是最終的壓縮數據流如圖2.5所示。

壓縮後的數據流是24位（三個位元組），原來是80位（10個位元組）。當然，我應該存儲哈夫曼樹，這樣解碼器就能夠解碼出對應的壓縮流了，這就使得該例子中的真正數據流比輸入的流數據量大。這是相對較短的數據上的副作用。對於大數據量來說，上面的哈夫曼樹就不佔太多比例了。解碼的時候，從上到下遍歷樹，為壓縮的流選擇從左/右分支，每次碰到一個葉子節點的時候，就可以將對應的位元組寫到解壓輸出流中，然後再從根開始遍歷。實現哈夫曼編碼器可以在基本壓縮庫中找到，其是非常直接的實現。
這個實現的基本缺陷是：
1．慢位流實現
2．相當慢的解碼（比編碼慢）
3．最大的樹深度是32（編碼器在任何超過32位大小的時候退出）。如果我不是搞錯的話，這是不可能的，除非輸出的數據大於232位元組。

另一方面，這個實現有幾個優點：
1．哈夫曼樹以一個緊密的形式每個符號要求12位（對於8位的符號）的方式存儲，這意味著最大的頭為384。
2．編碼相當容易理解
哈夫曼編碼在數據有噪音的情況（不是有規律的，例如RLE）下非常好，這中情況下大多數基於字典方式的編碼器都有問題。
3. Rice對於由大word（例如：16或32位）組成的數據和教低的數據值，Rice編碼能夠獲得較好的壓縮比。音頻和高動態變化的圖像都是這種類型的數據，它們被某種預言預處理過（例如delta相鄰的採樣）。
儘管哈夫曼編碼處理這種數據是最優的，卻由於幾個原因而不適合處理這種數據（例如：32位大小要求16GB的柱狀圖緩衝區來進行哈夫曼樹編碼）。因此一個比較動態的方式更適合由大word組成的數據。

原理Rice編碼背後的基本思想是儘可能的用較少的位來存儲多個字（正像使用哈夫曼編碼一樣）。實際上，有人可能想到Rice是靜態的哈夫曼編碼（例如，編碼不是由實際數據內容的統計信息決定，而是由小的值比高的值常見的假定決定）。
編碼非常簡單：將值X用X個『1』位之後跟一個0位來表示。

實現在基本壓縮庫針對Rice做了許多優化：
1．每個字最沒有意義的位被存儲為k和最有意義的N-k位用Rice編碼。K作為先前流中少許採樣的位平均數。這是通常最好使用Rice編碼的方法，隱藏噪音且對於動態變化的範圍並不導致非常長的Rice編碼。
2．如果rice編碼比固定的開端長，T，一個可選的編碼：輸出T個『1』位，緊跟（log2(X-T)）個『1』和一個『0』位，接著是X-T（最沒有意義的(log2(X-T))-1位）。這對於大值來說都是比較高效的代碼並且阻止可笑的長Rice編碼（最壞的情況，對於一個32位word單個Rice編碼可能變成232位或512MB）。
如果開端是4，下面是結果編碼表：
X
bin
Rice
Thresholded
Rice
0
00000
0
0

1
00001
10
10

2
00010
110
110

3
00011
1110
1110

4
00100
11110
11110

5
00101
111110
111110

6
00110
1111110
11111100
+1
7
00111
11111110
11111101

8
01000
111111110
1111111000
+1
9
01001
1111111110
1111111001

10
01010
11111111110
1111111010
-1
11
01011
111111111110
1111111011
-2
12
01100
1111111111110
111111110000

13
01101
11111111111110
111111110001
-1
14
01110
111111111111110
111111110010
-2
15
01111
1111111111111110
111111110011
-3
16
10000
11111111111111110
111111110100
-4
17
10001
111111111111111110
111111110101
-5
18
10010
1111111111111111110
111111110110
-6
19
10011
11111111111111111110
111111110111
-7
20
10100
111111111111111111110
11111111100000
-5
就像你看到的一樣，在這個實現中使用threshold方法僅僅兩個編碼導致一個最壞的情況；剩下的編碼產生比標準Rice編碼還要短的編碼。
最壞的情況，輸出。

--------------------------------------------------------------------------------------------------------------
Lempel-Ziv (LZ77)

Lempel-Ziv壓縮模式有許多不同的變數。基本壓縮庫有清晰的LZ77演算法的實現（Lempel-Ziv，1977），執行的很好，源代碼也非常容易理解。
LZ編碼器能用來通用目標的壓縮，特別對於文本執行的很好。
它也在RLE和哈夫曼編碼器（RLE，LZ，哈夫曼）中使用來大多數情況下獲得更多的壓縮。這個壓縮演算法是有版權的。
原理在LZ壓縮演算法的背後是使用RLE演算法用先前出現的相同位元組序列的引用來替代。
簡單的講，LZ演算法被認為是字元串匹配的演算法。例如：在一段文本中某字元串經常出現，並且可以通過前面文本中出現的字元串指針來表示。當然這個想法的前提是指針應該比字元串本身要短。
例如，在上一段短語「字元串」經常出現，可以將除第一個字元串之外的所有用第一個字元串引用來表示從而節省一些空間。
一個字元串引用通過下面的方式來表示：
1．唯一的標記
2．偏移數量
3. 字元串長度
由編碼的模式決定引用是一個固定的或變動的長度。後面的情況經常是首選，因為它允許編碼器用引用的大小來交換字元串的大小（例如，如果字元串相當長，增加引用的長度可能是值得的）。

實現使用LZ77的一個問題是由於演算法需要字元串匹配，對於每個輸入流的單個位元組，每個流中此位元組前面的哪個位元組都必須被作為字元串的開始從而儘可能的進行字元串匹配，這意味著演算法非常慢。
另一個問題是為了最優化壓縮而調整字元串引用的表示形式並不容易。例如，必須決定是否所有的引用和非壓縮位元組應該在壓縮流中的位元組邊界發生。
基本壓縮庫使用一個清晰的實現來保證所有的符號和引用是位元組對齊的，因此犧牲了壓縮比率，並且字元串匹配程序並不是最優化的（沒有緩存、歷史緩衝區或提高速度的小技巧），這意味著程序非常慢。
另一方面，解壓縮程序非常簡單。
一個提高LZ77速度的試驗已經進行了，這個試驗中使用數組索引來加速字元串匹配的過程。然而，它還是比通常的壓縮程序慢。

當然靜態數據和動態數據的壓縮策略是完全不同的。

一個壓縮文件是不是還可以用其他演算法再繼續壓縮？
可以，但沒要。壓縮文件有極限值存在。高壓一遍已經很接近這個值了，再壓縮的話基本也就只有一丁點壓縮率提升，甚至會增加體積。

隨便做的渣繪圖。不要在意細節→ →

————————————————————————————————————————
下面是題外話。
那麼一般要如何簡單實現高壓縮？
系統文件諸如GAL遊戲跟一些純代碼的文檔基本能直接用 7Z 進行無損壓縮就可以了。當然，高壓縮率也意味著更費時間的壓縮跟解壓。壓縮率小的沒必要用 7z，直接打包反而更適合。
影音圖像文件多數壓縮率只能通過再編碼有損壓縮。比如BMP圖像轉jpg 吧圖片的一些一般人用不到的雜信息去除，APE轉MP3之類。基本除了音源文件外其他要對比不太明顯。(照片BMP通過7Z壓縮後解壓其實是有點變化的，這個不細說，一說就沒完沒了了。)

http://bt.ktxp.com/html/2013/0305/293319.html
→→至於有的人說我上面附帶的極限壓縮例子太坑爹，於是再附帶一個我做的動畫壓制1080p BDMV 通過10bit x264再編碼壓縮成每話90M大小視頻。源BDBOX總大小119.16GB。
畫面的話我【個人主觀看法】覺得在電腦觀看跟源盤沒什麼區別。(PS3跟一些高端硬體晶元的解碼器播放那是另一回事了)
畫面控追求的BDMV無損畫質也是相對無損。真正意義上的無損畫質輸出的影片，渲染體積1分鐘視頻就超過10G。我個人渲過最大的是18秒44.5G 8k視頻。

參考資料
[1]幾種壓縮演算法原理介紹

這個問題只要一句話就能解釋明白：根據香農的信息理論，任何一個文件被無損壓縮後的結果不可能小於其熵 (資訊理論) 。

換句話說，如果一個文件有20多個G的大小，但是其信息熵只有20多M，則實現一個1000倍的壓縮是完全可能的（比如樓主放出的幾小時全黑視頻）；反過來看，一個文件如果雖然只有100M，但是其信息熵卻高達90M，則這樣的文件是無論如何也不可能被無損壓縮至20M大小的。

多說一句，一個文件的信息熵有多少，靠一個公式是完全可以算出來的。所以只要提供任何一個文件，我們都能知道它最小可以被壓縮到多少。

以上說法僅限於無損壓縮，對於有損壓縮來說，壓縮了多少倍皆有可能。

老師說，回去把課文抄一千遍，結果第二天你交上去十幾萬字的作業，外星人看了後驚嘆道，老師說的九個字竟然包含了這麼多信息，壓縮比太驚人了。

一個 102400x10240 的純色圖像，未壓縮全彩點陣圖是1000MB，可以壓縮成長，寬，顏色三個32位數，即12位元組。

通用無損壓縮演算法碰上合適的文件壓縮比也可以很誇張。

一句話：

原文件：
333333333333333300000000000000000000000000000000000000000

壓縮文件：
10個3 30個0

原文件：
ABCDEFGHIJKLMN

壓縮文件：
A到N

沒有神奇的技術，就是一般的壓縮演算法，只是和被壓縮文件的編碼有關係，你那個2個G的文件隨便用什麼壓都能壓到那麼小。

壓縮率與文件內容本身的重複程度有關，重複的內容越多，壓縮率越高，如：純色的圖片（只需記錄長、寬、一個RGBA值等基本信息），單個字元組成的文件（只需要記錄開始、結束的位置及一個字元）。

壓縮演算法則通過自身的規則替換掉重複的內容，編成更短的字元，並且解壓時有能力反向還原。
極端的例子，假如整個文件全是『0』組成，無論文件大小有多少個G，實際上壓縮演算法都能將其編成一句話：
[0, N]0
表示從開始到結束都是0，解壓的時候，往文件里寫入N個0就是了。

曾經有過把一個1G的tif文件壓縮成1M的經歷，同事從qq上傳過來的時候我以為文件壞了，解壓以後果然1G。
但是顯然這跟文件本身有關係，那是一張單純底色的圖。
壓縮軟體就是winrar

看到大家都在介紹數據壓縮的基本原理，我來回答一下典型的高壓縮率演算法是怎麼實現的。

首先拆分一下，很多壓縮演算法體系有這麼幾段：
1. 過濾器
2. 預測器
3. 編碼器

過濾器：
輸入一個文件，先判斷它的內容，做些預處理。有些過濾器會把已經壓縮的數據解壓出來，方便之後做更強的壓縮。例如可以把 JPEG 圖片里用的 Huffman 編碼解開，然後改用 PPM 之類的演算法壓縮。更強一點的過濾器甚至會還原出原圖，然後套上一個圖像數據預測器，再把預測器和真實圖像的誤差單獨壓縮。

預測器：
根據輸入的數據，預測出某個位置上可能的值的分布，比如「下一個位元組有 0.8753 的概率是 42，有 0.0314 的概率是 233，…」這樣。現在綜合壓縮能力前幾的軟體基本用的是 Context Modeling 一類的技術，即掃描輸入數據，從中提取數據的統計學特徵。記得 PAQ 是用神經網路來預測數據的，所以各種稀奇古怪的數據壓縮率都不錯，但速度也很感人（個位數 KB/s）。

編碼器：
一直在教科書里出現的 Huffman 就是一種比較經典的編碼器。高壓縮率演算法通常用算數編碼或者區間編碼（其實是一回事），原理是讓出現概率大的數據佔用更大的「空間」。比如一個常用數據佔了 1/4 的空間，那長度就是 2bit 了，但佔了 1/1024 的空間的罕見數據需要 10bit。這樣就能保證最終的編碼最短。算數/區間編碼可以認為是 Huffman 的推廣，通常更慢但強於 Huffman。

很多年沒碰了，憑記憶寫的。

比如百度雲中被和諧的視頻，比如一個1G的視頻，你下載下來，發現還是1G，然後你壓縮一下，發現不到100K。
其實就是把視頻用一張圖覆蓋了，在圖的數據後面填0，填到1G為止，所以很好壓縮

我覺得知乎上有許多問題wikipedia上都有最好的答案。
提問者直接去wikipedia上看就好了。如果能看英文，盡量看英文，有時候中英文同一個詞條是完全不一樣的，中文並不是英文的翻譯。英文通常更詳細

數據壓縮
Category:數據壓縮
Category:無損壓縮演算法

壓縮包炸彈。http://bbs.kafan.cn/thread-955032-1-1.html

我只是講個故事，有錯輕噴。在《天才在左，瘋子在右》看到的。一個外星人來到地球上覺得大英百科全書不錯，想帶一本回去。可是要採樣的東東太多了，一本書明顯佔位置，所以決定帶電子書回去，然後發現要存的資料也太多了，最後外星人想了一個辦法:1.把電子書改成數字組成的編碼。2.量了自己飛船的總長。3.在自己飛船上點了個點。這個點就是大英百科全書了。嘿嘿，故事到此為止。

壓縮率主要是由被壓縮文件本身決定的，不同壓縮演算法之間是有差別，但是不會有非常大的區別。

我就說一點，當年下flex的幫助文檔，下回來只有不到20M，解壓完之後有接近1G，後來分析了一下，發現幾乎所有幫助文件的html結構都是類似的，所以……嗯，就是這樣。

壓縮即映射，把一些代碼根據規則映射成另外一些代碼。為了讓代碼長度變短，就應該將出現頻率較高的代碼串映射成一些短的代碼串。總體變短的代碼串更利於傳輸，傳輸完畢之後帶利用映射規則將代碼還原，供機器識別。
壓縮程序就是儲存了映射規則的程序。
所以根據不同的映射規則一個文件能被壓縮的大小是不同的。理論上講任何文件都有可能壓縮成1比特，因為只要講這個文件的整個代碼映射成1就可以了（雖然這樣的壓縮程序是沒有意義的）。所以說2樓講的那個信息熵什麼純屬無稽之談。

常見有三種：

1 霍夫曼樹壓縮演算法。各種無損壓縮。參考其他答案，不重複敘述了。

2 替代壓縮法。例如用短連接替代長連接，依賴於一個外部引用庫，也許並不符合你的情況。

3 常用於一些盜版軟體（主要是遊戲）的有損壓縮技術：

例如某個軟體的音頻、視頻、圖片，原以一種較低壓縮率（或未壓縮）的方式保存在一個包文件內。分發商可以把他們提取出來，以有損方式壓縮。在還原的時候，將他們還原為原有的格式（但已經不是原有的質量），再封裝成原有的包格式，替代原來的包文件。

不是所有的文件都有有如此高的壓縮率的

幾G能壓縮到十幾M，我們可以認為這個文件"廢話"太多了

1. 向量編碼,碼本越大,壓縮比越高,但是考慮到實際操作,這種高壓縮比的成本太高.

2. 廣義的壓縮就是編碼,這種意義上任何一個URL連接都可以視作一種在線壓縮,只是這種壓縮不具備通用性.

3. 基於以上兩種理論,可以忽悠出一些所謂的黑科技,比如這個http://news.sina.cn/?sa=t124d10242716v71from=mbaidustun=20007vt=4

壓縮就是通過匹配相同的字元，讓後在講匹配規律記錄在個文件里，所以可以將大文件壓縮啦咔咔

個人是懶人，看長點的科普文實在提不起興趣，在這裡簡單回答下壓縮原理。

眾所周知計算機使用二進位1和0的組合，當遇到一串有規律的組合時我們就可以採用簡化表示方法，比如我們常常用的0-9，a-z，難道還有誰不厭其煩的會寫全了？這就是壓縮。

壓縮率看源文件而定，沒有規律就沒法壓縮，比如圖片的一大片純藍色背景。至於LZ提及的壓縮率不到10%，純粹是有人沒事折騰玩，你可以打開文件，發現裡面二進位數據全是一個個0...