Huffman編碼在不同場(chǎng)景中的應(yīng)用研究

陳泓夫

摘 要 文章主要針對(duì)不同場(chǎng)景的信源進(jìn)行概率統(tǒng)計(jì)，并進(jìn)行Huffman編碼。通過(guò)編碼分析得到了不同信源Huffman編碼的區(qū)別，并將編碼長(zhǎng)度與香農(nóng)極限進(jìn)行了比較。發(fā)現(xiàn)在信源長(zhǎng)度較長(zhǎng)時(shí)，實(shí)際Huffman編碼長(zhǎng)度接近于香農(nóng)極限，而在信源較短時(shí)，則與香農(nóng)極限差別較大。

關(guān)鍵詞 信源編碼；Huffman編碼；香農(nóng)極限

中圖分類號(hào) TP3 文獻(xiàn)標(biāo)識(shí)碼 A 文章編號(hào) 1674-6708（2018）204-0148-02

信源編碼是將人類可以感知的機(jī)械信號(hào)轉(zhuǎn)化為計(jì)算機(jī)或者數(shù)字邏輯電路可以感知的電信號(hào)，數(shù)學(xué)上表示為“01”串，是通信領(lǐng)域的一個(gè)重要環(huán)節(jié)。除進(jìn)行信息轉(zhuǎn)化，信源編碼要消除信息冗余，從而提高傳輸效率，所以信源編碼又叫信源壓縮編碼。

文章主要分為以下幾個(gè)方面：1）統(tǒng)計(jì)了特定場(chǎng)景信源的符號(hào)特征，得到了其頻率；2）把得到的頻率作為概率，對(duì)該場(chǎng)景的信源進(jìn)行了Huffman編碼，并與香農(nóng)極限進(jìn)行了比較；3）針對(duì)不同場(chǎng)景的Huffman編碼結(jié)果進(jìn)行了分析。

本文的剩余章節(jié)安排如下：第1章介紹Huffman編碼的基本原理；第2章介紹一個(gè)特定場(chǎng)景下的Huffman編碼；第3章介紹不同場(chǎng)景的 Huffman編碼研究分析；第4章對(duì)本文進(jìn)行總結(jié)。

1 基本原理

文章主要介紹Huffman編碼的基本原理。Huffman編碼基于Huffman樹的構(gòu)造，構(gòu)造過(guò)程如下：

1）統(tǒng)計(jì)字符序列的每種字符的頻率，并為每種字符建立一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)權(quán)重為其頻率；

2）初始化最小優(yōu)先隊(duì)列中，把上述的結(jié)點(diǎn)全部插入到隊(duì)列中；

3）取出優(yōu)先隊(duì)列的前兩種符號(hào)節(jié)點(diǎn)，并從優(yōu)先隊(duì)列中刪除；

4）新建一個(gè)父節(jié)點(diǎn)，并把上述兩個(gè)節(jié)點(diǎn)作為其左右孩子節(jié)點(diǎn)，父節(jié)點(diǎn)的權(quán)值為左右節(jié)點(diǎn)之和；

5）如果此時(shí)優(yōu)先隊(duì)列為空，則退出并返回父節(jié)點(diǎn)的指針。否則把父節(jié)點(diǎn)插入到優(yōu)先隊(duì)列中，重復(fù)步驟3）。

完成構(gòu)造Huffman樹之后，將每個(gè)父節(jié)點(diǎn)的左子節(jié)點(diǎn)編碼為1（0），右子節(jié)點(diǎn)編碼為0（1），每個(gè)字符正好是Huffman樹的葉子節(jié)點(diǎn)，從根節(jié)點(diǎn)做深度優(yōu)先搜索即可得到并將路徑上節(jié)點(diǎn)的編碼拼在一起即為該字符的Huffman編碼。在本文中，用上下子節(jié)點(diǎn)來(lái)代替左右子節(jié)點(diǎn)。

2 特定場(chǎng)景下的Huffman編碼

文章摘取了BBC一篇新聞稿，對(duì)其Huffman編碼情況進(jìn)行了研究分析。首先我們統(tǒng)計(jì)了該新聞稿的字符頻率情況（共12 524個(gè)字符），如表1所示。

將上標(biāo)的字符頻率作為字符概率，構(gòu)建得到的Huffman樹如圖2所示。

3 不同場(chǎng)景下的Huffman編碼分析

更換一個(gè)場(chǎng)景的信源做統(tǒng)計(jì)，將統(tǒng)計(jì)得到的頻率作為概率使用，并進(jìn)行Huffman編碼，發(fā)現(xiàn)當(dāng)統(tǒng)計(jì)字符個(gè)數(shù)較多時(shí)（如超過(guò)10 000個(gè)字符），各個(gè)字符的統(tǒng)計(jì)頻率趨于穩(wěn)定，Huffman編碼長(zhǎng)度非常接近香農(nóng)極限長(zhǎng)度，所以，Huffman編碼是一種熵編碼。

4 結(jié)論

文章主要介紹了Huffman編碼在實(shí)際信源場(chǎng)景中的應(yīng)用，并對(duì)不同應(yīng)用場(chǎng)景下的編碼進(jìn)行了研究分析，在不同場(chǎng)景下，各個(gè)字符的統(tǒng)計(jì)頻率趨于穩(wěn)定，所以，Huffman編碼形式趨于穩(wěn)定。Huffman在實(shí)際應(yīng)用中的編碼長(zhǎng)度趨近于香農(nóng)極限。

參考文獻(xiàn)

[1]Shannon C E.A mathematical theory of communica tion[J].ACM SIGMOBILE Mobile Computing and Communications Review，2001，5（1）：3-55.

[2]Knuth D E.Dynamic Huffman coding[J].Journal of algorithms，1985，6（2）：163-180.表1endprint