哈夫曼編碼的分析與實現(xiàn)

1、吉林建筑大學(xué)吉林建筑大學(xué)電氣與計算機學(xué)院電氣與計算機學(xué)院信息理論與編碼課程設(shè)計報告信息理論與編碼課程設(shè)計報告設(shè)計題目：設(shè)計題目：哈夫曼編碼的分析與實現(xiàn)哈夫曼編碼的分析與實現(xiàn)專業(yè)班級：專業(yè)班級：電子信息工程電子信息工程131學(xué)生姓名：學(xué)生姓名：學(xué)號：號：指導(dǎo)教師：指導(dǎo)教師：設(shè)計時間：設(shè)計時間：2016.11.21－2016.12.2教師評語：成績評閱教師日期1第2章哈夫曼編碼的分析與實現(xiàn)2.1哈夫曼編碼介紹及原理哈夫曼編碼(Huffman

2、Coding)是一種熵編碼編碼壓縮方式，哈夫曼編碼是可變字長編碼(VLC)的一種。哈夫曼壓縮是個無損的壓縮算法，一般用來壓縮文本和程序文件。哈夫曼壓縮屬于可變代碼長度算法一族。意思是不同符號（例如，文本文件中的字符）用一個特定長度的位序列替代。因此，在文件中出現(xiàn)頻率高的符號，使用短的位序列，而那些很少出現(xiàn)的符號，則用較長的位序列。哈夫曼編碼的碼長是變化的，對于出現(xiàn)頻率高的信息，編碼的長度較短；而對于出現(xiàn)頻率低的信息，編碼長度較長。這樣，

3、處理全部信息的總碼長一定小于實際信息的符號長度。下面給出具體的Huffman編碼算法。(1)首先統(tǒng)計出每個符號出現(xiàn)的頻率，如本次課程設(shè)計x1到x7的出現(xiàn)頻率分別為0.39，0.17，0.12，0.1，0.07，0.06，0.05，0.04。(2)從左到右把上述頻率按從小到大的順序排列。(3)每一次選出最小的兩個值，作為二叉樹的兩個葉子節(jié)點，將和作為它們的根節(jié)點，這兩個葉子節(jié)點不再參與比較，新的根節(jié)點參與比較。(4)重復(fù)(3)，直到最后得

4、到和為1的根節(jié)點。(5)將形成的二叉樹的左節(jié)點標(biāo)0，右節(jié)點標(biāo)1。把從最上面的根節(jié)點到最下面的葉子節(jié)點途中遇到的01序列串起來，就得到了各個符號的編碼。2.2哈夫曼編碼步驟（1）將信源消息符號按其出現(xiàn)的概率大小依次排列為12nppp????（2）取兩個概率最小的字母分別分配以0和1兩個碼元，并將這兩個概率相加作為一個新字母的概率，與未分配的二進制符號的字母重新排隊。（3）對重排后的兩個概率小符號重復(fù)步驟（2）的過程。（4）不斷繼續(xù)上述過程