Huffman Codes算法设计与分析课程设计实验报告.doc

1 实验题目哈夫曼编码一、问题描述: Problem E Dan McAmbi isa member ofa crack counter-espionage team and has recently obtained the partial contents ofa file containing information vital to his nation! ˉs interests. The file had pressed using Huffman encoding. Unfortunately, the part of the file that Dan has shows only the Huffman codes themselves, not pressed information. Since Huffman codes are based on the frequencies of the characters in the original message, Dan! ˉs boss thinks that some information might be obtained if Dan can reverse the Huffman encoding process and obtain the character frequencies from the Huffman codes. Dan! ˉs gut reaction to this is that any given set of codes could be obtained from a wide variety of frequency distributions, but his boss is not impressed with this reasoned analysis. So Dan e to you to get more definitive proof to take back to his boss. Huffman encoding is an optimal pression method if you know in advance the relative frequencies of letters in the text to pressed. The method works by first constructing a Huffman tree as follows. Start with a forest of trees, each tree a single node containing a character from the text and its frequency (the character value is used only in the leaves of the resulting tree). Each step of the construction algorithm takes the two trees with the lowest frequency values (choosing arbitrarily if there are ties), and replaces them with a new tree formed by joining the two trees as the left and right subtrees ofa new root node. The frequency value of the new root is the sum of the frequencies of the two subtrees. This procedure repeats until only one tree is left. An example of this is shown below, assuming we have a file with only 5 characters ¨C A, B, C,D and E¨C with frequencies 10%, 14%, 31%, 25% and 20%, respectively. After you have constructed a Huffman tree, assign the Huffman codes to the characters as follows. Label each left branch of the tree with a0 and each right branch with a 1. Reading down from the r