Description: David A. Huffman published his paper A Method for the Construction of Minimum-Redundancy Codes , and hence printed his name in the history of computer science. As a professor who gives the final exam problem on Huffman codes, I am encountering a big problem: the Huffman codes are NOT unique. For example, given a string aaaxuaxz , we can observe that the frequencies of the characters a , x , u and z are 4, 2, 1 and 1, respectively. We may either encode the symbols as { a =0, x =10, u =110, z =111}, or in another way as { a =1, x =01, u =001, z =000}, both compress the string into 14 bits. Another set of code can be given as { a =0, x =11, u =100, z =101}, but { a =0, x =01, u =011, z =001} is NOT correct since aaaxuaxz and aazuaxax can both be decoded the code 00001011001001. The students are submitting all kinds of codes, and I need a computer program to help me determine which ones are correct and which ones are not.
To Search:
File list (Check if you may need any files):
code.cpp
Download