最近需要把采集到的圖像數(shù)據(jù)進(jìn)行壓縮，節(jié)省存儲空間。綜合考慮壓縮比和速度，決定采用靜態(tài)Huffman編碼，使用預(yù)先計(jì)算好的字典對數(shù)據(jù)進(jìn)行壓縮，這樣壓縮速度可以非常高，使用多線程之后可以進(jìn)行實(shí)時壓縮，但解壓速度比較慢。

于是去gzip的代碼里面找了一下，在一個叫unpack.c的文件里發(fā)現(xiàn)了Huffman解碼的實(shí)現(xiàn)，gzip的解碼確實(shí)很高效，其中的原因，簡單來說就是多用內(nèi)存，少用循環(huán)。

假設(shè)我們要壓縮的字符串是“ABBBCC”，計(jì)算得到Huffman編碼如下：

字符

計(jì)數(shù)

編碼

A

1

00

B

3

1

C

2

01

編碼后的二進(jìn)制串是 0011101

要對編碼后的字符串進(jìn)行解碼，比較容易想到的方法是這樣的，構(gòu)造這么一個字典

編碼

字符

1

B

00

A

01

C

這個字典是原始的編碼表按字符編碼的長度進(jìn)行排序，解碼的時候就在字典里面順序地查找編碼

對于這個例子而言是這樣一個過程

對二進(jìn)制串0011101從左往右解碼，先嘗試編碼1(對應(yīng)字符B)，發(fā)現(xiàn)不對，因?yàn)樽钭筮吺?，因此再嘗試字典的第二個編碼00(對應(yīng)A)，發(fā)現(xiàn)是正確的，最左邊就是00，因此解碼出字符A，將二進(jìn)制串左移兩位得到11101，繼續(xù)從B的編碼1開始嘗試。最后能解碼出ABBBCC這個原始編碼。

這個解碼方法的問題就是每解碼一個字符串都要在字典里面循環(huán)一遍，效率不高。

gzip的方法

對于我們的例子gzip會構(gòu)造這么一個字典

索引

索引編碼

編碼

字符

2

10

1

B

3

11

1

B

0

00

00

A

1

01

01

C

這個字典的特點(diǎn)就是有索引，因此查找編碼的時候不用循環(huán)，而是計(jì)算索引直接定位到對應(yīng)的編碼。字典的構(gòu)造方法是根據(jù)編碼生成索引編碼，所有索引編碼的長度是相同的，從二叉樹的角度來看就是把所有的子樹都補(bǔ)到同樣的長度，然后所有非編碼節(jié)點(diǎn)(如11)都和其父節(jié)點(diǎn)(如1)對應(yīng)同一個字符(如B)。

這個方法同樣也是一種空間換時間的方法，隨著編碼長度的增加，內(nèi)存消耗會指數(shù)增長，因此當(dāng)編碼太長時，gzip會使用多個字典，將長編碼放在一些單獨(dú)的字典里面，減小內(nèi)存消耗。

總結(jié)

以上是生活随笔為你收集整理的Php 哈夫曼 压缩图片,快速Huffman解码的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。