修復損壞的gz或tar.gz壓縮文件之原理篇
責編：admin ｜2014-12-22 16:07:05gzip的壓縮算法本質上是deflate(zip也幾乎都用)，這個算法其實是由LZ77算法加上一個變形的哈夫曼編碼組成的。大概算法流程是：“原始數據—>LZ77—>哈夫曼 ”這三個步驟。因啥夫曼樹仍有可能進行壓縮，所以，實質上的算法流程是：“原始數據—>LZ77—>(哈夫曼樹->CL壓縮)。 ”
先來聊聊“原始數據—>LZ77”這一層的思想。LZ77的詳細算法見相關文檔，本文不做贅述，僅描述涉及本文主題的一些思想。本質上看，LZ77是基于對連續重復的字節片斷用指向的方式表示來實現壓縮。比如：有句英文叫business is business，為了簡化這個句子(注意有空格)，我們用business is (12，8)來表示，意思是括號內的數字并非原始數據，而是代表從當前位置向前12個字節，并且連續了8個字節的那段文字。這樣一來，文字部分就變得簡短了。當然，我們一定會注意到，對于每個句子，要額外有信息表示到底是原始數據，還是指針類的數據。所以，整個壓縮后的數據，由三類不同的信息元素組成：本來就是這樣的文字、指向的位置，指向的長度，這三個元素即是lz77算法中的literal、distance和length。
給定任何一段字節流，如果使用LZ77算法進行了壓縮，就一定會得到一段由literal、distance和length組成的字節流，那要如何區分這三類元素呢？distance和length總是成對出現的，所以，其實是如何區分這2類：1、literal 2、distance與length。通過適當方法區分開這2類成員，就完成了LZ77算法的整個方法。
LZ77完成后，會形成一段較短的字節流。但這還不夠，還要經過哈夫曼編碼進行二次壓縮才能使壓縮比更為理想。
同樣的原因，對哈夫曼編碼原理不做過多解釋，僅對涉及本文主題的一些原理進行概要性表述。關于哈夫曼編碼，舉個例子說明一下：如果有一段字節流(由字節為最小單位組成)，這些字節流中每種字節值的出現概率是不相同的，但每個字節都使用了8位進行記錄，從概率角度可以知道，這一定是可以再做優化的。哈夫曼就是針對這個思想的優化，簡單地說，就如同生成了一個一一對應的映射字典，用一些短的位代替經常頻繁出現的字節，用一些長的位代替不常出現的字節，這樣，總體上就又進行了一次壓縮
當然，如何區分某個位置開始的是短的位還是些長的位呢？其實很簡單，只要約定：短位用了的，比他長的就不再用這個短位做前綴即可。比如，如果英文中不想用空格間隔開單詞了，只需要這樣設計：I如果表示我的意思，那其他所有單詞就不可能以I開頭。AM如果表示”是”的含義，那既沒有以A開頭的單詞，也沒有以AM開頭的更長的單詞了。以此類推，或許Iamchinese就不用加空格也能間隔開了。
因為LZ77壓縮后的數據元素中有literal、distance和length，為了有效區分，deflate算法把把literal和length合起來，使用一顆哈夫曼樹。樹中編碼表述的數值如果小于255，即表示literal；如果等于256，表示本壓縮塊結束；如果大于256，表示length(需要減254得到)；如果是length，再在其后緊跟distance的編碼，distance使用單一的哈夫曼樹，實現方法見相關文檔。
literal、distance和length采用的哈夫曼樹本身也是個大的負擔，為了進一步壓縮空間，deflate又對這兩顆哈夫曼樹進行了一次壓縮，同樣的，主體上，也是采用哈夫曼算法，這樣，就是第三顆哈夫曼樹了。
簡單的結構如下圖：
按照圖中結構可知，一個gzip結構大致如下圖所示：
可以看到，每個的壓縮包均是獨立存在的，包括其本身使用的動態哈夫曼樹，也僅存在于其作用域的壓縮包內。故而，只要找到每個壓縮包的起始位置，如果這個包沒被破壞，就可解出其對應內容。
通常而言，因gzip的壓縮作業窗口僅32K，所以每個包的大小都不會很大，如果部分包損壞，只要找到下一個包的起始，即可正確解壓后續的數據。
如果gzip壓縮的是多個文件(并非tar之后再做gzip)，此種情況則相對容易。對于gzip而言，文件內包含多個原始文件的，不可以多個文件共用一個壓縮包，也就是說如果有一個文件損壞，并不影響其他文件。這種思路容易實現，也可以使用linux下的gzip recover來完成修復。
我們重點要討論的如果單一文件(如TAR包)gzip后，若其中間損壞，如何正確解壓出后面的數據。這個思路如果理解了，gzip recover的算法就非常容易理解了，其算法也似乎有些弱了。
文章來源：http：//zhangyu.blog.51cto.com/197148/1592013