汽配人首頁 > 問答首頁

霍夫曼編碼器

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

最佳回答