一、實(shí)驗(yàn)要求：

1 采用熵編碼對(duì)《小王子》文本進(jìn)行壓縮，生成壓縮文件；

2 將壓縮文件解壓，并與源文件比較；

3 從香農(nóng)編碼、Huffman編碼、Fano編碼中選擇一種；

4 計(jì)算編碼效率，并與理論值對(duì)比，分析差異原因。

二、編碼思路分析：

1. Huffman編碼

（1）首先導(dǎo)入文件，進(jìn)行字符概率計(jì)算，將字符和頻率按順序錄入表中。

（2）進(jìn)行數(shù)據(jù)清洗，清除出現(xiàn)頻率較低的無(wú)用字符。

（3）生成霍夫曼樹(shù)。

????<1>將數(shù)據(jù)從小到大進(jìn)行排序,每個(gè)數(shù)據(jù)都是一個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)可以看成是一個(gè)二叉樹(shù)。

????<2>取出根節(jié)點(diǎn)權(quán)值最小的兩個(gè)二叉樹(shù)。

????<3>組成一棵新二叉樹(shù), 其中新二叉樹(shù)的根節(jié)點(diǎn)的權(quán)值是前面兩個(gè)二叉樹(shù)根節(jié)點(diǎn)權(quán)值的和。????

????<4>再將這個(gè)新的二叉樹(shù)，以根節(jié)點(diǎn)的權(quán)值大小再次排序，遞歸<1>-<4>，得到霍夫曼樹(shù)。

（4）將純英文文本用霍夫曼編碼，并輸出。

（5）壓縮文件：將所有字符以霍夫曼樹(shù)轉(zhuǎn)化為01序列，再轉(zhuǎn)化為ASCⅡ碼存儲(chǔ)為txt格式，并計(jì)算壓縮率和編碼效率。

（6）解壓文件：根據(jù)編碼表重建霍夫曼樹(shù)，依據(jù)讀取霍夫曼碼字進(jìn)行遞歸，解碼，輸出文件。

（7）判斷是否為無(wú)失真壓縮。

2. Shannon編碼

（除去編碼過(guò)程，其余過(guò)程與Huffman編碼過(guò)程相似，故以下只介紹Shannon編碼過(guò)程）

（1）對(duì)于一個(gè)給定的符號(hào)列表，制定了概率相應(yīng)的列表或頻率計(jì)數(shù)，使每個(gè)符號(hào)的相對(duì)發(fā)生頻率是已知。

（2）排序根據(jù)頻率的符號(hào)列表，最常出現(xiàn)的符號(hào)在左邊，最少出現(xiàn)的符號(hào)在右邊。

（3）清單分為兩部分，使左邊部分的總頻率和盡可能接近右邊部分的總頻率和。

（4）該列表的左半邊分配二進(jìn)制數(shù)字0，右半邊是分配的數(shù)字1。這意味著，在第一半符號(hào)代都是將所有從0開(kāi)始，第二半的代碼都從1開(kāi)始。

（5）對(duì)左、右半部分遞歸應(yīng)用步驟3和4，細(xì)分群體，并添加位的代碼，直到每個(gè)符號(hào)已成為一個(gè)相應(yīng)的代碼樹(shù)的葉。

3. APP搭建

（1）利用Matlab的Appdesigner，搭建壓縮解壓小程序。

（2）在設(shè)計(jì)界面規(guī)劃顯示變量和控制按鍵控件，調(diào)節(jié)回調(diào)函數(shù)，完善程序功能。

三、實(shí)驗(yàn)過(guò)程：

1、讀入文件后統(tǒng)計(jì)所有字符差別，數(shù)量，計(jì)算頻率，進(jìn)行排序

生成霍夫曼樹(shù)。

3、將純英文文本用霍夫曼編碼，并輸出。

4、壓縮文件：將所有字符以霍夫曼樹(shù)轉(zhuǎn)化為01序列，并計(jì)算壓縮率和編碼效率。

壓縮率為：56.8%

理論壓縮效率：56.27%

編碼效率：99.33%

四、結(jié)論及分析：

1、我們使用了霍夫曼編碼，因?yàn)榛舴蚵幋a所形成的碼字不是唯一的，但編碼效率是唯一的。對(duì)于同一個(gè)信息源，無(wú)論上述的前后順序如何排列，它的平均碼長(zhǎng)是不會(huì)改變的，所以編碼效率是唯一的。正是這樣的編碼方式使得霍夫曼編碼可以用盡可能少的內(nèi)存存儲(chǔ)盡可能多的內(nèi)容，我們對(duì)《小王子》進(jìn)行壓縮與解壓，通過(guò)對(duì)壓縮、解壓程序的運(yùn)行，計(jì)算出編碼效率為99.33%，壓縮效率為56.8%，理論壓縮效率：56.27%，實(shí)際壓縮效率比理論值大的原因是因?yàn)閴嚎s的適合需要保證最后幾位碼元是8的整數(shù)倍，如果不是8的整數(shù)倍的話，則添加缺的位數(shù)，這里添加0來(lái)補(bǔ)充，這樣的話就會(huì)導(dǎo)致實(shí)際文件比原來(lái)的文件多幾個(gè)0bit，最終實(shí)際壓縮效率略大于理論壓縮效率。

2、通過(guò)實(shí)驗(yàn)，我們發(fā)現(xiàn)了許多有關(guān)霍夫曼編碼的特點(diǎn)：

?? （1）編出來(lái)的碼都是異字頭碼，可以用來(lái)保證編碼的唯一可譯性。

