编程辅导 C C++ Java Python MIPS Processing 网络家教 在线辅导

Huffman Encoding

Write a program that reads in a file (argv[1]) and, based on the characters it contains, computes

the Huffman tree.

The output, for an example input file, should look something like:

010 : 00101 ( 5 * 125)

‘ ’ : 110 ( 3 * 792)

‘"’ : 111001010 ( 9 * 12)

‘’’ : 00100000 ( 8 * 15)

‘(’ : 01100000100 ( 11 * 2)

‘)’ : 01100001101 ( 11 * 2)

‘,’ : 1001001 ( 7 * 39)

‘-’ : 0010010 ( 7 * 31)

‘.’ : 1001100 ( 7 * 40)

‘/’ : 00100110000 ( 11 * 1)

‘0’ : 11100110010 ( 11 * 3)

‘1’ : 00100010 ( 8 * 15)

‘3’ : 01100000101 ( 11 * 2)

‘4’ : 01100001001 ( 11 * 2)

‘5’ : 11100110011 ( 11 * 3)

‘6’ : 01100001000 ( 11 * 2)

‘7’ : 01100001100 ( 11 * 2)

‘8’ : 001001101 ( 9 * 8)

‘9’ : 10010000 ( 8 * 18)

‘:’ : 01100001011 ( 11 * 2)

‘A’ : 00100111 ( 8 * 16)

‘B’ : 111001101 ( 9 * 13)

‘C’ : 10011011 ( 8 * 22)

‘D’ : 111001110 ( 9 * 13)

‘E’ : 10011010 ( 8 * 19)

‘F’ : 111001000 ( 9 * 11)

‘G’ : 0110000000 ( 10 * 4)

‘H’ : 1110011111 ( 10 * 7)

‘I’ : 1110010011 ( 10 * 6)

‘J’ : 11100111101 ( 11 * 3)

‘K’ : 1110010111 ( 10 * 6)

‘L’ : 00100011 ( 8 * 15)

‘M’ : 11100111100 ( 11 * 3)

‘N’ : 01100001010 ( 11 * 2)

‘O’ : 01100000111 ( 11 * 2)

‘P’ : 1110011000 ( 10 * 6)

‘R’ : 0110000111 ( 10 * 5)

1‘S’ : 10010001 ( 8 * 19)

‘T’ : 0010011001 ( 10 * 4)

‘U’ : 1110010010 ( 10 * 5)

‘W’ : 0110000001 ( 10 * 4)

‘a’ : 1010 ( 4 * 339)

‘b’ : 1111110 ( 7 * 60)

‘c’ : 100101 ( 6 * 77)

‘d’ : 01101 ( 5 * 143)

‘e’ : 000 ( 3 * 473)

‘f’ : 100111 ( 6 * 84)

‘g’ : 111000 ( 6 * 94)

‘h’ : 11110 ( 5 * 223)

‘i’ : 0100 ( 4 * 266)

‘j’ : 01100000110 ( 11 * 2)

‘k’ : 00100001 ( 8 * 15)

‘l’ : 10110 ( 5 * 176)

‘m’ : 101111 ( 6 * 92)

‘n’ : 0111 ( 4 * 288)

‘o’ : 0101 ( 4 * 269)

‘p’ : 101110 ( 6 * 89)

‘q’ : 00100110001 ( 11 * 2)

‘r’ : 11101 ( 5 * 214)

‘s’ : 0011 ( 4 * 260)

‘t’ : 1000 ( 4 * 305)

‘u’ : 111110 ( 6 * 108)

‘v’ : 0110001 ( 7 * 37)

‘w’ : 1111111 ( 7 * 60)

‘x’ : 1110010110 ( 10 * 6)

‘y’ : 011001 ( 6 * 72)

2916 bytes

Each character is shown, along with its Huffman bit-pattern, the length of the bit-pattern and

the frequency of occurrence. At the bottom, the total number of bytes required to encode the

characters is displayed.

2