亚洲日本免费-啊轻点灬太粗太长了三男一女-麻豆av电影在线观看-日韩一级片毛片|www.grbbt.com

　　gzip的壓縮算法本質(zhì)上是deflate(zip也幾乎都用)，這個算法其實是由LZ77算法加上一個變形的哈夫曼編碼組成的。大概算法流程是：“原始數(shù)據(jù)—>LZ77—>哈夫曼 ”這三個步驟。因啥夫曼樹仍有可能進(jìn)行壓縮，所以，實質(zhì)上的算法流程是：“原始數(shù)據(jù)—>LZ77—>(哈夫曼樹->CL壓縮)。 ”

　　先來聊聊“原始數(shù)據(jù)—>LZ77”這一層的思想。LZ77的詳細(xì)算法見相關(guān)文檔，本文不做贅述，僅描述涉及本文主題的一些思想。本質(zhì)上看，LZ77是基于對連續(xù)重復(fù)的字節(jié)片斷用指向的方式表示來實現(xiàn)壓縮。比如：有句英文叫business is business，為了簡化這個句子(注意有空格)，我們用business is (12，8)來表示，意思是括號內(nèi)的數(shù)字并非原始數(shù)據(jù)，而是代表從當(dāng)前位置向前12個字節(jié)，并且連續(xù)了8個字節(jié)的那段文字。這樣一來，文字部分就變得簡短了。當(dāng)然，我們一定會注意到，對于每個句子，要額外有信息表示到底是原始數(shù)據(jù)，還是指針類的數(shù)據(jù)。所以，整個壓縮后的數(shù)據(jù)，由三類不同的信息元素組成：本來就是這樣的文字、指向的位置，指向的長度，這三個元素即是lz77算法中的literal、distance和length。

　　給定任何一段字節(jié)流，如果使用LZ77算法進(jìn)行了壓縮，就一定會得到一段由literal、distance和length組成的字節(jié)流，那要如何區(qū)分這三類元素呢？distance和length總是成對出現(xiàn)的，所以，其實是如何區(qū)分這2類：1、literal    2、distance與length。通過適當(dāng)方法區(qū)分開這2類成員，就完成了LZ77算法的整個方法。

　　LZ77完成后，會形成一段較短的字節(jié)流。但這還不夠，還要經(jīng)過哈夫曼編碼進(jìn)行二次壓縮才能使壓縮比更為理想。

　　同樣的原因，對哈夫曼編碼原理不做過多解釋，僅對涉及本文主題的一些原理進(jìn)行概要性表述。關(guān)于哈夫曼編碼，舉個例子說明一下：如果有一段字節(jié)流(由字節(jié)為最小單位組成)，這些字節(jié)流中每種字節(jié)值的出現(xiàn)概率是不相同的，但每個字節(jié)都使用了8位進(jìn)行記錄，從概率角度可以知道，這一定是可以再做優(yōu)化的。哈夫曼就是針對這個思想的優(yōu)化，簡單地說，就如同生成了一個一一對應(yīng)的映射字典，用一些短的位代替經(jīng)常頻繁出現(xiàn)的字節(jié)，用一些長的位代替不常出現(xiàn)的字節(jié)，這樣，總體上就又進(jìn)行了一次壓縮

　　當(dāng)然，如何區(qū)分某個位置開始的是短的位還是些長的位呢？其實很簡單，只要約定：短位用了的，比他長的就不再用這個短位做前綴即可。比如，如果英文中不想用空格間隔開單詞了，只需要這樣設(shè)計：I如果表示我的意思，那其他所有單詞就不可能以I開頭。AM如果表示”是”的含義，那既沒有以A開頭的單詞，也沒有以AM開頭的更長的單詞了。以此類推，或許Iamchinese就不用加空格也能間隔開了。

　　因為LZ77壓縮后的數(shù)據(jù)元素中有l(wèi)iteral、distance和length，為了有效區(qū)分，deflate算法把把literal和length合起來，使用一顆哈夫曼樹。樹中編碼表述的數(shù)值如果小于255，即表示literal；如果等于256，表示本壓縮塊結(jié)束；如果大于256，表示length(需要減254得到)；如果是length，再在其后緊跟distance的編碼，distance使用單一的哈夫曼樹，實現(xiàn)方法見相關(guān)文檔。

　　literal、distance和length采用的哈夫曼樹本身也是個大的負(fù)擔(dān)，為了進(jìn)一步壓縮空間，deflate又對這兩顆哈夫曼樹進(jìn)行了一次壓縮，同樣的，主體上，也是采用哈夫曼算法，這樣，就是第三顆哈夫曼樹了。

　　簡單的結(jié)構(gòu)如下圖：

　　按照圖中結(jié)構(gòu)可知，一個gzip結(jié)構(gòu)大致如下圖所示：

　　可以看到，每個的壓縮包均是獨立存在的，包括其本身使用的動態(tài)哈夫曼樹，也僅存在于其作用域的壓縮包內(nèi)。故而，只要找到每個壓縮包的起始位置，如果這個包沒被破壞，就可解出其對應(yīng)內(nèi)容。

　　通常而言，因gzip的壓縮作業(yè)窗口僅32K，所以每個包的大小都不會很大，如果部分包損壞，只要找到下一個包的起始，即可正確解壓后續(xù)的數(shù)據(jù)。

　　如果gzip壓縮的是多個文件(并非tar之后再做gzip)，此種情況則相對容易。對于gzip而言，文件內(nèi)包含多個原始文件的，不可以多個文件共用一個壓縮包，也就是說如果有一個文件損壞，并不影響其他文件。這種思路容易實現(xiàn)，也可以使用linux下的gzip recover來完成修復(fù)。

　　我們重點要討論的如果單一文件(如TAR包)gzip后，若其中間損壞，如何正確解壓出后面的數(shù)據(jù)。這個思路如果理解了，gzip recover的算法就非常容易理解了，其算法也似乎有些弱了。

　　文章來源：http：//zhangyu.blog.51cto.com/197148/1592013