前言
數據壓縮技巧始終是讓我感到到比擬神秘的數學算法之一,而當我接觸到其具體的算法時候，發明其原理是如此的簡略，所以就寫了這篇文件來談談自己的感觸。但由於本文篇幅有限，就以只以一個最簡略的LZ77算法作為例子來講解。數據壓縮技巧的分類
數據壓縮算法重要分有損壓縮和無損壓縮兩種。無損壓縮就是能夠完整還原的壓縮算法. 而有損壓縮就是不能完整還原的壓縮算法。比如典范的mp3音頻就是有損壓縮算法，固然它喪失了一些本來的音頻信息,但是它能極大地提高其壓縮比例，而喪失的那點信息對全部音樂片段沒有多大影響。本文先容的通用數據壓縮算法針對的不是某種具體的音頻或者視頻信息，而是一種通用的數據信息，我們並不知道什麼信息能夠喪失，什麼信息該保留，所以它確定就是無損壓縮了。我們平時在Windows下應用的WinZip,WinRar的壓縮就是尺度的通用數據壓縮,而本文講解的算法也就是這些算法通用數據壓縮技巧發展
我們在大學課程《離散數學》和《數據結構》裡面都學過Huffman樹。幾乎每本講Huffman樹的書都會提到應用Huffman樹結構最小冗余度的前綴編碼。Huffman編碼就是數據壓縮技巧的基礎。D.A.Huffman在1952發表了他的論文《最小冗余度代碼的結構方法》揭開了早期的數據壓縮技巧形成。早期的數據壓縮技巧就是基於編碼上的優化技巧。但是我們都知道這種編碼上的優化是要統計數據的呈現概率的。但是在處理大文件的時候，統計文件裡面的字符概率是件十分麻煩的時候，要耗費很長的盤算時間。實際的方法都是采用一種叫做自適應編碼的方法，也就是在壓縮的時候來不斷統計字符的概率。這種方法在壓縮開端的時候後果不是很好，但是到了壓縮後面，它統計的概率就會越來越接近真實的字符呈現的概率。(具體的這類算法我還沒有仔細研究過，所以我就不好講解了。)
1977 年，以色列人 Jacob Ziv 和 Abraham Lempel 發表了論文《次序數據壓縮的一個通用算法》, 1978 年，他們發表了該論文的續篇《通過可變比率編碼的獨立序列的壓縮》。從此，數據壓縮技巧進進字典范的模式壓縮了。字典范的數據壓縮十分輕易明白，就是盡量不保留重復的信息而已。那兩個以色列人發明的算法LZ77,LZ78就是現在風行的Zip壓縮算法的前身。1984 年，Terry Welch 發表了名為《高性能數據壓縮技巧》(A Technique for High-Performance Data Compression)的論文，也就是現在風行的LZW壓縮算法的實現。實在LZW壓縮算法和LZ77,LZ78的壓縮沒有多大的差別，只是在實現手段有進一步的優化。現在著名的GIF圖片格局中保留內部每個點的色彩的信息就是應用LZW那套算法。LZ77,LZW這種字典范的數據壓縮方法壓縮比例遠遠比單純的從編碼上的優化的壓縮要高。而且這種壓縮算法無論是在壓縮還是在解壓，履行效率都比以前的編碼優化壓縮要高得多！
Unix 上當時應用LZW的壓縮程序Compress幾乎成為Unix上壓縮程序的尺度。而同時在MS-DOS上也有一個同樣的叫ARC程序的壓縮程序。80 年代中期以後，人們對 LZ77 進行了改良，隨之出生了一批我們今天還在大批應用的壓縮程序。Haruyasu Yoshizaki(Yoshi) 的 LHarc 和 Robert Jung 的 ARJ 是其中兩個著名的例子,還有到今天都已經成為壓縮尺度的Zip壓縮
最小長度的Huffman編碼
下面我們開端進進數據壓縮的正題。
幾乎每篇講解數據壓縮的文章都會把“信息熵”擺出來講解。但是本文篇幅有限，不打算講解了。由於一旦把信息熵講解出來，那麼以後的壓縮都會信息熵接洽在一起了，挺麻煩的。我們直接進進數據的編碼部分。不要認為只有早期的編碼優化的壓縮才涉及到數據的編碼，實在現在Zip,Rar壓縮內部也應用了優良的數據編碼方法，來縮小信息的冗長。
首先我們得知道假如設計一個變長的編碼。通常的方法就是應用前綴碼方法。所謂前綴碼就是把編碼的特點信息表現在編碼的最前面。下面來看個例子。
有三個信息A,B,C,他們的二進制碼分辨是0,1,01,假如我們收到一段信息是01010,解碼時候我們怎麼區分他們是CCA還是ABABA,或者是ABCA呢?假如應用前綴碼，我們就可以避免這種沖突。下面應用前綴碼給A,B,C編碼。
A: 0 B: 10 C: 110
那麼01010 就只能被翻譯成ABB.所以這中變長的編碼是不會有沖突的。可是下面又有一個標題了，既然0,10,110,1110…這中前綴編碼的任意組合都不會產生解碼的沖突，假如安排A,B,C的編碼能夠使A,B,C表現的信息最短？這個標題就是前面提到的Huffman提出的最小編碼的結構方法.
Huffman編碼就是一種最優的前綴編碼(也是最小的編碼)。它實現的基礎是在已經知道每個字符呈現的比例或者概率。比如知道A,B,C,D字符呈現的個數分辨為12,3,4,5 .那麼結構其Huffman二叉樹。
root
A @
D @
C B
(本文在這裡只是簡略地提一下Huffman編碼，具體的結構方法和其原理請大家參考離散數學相干書籍。)根據結構的Huffman二叉樹:
A的編碼:0 B的編碼:111 C的編碼:110 D的編碼:10
那麼A 就只用了1個bit,B用了3個,C用了3個,D用了2個.那麼這段信息總共用了12*1+3*3+4*3+5*2 = 43個bit.而安裝一般的2-10進制編碼,那麼A,B,C,D每個都需要應用2個bit才行,總共就應用了12*2+3*2+3*2+5*2= 46個bit.
實在這中前綴編碼無非就是用短的碼來表現呈現概率高的字符號，這個著名的電報莫斯編碼是同一個道理。電報中的莫斯編碼就是把英文中最常呈現的字母e編成最短的編碼。
中學數學裡面講過排序不等式: 次序和 >= 亂序和 >= 反序和.而這裡的編碼為了獲得“最小”，所以采用了“反序”的結構方法。
可以確定的是，無論你采用何種編碼，能夠不沖突的編碼方法中，應用Huffman編碼方法編碼出來的信息的長度是最小的。
除了Huffman編碼以外，還有種更優良的算術編碼，不過其原理有點復雜，本文也不打算講解了。下面我們就來看著名的LZ77算法
LZ77字典壓縮算法的原理
輕易想到的字典壓縮算法就是結構一本實際的字典。比如說一篇英文文章，實在我們只要保留每個單詞在一本英語字典中呈現的頁數和個數就可以了。頁數用兩個字節，個數用1 個字節，那麼一個單詞均勻應用了3個字節來保留，而我們知道一般的英語單詞長度都在3個以上的。由此，我們的這篇英文文章實現了數據的壓縮。但是實際的通用數據壓縮算法卻不能這麼做，由於我們在解壓的時候需要一本上千頁的英語單詞字典，而這部分的信息首先是壓縮程序不可預知的，同時它又不能保留在壓縮信息裡面(英語字典比我們的英文文章還厚)。我們這裡先容的LZ77壓縮算法就是應用的動態創立字典方法。也就是說，字典信息就是前面壓縮信息本身。
前面已經說過，LZ77算法重要就是避免重復的長信息呈現。比如說下面一串字符
AABAABAAB
我們發祥地裡面有三個重復呈現的AAB,但是我們只要保留一個AAB就可以了，然後其它兩個呈現AAB的處所只需要把第一個呈現AAB的地位和長度存儲下來就可以了。那麼我們保留後面兩個AAB就只需要一個二元數組<匹配串的相對地位,匹配長度>。解壓的時候，我們根據匹配串的相對地位，向前找到第一個AAB的位移，然後再根據匹配長度，直接把第一個AAB復制到當前解壓緩沖裡面就可以了。假如壓縮時找不到之前雷同的信息(也就是可匹配的信息)，那麼我們就直接輸出這段信息到壓縮緩沖裡面,然後移下下段要壓縮的信息。
好了，讓我們來看看一個實際的例子,字符串AABAABCDDABC
步驟
當前輸進緩沖
當前內存中的字典
輸出信息
1.
AABAABCDDABC
空
空
2.
ABAABCDDABC
A
A
3.
BAABCDDABC
AA
<0,1>
4.
AABCDDABC
AAB
B
5.
CDDABC
AABAAB
<0,3>
6.
DDABC
AABAABC
C
7.
DABC
AABAABCD
D
8.
ABC
AABAABCDD
<7,1>
9.
空
AABAABCDDABC
<4,3>
這裡有個麻煩的標題，在解壓的時候如何區分一段信息是源數據信息還是一個匹配信息？假如是源數據信息，那麼我們直接復制到解壓緩沖區，假如是匹配信息，我們得從當前解壓緩沖地位向前查找重復的匹配信息。通行的解決措施就是多應用1 個位(bit)來區分壓縮信息裡面的源數據信息和匹配信息。大家可能會擔心，我們這裡引進了新的信息進來，會不會讓壓縮文件壓得反而比源文件還大？但是實踐已經證實了，對於一般的未壓縮的數據信息，那多引進的一個bit的標記信息並不會有多大的影響。不過同時重復壓縮一個文件後，文件確實不僅不會壓小，還會反而壓得比以前大。
記錄重復信息的匹配信息包含兩項, 一個是匹配的地位,一個是匹配的長度.如何分配這兩個信息的保留是個要害的標題.匹配的地位不能是盡對任意的地位,由於有些文件長度高達幾MB,甚至上百 MB,那麼僅僅保留一個匹配地位的信息就要好幾個字節.實際的安排計劃是用兩個字節來保留一個匹配信息.12位來表現匹配地位,4位來表現匹配長度.那麼可尋找匹配
地位長度可以達到4096, 而4位表現的匹配長度可以達到16個字節。而針對匹配信息的尋找也找匹配長度至少為3個字節的，由於假如匹配長度小於3 個字節，那麼僅僅保留匹配信息的字節數就高於壓縮縮掉的字節數,就得不償失了。實際的許多壓縮軟件都是這樣分配的,我也自己測試過,這種分配計劃的確是最佳的.
那麼這固定長度的匹配尋找區間就是許多人所說的字典窗口
當前分析地位
要壓縮的源數據
用來查找匹配的字典信息
4096個字節長度
在當前分析地位提取要壓縮的數據信息，在源數據緩沖中當前分析地位之前固定長度的信息區域往找可以匹配的最長匹配串。假如找到後，當前分析地位移動匹配長度個字節，然後字典窗口也移動匹配個長度字節。這樣，分析指針不斷向後移動，字典窗口也不斷向後移動，直到分析指針移動到源數據緩沖結尾。
