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

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

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

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

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