汽配人首頁 > 問答首頁

霍夫曼編碼器

要求: a. 隨機(jī)輸入一段英文(含標(biāo)點(diǎn)、空格以及大小寫的區(qū)分，標(biāo)點(diǎn)僅限逗號(hào)“，”和句點(diǎn)“.”)； b. 統(tǒng)計(jì)各種符號(hào)出現(xiàn)的頻度； c. 進(jìn)行Huffman編碼（以二進(jìn)制01代碼輸出）； d. 以上一步的輸出（二進(jìn)制序列）作為輸入進(jìn)行解碼，恢復(fù)原英文； e. 比較輸入和輸出，統(tǒng)計(jì)出錯(cuò)的個(gè)數(shù)。前綴碼、Huffman編碼算法：前綴碼：給定一個(gè)序列的集合，若不存在一個(gè)序列是另一個(gè)序列的前綴，則該序列集合稱為前綴碼。哈夫曼（Huffman）算法可用來設(shè)計(jì)前綴編碼，用該算法構(gòu)造一棵有n個(gè)葉子（每個(gè)葉子具有一個(gè)權(quán)值）的二叉樹的過程如下：（1）根據(jù)n個(gè)權(quán)值{w1，w2，…，wn}構(gòu)成n棵二叉樹的集合F={T1，T2，…，Tn}，其中每棵二叉樹Ti中只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn)，其左右子樹均為空。（2）在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹來構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹結(jié)點(diǎn)的根結(jié)點(diǎn)的權(quán)值之和。（3）在F中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入F中。（4）重復(fù)（2）和（3），直到F中只含一棵樹時(shí)為止。稱這棵樹為最優(yōu)二叉樹（或哈夫曼樹）。如果約定將每個(gè)結(jié)點(diǎn)的左分支表示字符“0”，右分支表示字符“1”，則可以把從根結(jié)點(diǎn)到某葉子結(jié)點(diǎn)的路徑上分支字符組成的字符串作為該葉子結(jié)點(diǎn)的編碼。對(duì)于所有可能傳輸?shù)淖址蠲總€(gè)字符對(duì)應(yīng)一個(gè)葉結(jié)點(diǎn)，權(quán)值為其出現(xiàn)的頻率，那么根據(jù)哈夫曼算法構(gòu)造出二叉樹后，就得到了每個(gè)字符的二進(jìn)制編碼。根據(jù)構(gòu)造過程可知，這種編碼方案得到的字符的編碼長度的數(shù)學(xué)期望值為最小，因此這種編碼方案是一個(gè)最優(yōu)前綴碼。在構(gòu)造過程中，每次都是選取兩棵最小權(quán)值的二叉樹進(jìn)行合并。: 問提問者：網(wǎng)友 | 2017-02-27

最佳回答