汽配人首頁 > 問答首頁

霍夫曼編碼器

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

最佳回答