• Huffman Codes

You will turn in one file: HuffmanCodes.java, which can encode and decode files using Huffman codes. The program has the following command-line interface:

$ javaHuffmanCodes --help
Usage: java HuffmanCodes OPTIONS IN OUT
Encodes and decodes files using Huffman's technique

-e, --encode encodes IN to OUT
-d, --decode decodes IN to OUT
--show-frequency show the frequencies of each byte
--show-codes show the codes for each byte
--show-binary show the encoded sequence in binary
-h, --help display this help and exit

• When the encode option is used, the program will read in the file specified by the IN operand and create the file specified by the OUT operand. Depending on the nature of the input file, the output file could be smaller than the original input.

• When the decode option is used, the program will read in the file specified by the IN operand and interpret it as the output from the encode operation. If the given file represents a valid encoding, the original encoding for the file will be restored in a new file, specified by the OUT operand.

• Frequency Counting

The show-frequency option assists debugging. When it is set, the frequency table computed from the input file is output during the encoding process. For example, if the input file is the characters "mississippi" (without a newline), then the output would be:
$ echo -n "mississippi" > mi.txt
$ javaHuffmanCodes --encode mi.txt mi.encoded --show-frequency

FREQUENCY TABLE
'm': 1
'p': 2
'i': 4
's': 4

input: 11 bytes [88 bits]

output: 12 bytes [header: 71 bits; encoding: 21 bits]
output/input size: 109.0909%

The first column is each byte of the input file displayed in the format of a Java character literal (e.g., the newline character would be represented as '\n'). The second column is the count (in decimal) for the number of times that byte's value is present in the input file.
The table is ordered from least frequent to most frequent, with ties broken by each byte's value.

• Generating Prefix-Free Codes

Like the show-frequency option, the show-codes option also assists debugging. It displays the variable-length Huffman codes for each value, using a sequence of "0" and "1" characters.
$ javaHuffmanCodes --encode mi.txt mi.encoded --show-codes
CODES
"0" -> 's'
"11" -> 'i'
"100" -> 'm'
"101" -> 'p'

input: 11 bytes [88 bits]

output: 12 bytes [header: 71 bits; encoding: 21 bits]
output/input size: 109.0909%

• Encoding the Sequence

Although you should also be using the xxd command to help you view your file contents in binary, it is also helpful to have an explicit show-binary option to describe the sequence:
$ javaHuffmanCodes --encode mi.txt mi.encoded --show-binary

• ENCODED SEQUENCE

100110011001110110111
input: 11 bytes [88 bits]
output: 12 bytes [header: 71 bits; encoding: 21 bits]
output/input size: 109.0909%

• Decoding

The program will also decode sequences:
$ xxd -b mi.encoded
0000000: 00000000 00000000 00000000 00001011 01011100 11001011 ....\.
0000006: 01101101 11000010 11010011 00110011 00111011 01110000 m..3;p
$ javaHuffmanCodes --decode mi.encodedmi.restored --show-codes

• CODES

"0" -> 's'
"11" -> 'i'
"100" -> 'm'
"101" -> 'p'
original size: 11
$ catmi.restored
mississippi