?? （2）由于編碼長(zhǎng)度可變，因此譯碼時(shí)間較長(zhǎng)，使得霍夫曼編碼的壓縮和解壓相當(dāng)費(fèi)時(shí)。

?? （3）由于"0"與"1"的指定是任意的，故由上述過(guò)程編出的最佳碼不是唯一的，但其平均碼長(zhǎng)是一樣的，故不影響編碼效率與數(shù)據(jù)壓縮性能。

五、其他壓縮方法的嘗試：

　　在完成霍夫曼編碼后，我們對(duì)fano編碼和shannon編碼壓縮也進(jìn)行了嘗試。

Fano編碼的過(guò)程：

1、對(duì)于一個(gè)給定的符號(hào)列表，制定了概率相應(yīng)的列表或頻率計(jì)數(shù)，使每個(gè)符號(hào)的相對(duì)發(fā)生頻率是已知。

2、排序根據(jù)頻率的符號(hào)列表，最常出現(xiàn)的符號(hào)在左邊，最少出現(xiàn)的符號(hào)在右邊。

3、清單分為兩部分，使左邊部分的總頻率和盡可能接近右邊部分的總頻率和。

4、該列表的左半邊分配二進(jìn)制數(shù)字0，右半邊是分配的數(shù)字1。這意味著，在第一半符號(hào)代都是將所有從0開(kāi)始，第二半的代碼都從1開(kāi)始。

5、對(duì)左、右半部分遞歸應(yīng)用步驟3和4，細(xì)分群體，并添加位的代碼，直到每個(gè)符號(hào)已成為一個(gè)相應(yīng)的代碼樹(shù)的葉。

編碼表

壓縮文件

壓縮效率

分析：fano編碼比huffman編碼的編碼效率低的原因是fano編碼不可能每次都做到平均平分概率，并且從大概率分的時(shí)候，容易導(dǎo)致某一側(cè)的概率與另一側(cè)的差值過(guò)大，最終導(dǎo)致編碼效率降低。

Shannon編碼：Shannon編碼是一種常見(jiàn)的可變字長(zhǎng)編碼，與哈夫曼編碼相似，香農(nóng)編碼的效率不高，實(shí)用性不大，但對(duì)其他編碼方法有很好的理論指導(dǎo)意義。一般情況下，按照香農(nóng)編碼方法編出來(lái)的碼，其平均碼長(zhǎng)不是最短的。即不是緊致碼(最佳碼)。只有當(dāng)信源符號(hào)的概率分布使不等式左邊的等號(hào)成立時(shí)，編碼效率才達(dá)到最高.我們對(duì)其也進(jìn)行了嘗試。Shannon編碼的主要思路是將字符按概率從大到小排序后，將概率累加（除最小概率之外），根據(jù)概率算出其信息熵確定碼長(zhǎng)，根據(jù)碼長(zhǎng)將其累加概率轉(zhuǎn)化為2進(jìn)制碼即shannon碼。具體思路如下：

將信源符號(hào)按其出現(xiàn)概率從大到小排序；

計(jì)算出各概率對(duì)應(yīng)的碼字長(zhǎng)度；

計(jì)算累加概率；

把各個(gè)累加概率由十進(jìn)制轉(zhuǎn)化為二進(jìn)制，取該二進(jìn)制數(shù)的前Ni位作為對(duì)應(yīng)信源符號(hào)的碼字。

二分法香農(nóng)-范諾編碼方法的步驟如下：

將信源符號(hào)按照其出現(xiàn)概率從大到小排序；

從這個(gè)概率集合中的某個(gè)位置將其分為兩個(gè)子集合，并盡量使兩個(gè)子集合的概率和近似相等，給前面一個(gè)子集合賦值為0，后面一個(gè)子集合賦值為1；

重復(fù)步驟(2)，直到各個(gè)子集合中只有一個(gè)元素為止；

將每個(gè)元素所屬的子集合的值依次串起來(lái)，即可得到各個(gè)元素的香農(nóng)編碼。

編碼表如下：

壓縮效率：

理論壓縮效率：62.85%

實(shí)際壓縮效率：62.85%

編碼效率：89.51%

六、遇到的問(wèn)題及解決方法：

1、壓縮之后輸出的文件內(nèi)容是01的二進(jìn)制序列，導(dǎo)致壓縮之后的文件大小要比源文件大小還要大，壓縮文件大小為425kb，源文件大小僅為96.4kb。

????????解決方法：經(jīng)查證后，將源文件代碼通過(guò)asc碼值轉(zhuǎn)換之后，轉(zhuǎn)化成為二進(jìn)制代碼。即可解決這個(gè)問(wèn)題。

2、如何剔除頻率過(guò)低的異常字符

????????解決辦法：判斷字符是不是ascii碼。正常字符都是ascii碼，因此某個(gè)字符如果是ascii碼，則進(jìn)行保留，不是則清除。

3、解碼時(shí)8bit碼長(zhǎng)大小長(zhǎng)短不一

????????原因：如某個(gè)字符ascii碼為 01111111，壓縮時(shí)沒(méi)問(wèn)題，解壓縮時(shí)，由于開(kāi)始的0沒(méi)有值，因此解壓縮后變?yōu)?111111七個(gè)1，少了個(gè)0。

????????解決方法：當(dāng)某個(gè)字符解碼時(shí)，判斷是不是8個(gè)bit，如果不是，則在前面補(bǔ)充缺失的0。

源碼資源網(wǎng)址：https://download.csdn.net/download/m0_53374676/85963294

總結(jié)

以上是生活随笔為你收集整理的Huffman编码、Shannon编码、Ｆａｎｏ编码——《小王子》文本压缩与解压的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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