一、實驗要求：

1 采用熵編碼對《小王子》文本進行壓縮，生成壓縮文件；

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

3 從香農編碼、Huffman編碼、Fano編碼中選擇一種；

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

二、編碼思路分析：

1. Huffman編碼

（1）首先導入文件，進行字符概率計算，將字符和頻率按順序錄入表中。

（2）進行數據清洗，清除出現頻率較低的無用字符。

（3）生成霍夫曼樹。

????<1>將數據從小到大進行排序,每個數據都是一個節點，每個節點可以看成是一個二叉樹。

????<2>取出根節點權值最小的兩個二叉樹。

????<3>組成一棵新二叉樹, 其中新二叉樹的根節點的權值是前面兩個二叉樹根節點權值的和。????

????<4>再將這個新的二叉樹，以根節點的權值大小再次排序，遞歸<1>-<4>，得到霍夫曼樹。

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

（5）壓縮文件：將所有字符以霍夫曼樹轉化為01序列，再轉化為ASCⅡ碼存儲為txt格式，并計算壓縮率和編碼效率。

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

（7）判斷是否為無失真壓縮。

2. Shannon編碼

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

（1）對于一個給定的符號列表，制定了概率相應的列表或頻率計數，使每個符號的相對發生頻率是已知。

（2）排序根據頻率的符號列表，最常出現的符號在左邊，最少出現的符號在右邊。

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

（4）該列表的左半邊分配二進制數字0，右半邊是分配的數字1。這意味著，在第一半符號代都是將所有從0開始，第二半的代碼都從1開始。

（5）對左、右半部分遞歸應用步驟3和4，細分群體，并添加位的代碼，直到每個符號已成為一個相應的代碼樹的葉。

3. APP搭建

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

（2）在設計界面規劃顯示變量和控制按鍵控件，調節回調函數，完善程序功能。

三、實驗過程：

1、讀入文件后統計所有字符差別，數量，計算頻率，進行排序

生成霍夫曼樹。

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

4、壓縮文件：將所有字符以霍夫曼樹轉化為01序列，并計算壓縮率和編碼效率。

壓縮率為：56.8%

理論壓縮效率：56.27%

編碼效率：99.33%

四、結論及分析：

1、我們使用了霍夫曼編碼，因為霍夫曼編碼所形成的碼字不是唯一的，但編碼效率是唯一的。對于同一個信息源，無論上述的前后順序如何排列，它的平均碼長是不會改變的，所以編碼效率是唯一的。正是這樣的編碼方式使得霍夫曼編碼可以用盡可能少的內存存儲盡可能多的內容，我們對《小王子》進行壓縮與解壓，通過對壓縮、解壓程序的運行，計算出編碼效率為99.33%，壓縮效率為56.8%，理論壓縮效率：56.27%，實際壓縮效率比理論值大的原因是因為壓縮的適合需要保證最后幾位碼元是8的整數倍，如果不是8的整數倍的話，則添加缺的位數，這里添加0來補充，這樣的話就會導致實際文件比原來的文件多幾個0bit，最終實際壓縮效率略大于理論壓縮效率。

2、通過實驗，我們發現了許多有關霍夫曼編碼的特點：

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

?? （2）由于編碼長度可變，因此譯碼時間較長，使得霍夫曼編碼的壓縮和解壓相當費時。

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

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

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

Fano編碼的過程：

1、對于一個給定的符號列表，制定了概率相應的列表或頻率計數，使每個符號的相對發生頻率是已知。

2、排序根據頻率的符號列表，最常出現的符號在左邊，最少出現的符號在右邊。

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

4、該列表的左半邊分配二進制數字0，右半邊是分配的數字1。這意味著，在第一半符號代都是將所有從0開始，第二半的代碼都從1開始。

5、對左、右半部分遞歸應用步驟3和4，細分群體，并添加位的代碼，直到每個符號已成為一個相應的代碼樹的葉。

編碼表

壓縮文件

壓縮效率

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

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

將信源符號按其出現概率從大到小排序；

計算出各概率對應的碼字長度；

計算累加概率；

把各個累加概率由十進制轉化為二進制，取該二進制數的前Ni位作為對應信源符號的碼字。

二分法香農-范諾編碼方法的步驟如下：

將信源符號按照其出現概率從大到小排序；

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

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

將每個元素所屬的子集合的值依次串起來，即可得到各個元素的香農編碼。

編碼表如下：

壓縮效率：

理論壓縮效率：62.85%

實際壓縮效率：62.85%

編碼效率：89.51%

六、遇到的問題及解決方法：

1、壓縮之后輸出的文件內容是01的二進制序列，導致壓縮之后的文件大小要比源文件大小還要大，壓縮文件大小為425kb，源文件大小僅為96.4kb。

????????解決方法：經查證后，將源文件代碼通過asc碼值轉換之后，轉化成為二進制代碼。即可解決這個問題。

2、如何剔除頻率過低的異常字符

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

3、解碼時8bit碼長大小長短不一

????????原因：如某個字符ascii碼為 01111111，壓縮時沒問題，解壓縮時，由于開始的0沒有值，因此解壓縮后變為1111111七個1，少了個0。

????????解決方法：當某個字符解碼時，判斷是不是8個bit，如果不是，則在前面補充缺失的0。

源碼資源網址：https://download.csdn.net/download/m0_53374676/85963294

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。