Given a frequency data, produces huffman codes for the unique messages.
- Node.java: DS for storing huffman tree
- PairNode.java: DS used in PairingHeap.java
- BinaryHeap.java: To implement binary heap
- PairingHeap.java: To implement pairing heap
- D_aryHeap.java: To implement D-ary heap. For eg. 4-way heap.
- Gen_huffman_code.java: To comapre the performance of above mentioned priority queues for huffman coding.
Usage:
~:src$ java Gen_huffman_code ../sample_input_large.txt
Reading input file ... Building Freq Table ... Done.
Building Huffman Tree using Binary Heap ...
Run:1.. 2.. 3.. 4.. 5.. 6.. 7.. 8.. 9.. 10.. Done
Average Time: 1663.0
Building Huffman Tree using Pairing Heap ...
Run:1.. 2.. 3.. 4.. 5.. 6.. 7.. 8.. 9.. 10.. Done
Average Time: 3417.0
Building Huffman Tree using 4-ary Heap ...
Run:1.. 2.. 3.. 4.. 5.. 6.. 7.. 8.. 9.. 10.. Done
Average Time: 1291.0
It is found that 4-ary heap is the fastest. So later encoding is done using 4-ary heap.
- encoder.java: Produces code_table.txt containing codes for all the unique messages; and encoded.bin, which is the binary file for the codes corresponding to the input file.
Usage:
~:src$ java encoder ../sample_input_large.txt
Reading input file ...
Building Freq Table ...
Building huffman tree... Done.
Generating code_table.txt .. Done.
Generating encoded.bin .. Done.
As a proof of concept, we will reconstruct our input using code_table.txt and encoded.bin
- decoder.java: Takes in input encoded.bin and code_table.txt and produces decoded.txt which is exactly the same as sample_input_large.txt as used in encoder.
Usage:
~:src$ java decoder encoded.bin code_table.txt
Building huffman tree from code_table.txt ..
Reading code_table.txt .. Done.
Reading encoded.bin .. Done.
Generating decoded.txt .. Done.
Do diff decoded.txt ../sample_input_large.txt to check correctness.
Clone repository and make:
~:$ git clone https://github.com/vishalkg/huffman_coding.git
~:$ cd huffman_coding/src
~:src$ make