Huffman Compression Algorithm Optimization

This project was a desktop implementation used to examine Huffman compression in terms of both execution cost and the resulting compressed size.

From Frequencies to Prefix Codes

Huffman coding starts from symbol frequencies and repeatedly combines low-frequency nodes into a binary tree. Paths from the root to leaves define variable-length bit codes.

Frequently occurring symbols can receive shorter codes while less common symbols receive longer ones. Because the code set is prefix-free, the bit stream can be decoded unambiguously without inserting delimiters between symbols.

Implementation Cost

The mathematical algorithm is only part of application performance. Building the frequency table, selecting low-weight nodes, constructing the tree, packing variable-length bits and performing file I/O all contribute to total execution time.

The surviving project record reports that the compressed output was approximately 58% of the original test-file size.

That figure is not a universal Huffman compression ratio. Compression depends on the symbol distribution of the input; already-compressed or high-entropy data may provide little benefit.

Algorithmic Context

Huffman coding is a lossless frequency-based prefix-code method. Its wider data-structure and algorithmic context is covered in my Data Structures and Algorithm Analysis notes.

A repeatable benchmark of the same code should report compression ratio, encode/decode time, memory use and the exact test corpus as separate metrics.