實現最優二叉樹的構造;在此基礎上完成哈夫曼編碼器與譯碼器。 假設報文中只會出現如下表所示的字符:
字符 A B C D E F G H I J K L M N
頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 57
字符 O P Q R S T U V W X Y Z , .
頻度 63 15 1 48 51 80 23 8 18 1 16 1 6 2
要求完成的系統應具備如下的功能:
1.初始化。從終端(文件)讀入字符集的數據信息,。建立哈夫曼樹。
2.編碼:利用已建好的哈夫曼樹對明文文件進行編碼,并存入目標文件(哈夫曼碼文件)。
3.譯碼:利用已建好的哈夫曼樹對目標文件(哈夫曼碼文件)進行編碼,并存入指定的明文文件。
4.輸出哈夫曼編碼文件:輸出每一個字符的哈夫曼編碼。
哈夫曼樹很易求出給定字符集及其概率(或頻度)分布的最優前綴碼。哈夫曼編碼正是一種應用廣泛且非常有效的數據壓縮技術。該技術一般可將數據文件壓縮掉20%至90%,其壓縮效率取決于被壓縮文件的特征。
利用哈夫曼編碼進行通信可以大大提高信道利用率,縮短信息傳輸時,降低傳輸成本。但是,這要求在發送端通過一個編碼系統對待傳送電文須預先編碼,在接收須將傳送來的數據進行譯碼。請自行設計實現一個具有初始化、編碼、譯碼、輸入/輸出等功能的哈夫曼碼的編碼/譯碼系統。并實現以下報文的編碼和譯碼:“this program is my favorite”。