Analysis and Implementation of Minimum-Redundancy Huffman Codes

Abstract

This student research project analyzes David A. Huffman's 1952 paper, "A Method for the Construction of Minimum-Redundancy Codes." The document explains the theory of minimum-redundancy prefix-free codes, formulates the greedy merging property behind Huffman coding, and designs binary and generalized D-ary Huffman algorithms. It also presents hufflab, a Python research tool for constructing Huffman codebooks, generating canonical codes, analyzing average code length, encoding files, and decoding compressed bitstreams. Experimental validation includes binary compression of a sample text file, generalized D-ary coding using Huffman's Table III example, and a lossless round-trip decoding test. The source code is available at https://github.com/sethigris/hufflab.