基于Huffman算法和LZ77算法的文件压缩的改进方向
基于Huffman算法和LZ77算法的文件壓縮（八）
到這里已經(jīng)簡單實現(xiàn)基于Huffman算法和LZ77算法的文件壓縮，
GitHub源碼：點我
根據(jù)基于Huffman算法和LZ77算法的文件壓縮（七）已經(jīng)介紹當(dāng)前項目的缺陷及改進(jìn)方法。
那么本文只講思想，不實現(xiàn)。
一、范式Huffman樹
范式hu?man樹是在hu?man樹的基礎(chǔ)之上，進(jìn)行了一些強(qiáng)制性的約定，即：對于同一層節(jié)點中，所有的 葉子節(jié)點都調(diào)整到左邊，然后，對于同一層的葉子節(jié)點按照符號順序從小到大調(diào)整 ，最后按照左0右1的方式 分配編碼。大家仔細(xì)觀察下圖：
從上表中可以得出一些結(jié)論：
范式hu?man樹該如何創(chuàng)建呢？ 范式hu?man樹根本不用創(chuàng)建，可以利用hu?man樹推到出來：
通過以上兩步就可以得出范式hu?man樹的碼表，然后按照上面的公式既可以計算出范式hu?man碼表。
二、 基于范式hu?man樹的壓縮與解壓縮
1 壓縮
壓縮文件的格式：
2 解壓縮
2. 根據(jù)編碼位長建立解碼表。
注意：范式huffman編碼有一個很重要的特性即長度為i的碼字的前j位的數(shù)值大于長度為j的碼字的數(shù)值，其中i > j。
循環(huán)進(jìn)行一下操作，直到所有的比特流解析完成：設(shè)i=0
4. Huffman壓縮LZ77的結(jié)果
采用huffman樹對LZ77的結(jié)果壓縮時，GZIP將原字符和長度放在一起壓縮，因為這兩部分都占一個字節(jié)，將距離單獨壓縮。
4.1 距離的壓縮
Z77在查找緩沖區(qū)中找匹配時，最長的距離不會超過32K，即最大的距離為32768，即距離的范圍是[1,32768]，距離會非常多，雖然不會達(dá)到32768個，但是如果對于一個比較大的文件進(jìn)行LZ編碼，distance上千還是很正常的，因此會導(dǎo)致huffman樹非常大，計算量和內(nèi)存消耗都會超過當(dāng)時的硬件條件，怎么辦呢？
GZIP提供了一種非常好的方式，將distance劃分成多個區(qū)間，每個區(qū)間當(dāng)做一個整數(shù)來看，該整數(shù)稱為Distance Code。當(dāng)一個distance落到某個區(qū)間，則相當(dāng)于出現(xiàn)了那個Code，雖然distance很多，Distance Code可以劃分少一點，即多個distance對應(yīng)一個Distance Code，最后只需要對Distance Code進(jìn)行huffman編碼即可。得到Code后，Distance Code再根據(jù)一定規(guī)則擴(kuò)展出來。GZIP最終將distance劃分成了30個區(qū)間，如下圖：
Code表示區(qū)間編號，[0,29]，總共是30個區(qū)間,每個區(qū)間容納distance的個數(shù)剛好是2的n次冪，huffman樹只對0~29這30個Code進(jìn)行編碼，
得到編碼，Extra bits表示distance的編碼需要再Code的編碼基礎(chǔ)上擴(kuò)展的比特位個數(shù)，
比如：0表示不擴(kuò)展，13表示要擴(kuò)展13位，因為最大的區(qū)間中包含的distance數(shù)量為8192個。
比如：17~24這個區(qū)間的huffman編碼為110，因為這個區(qū)間有8個整數(shù)，于是按照上述表格的規(guī)則就可以得到所有distance的編碼：
17-----> 110 000
18-----> 110 001
19-----> 110 010
20-----> 110 011
21-----> 110 100
22-----> 110 101
23-----> 110 110
24-----> 110 111
這樣就可以將樹的高度降低，計算的時間和空間復(fù)雜度都降低了，而且擴(kuò)展起來也比較簡單
4.2 原字符和長度的壓縮
原字符表示在LZ77中未匹配的字符，長度表示重復(fù)字符串的個數(shù)，都占了一個字節(jié)，因此GZIP將其壓縮合二為一了，即對于原字符和距離采用同一棵huffman樹進(jìn)行處理。
原字符的范圍是[0, 255]，距離是[3, 258]，如何進(jìn)行處理呢？
GZIP用整數(shù)0~255表示原字符，256表示結(jié)束標(biāo)志，即解碼以后是256表示解碼結(jié)束，從257開始表示距離，比如：257表示重復(fù)3個字符，258重復(fù)4個字符，但GZIP并沒有一直這么一一對應(yīng)，而是采用了和distance類似的方式進(jìn)行分區(qū)，總共將距離劃分成了29個區(qū)間，如下圖
即原字符和距離的hu?man編碼的輸入元素一共有285個，當(dāng)解碼器接收到一個比特流的時候，首先可以按 照literal/length這個碼表來解碼，如果解出來是0-255，就表示未匹配字符，如果是256，那自然就結(jié)束， 如果是257-285之間，則表示length，把后面擴(kuò)展比特加上形成length后，后面的比特流肯定就表示 distance，
因此，實際上通過一個Hu?man碼表，對各類情況進(jìn)行了統(tǒng)一，而不是通過加一個什么標(biāo)志來 區(qū)分到底是literal還是重復(fù)字符串。
到此GZIP的主體壓縮過程基本出來了，第一步：先是采用LZ77對源文件進(jìn)行壓縮，第二步采用hu?man對 LZ77的壓縮結(jié)果進(jìn)行再次壓縮，因為原字符和長度使用一棵hu?man樹，將其稱為hu?man碼表1， distance對應(yīng)hu?man樹稱為hu?man碼表2，而最終的hu?man樹信息只需要使用碼字長度保存即可，稱之 為CL(Code Length)，即兩個碼表長度分別為：CL1、CL2。
碼樹記錄下來，對原字符的編碼比特流稱為LIT比 特流，對distance編碼的比特流稱為DIST比特流。按照上面的方法，LZ的編碼結(jié)果就變成四塊：CL1、CL2、 LIT比特流、DIST比特流 。
5. CL的游程編碼
編碼的長度即CL也是一對數(shù)字，該部分信息理論也可以使用huffman樹再次壓縮，但是GZIP并沒有對其使用huffman樹進(jìn)行壓縮，而是使用了游程編碼。
游程，即一段完全相同的數(shù)的序列。游程編碼，即對一段連續(xù)相同的數(shù)，記錄這個數(shù)一次，緊接著記錄出現(xiàn)了多少個。比如CL序列如下：
4, 4, 4, 4, 4, 3, 3, 3, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2
那么，游程編碼的結(jié)果為：
4, 16, 01（二進(jìn)制）, 3, 3, 3, 6, 16, 11（二進(jìn)制）, 16, 00（二進(jìn)制）, 17,011（二進(jìn)制）, 2, 16, 00（二進(jìn)制）
這是什么意思呢？因為CL的范圍是0-15，GZIP認(rèn)為重復(fù)出現(xiàn)2次太短就不用游程編碼了，所以游程長度從3開始。
用16這個特殊的數(shù)表示重復(fù)出現(xiàn)3、4、5、6個這樣一個游程，分別后面跟著00、01、10、11表示（實際存儲的時候需要低比特優(yōu)先存儲，需要把比特倒序來存，一些例子有時候會忽略這點，實際寫程序的時候一定要注意，否則會得到錯誤結(jié)果）。
于是4,4,4,4,4,這段游程記錄為4,16,01，也就是說，4這個數(shù)，后面還會連續(xù)出現(xiàn)了4次。6,16,11,16,00表示6后面還連續(xù)跟著6個6，再跟著3個6；
因為連續(xù)的0出現(xiàn)的可能很多，所以用17、18這兩個特殊的數(shù)專門表示0游程，17后面跟著3個比特分別記錄長度為3-10（總共8種可能）的游程；
18后面跟著7個比特表示11-138（總共128種可能）的游程。17,011（二進(jìn)制）表示連續(xù)出現(xiàn)6個0；18,0111110（二進(jìn)制）表示連續(xù)出現(xiàn)62個0。
總之記住，0-15是CL可能出現(xiàn)的值，16表示除了0以外的其它游程；17、18表示0游程。因為二進(jìn)制實際上也是個整數(shù)，所以上面的序列用整數(shù)表示為：
4, 16, 1, 3, 3, 3, 6, 16, 3, 16, 0, 17, 3, 2, 16, 0
原字符和長度的編碼符號總共有286個(256個原字符+1個結(jié)束標(biāo)記+29個長度區(qū)間)，distance編碼區(qū)間總共30個，因此這棵樹不會特別深，huffman編碼后的碼字長度不會特別長，不會超過15，即樹的深度不會超過15，因此CL1和CL2這兩個序列的任意整數(shù)的值的范圍是0-15,0表示沒有出現(xiàn)，故GZIP對CL1和CL2使用了游程編碼。
因為游程編碼之后整數(shù)值的范圍是0-18，這個序列稱之為SQ，因為碼字長度有CL1、CL2，因此最后有SQ1和SQ2兩組數(shù)據(jù)。GZIP采用第三個huffman樹對SQ1和SQ2再次進(jìn)行huffman壓縮。
通過統(tǒng)計各個整數(shù)（0-18范圍內(nèi)）的出現(xiàn)次數(shù)，按照相同的思路，對SQ1和SQ2進(jìn)行了Huffman編碼，得到的碼流記為SQ1 bits和SQ2 bits。同時，這里又需要記錄第三個碼表，稱為Huffman碼表3。同理，這個碼表也用相同的方法記錄，也等效為一個碼長序列，稱為CCL。到此GZIP壓縮才算真正結(jié)束，這個算法命名為Deflate算法：
6. 數(shù)據(jù)存儲格式
因為被壓縮的文件可能非常大，會嚴(yán)重影響壓縮率，因此GZIP采用了分段壓縮處理，每段的壓縮結(jié)果表示如 下：
總結(jié)：
1. 范式Huffman樹是用來解決Huffman樹當(dāng)中字符頻度信息、Huffman樹太大的，用范式Huffman樹當(dāng)中每個字符的位長來代替Huffman樹當(dāng)中的字符頻度，Huffman樹當(dāng)中每個字符的頻度是[0，65535]，范式Huffman樹的位長是[0，15]。
如可以采用...000000023456200000...共256個字節(jié)這樣的方式來存儲字符位長信息，多次重復(fù)出現(xiàn)的數(shù)字可以采用CL游程編碼解決。這樣就大大減少了標(biāo)記信息所占用的空間，使用范式Huffman樹，大大減少了遍歷Huffman樹的時間，提高壓縮的效率。
2. 對于LZ77壓縮的結(jié)果當(dāng)中，有原字符也有長度距離信息，Huffman的壓縮方法是把標(biāo)記信息也壓縮到Huffman樹當(dāng)中，那樣是非常浪費空間的，范式Huffman樹采用將distance劃分成多個區(qū)間的方法，也在一定成程度上節(jié)省了空間
3. 范式Huffman樹對原字符和長度的壓縮是采用一起壓縮的方法，因為二者都占一個字節(jié)，那么如何區(qū)分呢？因為一個字符的范圍是[0,255],所以用來表示字符，用256來分割，[256，285]這29個區(qū)間來表示長度
總結(jié)
以上是生活随笔為你收集整理的基于Huffman算法和LZ77算法的文件压缩的改进方向的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 基于LZ77算法的文件解压缩项目缺陷分析
- 下一篇： 阿里云linux上安装与配置Mysql