Huffman File Compressor
A Java Swing app that compresses and decompresses files and directories with the greedy Huffman algorithm, visualizes the resulting code tree, and benchmarks four interchangeable priority-queue implementations used to build it.
Huffman File Compressor
Practice 4 for the Advanced Algorithms course (21747) at the Universitat de les Illes Balears. A Java Swing application, on a Model–View–Controller architecture, that compresses and decompresses files and directories with the greedy Huffman algorithm (minimum-entropy variable-length coding), visualizes the resulting code tree, and benchmarks the data structures used to build it.
The problem
Huffman coding is a textbook greedy algorithm: count how often each symbol appears, put every symbol in a priority queue keyed by frequency, and repeatedly merge the two least frequent nodes until a single tree remains — assigning shorter bit codes to more frequent symbols and so approaching the minimum entropy of the source. The application builds that tree, encodes the payload to a compact bitstream, writes a self-describing archive (header + codes + bits), and can decode it back to the exact original. A benchmark workflow measures how the choice of priority-queue implementation affects tree-construction time, and an optional dictionary pre-pass can refine the payload before Huffman runs.
About
- Two workflows, one shared view — a compression tab (pick a file or folder, compress / decompress, inspect metrics and the Huffman tree) and a benchmark tab (compare queue implementations across dataset sizes).
- Codec — a Huffman codec builds the tree and the per-symbol bit codes; a directory codec packs whole folders, and streaming helpers keep large inputs off the heap. Archives carry a header so decompression is fully driven by the stored metadata.
- Pluggable priority queues — the greedy merge step runs over interchangeable implementations: a binary heap, a sorted list, a binary-search list and a Fibonacci heap; the benchmark contrasts their real cost.
- Optional refinement — a refinement layer (identity, LZ77, LZ78) can dictionary-encode the data before Huffman, selected through a small factory.
- Tree visualization — the view renders the code tree on a canvas with an explorer, turning the abstract structure into something inspectable.
- MVC +
Notify/Reporter— dedicated orchestrators run the heavy work on background threads and report progress and ETA through the message contract.
Executing the project
Requires a JDK 17 or newer — plain Java with Swing, no external dependencies or build tool. Open the P4/ folder in IntelliJ IDEA and run practice4.Main. In the compression tab choose a file or directory to compress, check the compression ratio and browse the generated Huffman tree; in the benchmark tab compare how the different priority queues scale.