汽配人首頁(yè) > 問(wèn)答首頁(yè)

霍夫曼編碼器

要求: a. 隨機(jī)輸入一段英文(含標(biāo)點(diǎn)、空格以及大小寫(xiě)的區(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è)序列的前綴，則該序列集合稱(chēng)為前綴碼。哈夫曼（Huffman）算法可用來(lái)設(shè)計(jì)前綴編碼，用該算法構(gòu)造一棵有n個(gè)葉子（每個(gè)葉子具有一個(gè)權(quán)值）的二叉樹(shù)的過(guò)程如下：（1）根據(jù)n個(gè)權(quán)值{w1，w2，…，wn}構(gòu)成n棵二叉樹(shù)的集合F={T1，T2，…，Tn}，其中每棵二叉樹(shù)Ti中只有一個(gè)帶權(quán)為wi的根結(jié)點(diǎn)，其左右子樹(shù)均為空。（2）在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為左右子樹(shù)來(lái)構(gòu)造一棵新的二叉樹(shù)，且置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)結(jié)點(diǎn)的根結(jié)點(diǎn)的權(quán)值之和。（3）在F中刪除這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入F中。（4）重復(fù)（2）和（3），直到F中只含一棵樹(shù)時(shí)為止。稱(chēng)這棵樹(shù)為最優(yōu)二叉樹(shù)（或哈夫曼樹(shù)）。如果約定將每個(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)造出二叉樹(shù)后，就得到了每個(gè)字符的二進(jìn)制編碼。根據(jù)構(gòu)造過(guò)程可知，這種編碼方案得到的字符的編碼長(zhǎng)度的數(shù)學(xué)期望值為最小，因此這種編碼方案是一個(gè)最優(yōu)前綴碼。在構(gòu)造過(guò)程中，每次都是選取兩棵最小權(quán)值的二叉樹(shù)進(jìn)行合并。: 問(wèn) 提問(wèn)者：網(wǎng)友 | 2017-02-27

最佳回答