Huffman coding

Huffman coding. It is a fundamental lossless data compression algorithm invented by David A. Huffman while he was a student at the Massachusetts Institute of Technology. The method creates an optimal prefix code based on the frequency of symbols in a given dataset, commonly used within formats like GZIP, JPEG, and MP3. Its efficiency and simplicity have made it a cornerstone in the field of information theory and a critical component in many modern compression schemes.

Algorithm overview

The algorithm begins by analyzing the input to determine the frequency of each symbol, such as characters in a text file. Each symbol is placed into a priority queue, typically implemented as a binary heap, ordered by its frequency. The process then repeatedly extracts the two nodes with the lowest frequency from the priority queue and merges them into a new internal node, with a frequency equal to the sum of its children. This new node is reinserted into the priority queue, and the cycle continues until only a single node, the root of the Huffman tree, remains. Traversing this tree from the root to each leaf assigns a variable-length prefix code to each original symbol, with more frequent symbols receiving shorter codes.

Example

Consider encoding the phrase "ABRACADABRA" using the Latin alphabet. A frequency analysis yields counts for the letters: A appears five times, B and R each appear twice, while C and D appear once. Following the standard procedure, the two least frequent symbols, C and D, are combined first into a node with frequency two, comparable to B and R. Subsequent merges incorporate the higher-frequency A, ultimately constructing a binary tree. The resulting codes might assign A as '0', B as '100', R as '101', C as '1100', and D as '1101'. This demonstrates the core principle where the most common symbol, A, receives the shortest codeword. The encoded bitstream is significantly shorter than a fixed-width ASCII representation, showcasing the compression achieved.

Properties

A primary characteristic is its optimality for symbol-by-symbol coding, meaning no other prefix code can yield a shorter expected length for the given symbol probabilities, a fact proven in Huffman's original paper in the Proceedings of the IRE. The algorithm produces a prefix code, ensuring no codeword is a prefix of another, which allows for instantaneous and unambiguous decoding without requiring special delimiters. While optimal for static probabilities, the basic algorithm requires two passes over the data: one for frequency analysis and a second for encoding, and the code table must be transmitted alongside the compressed data. The construction time is O(n log n) when using a binary heap for the priority queue.

Variations and extensions

Several adaptations address limitations of the canonical method. Adaptive Huffman coding, developed by researchers like Robert G. Gallager and later refined in the UNIX utility Compact, updates the Huffman tree dynamically as data is processed, eliminating the need for a preliminary pass. Canonical Huffman coding standardizes the code assignment, allowing the transmission of only code lengths rather than the full tree, a technique used in DEFLATE as implemented in GZIP and PNG. For contexts where symbol probabilities are not independent, arithmetic coding often provides better compression but with increased computational complexity. Other hybrid approaches combine it with algorithms like Lempel–Ziv–Welch in the TIFF file format.

Applications

The algorithm is ubiquitous in core compression technologies. It forms a key stage in the DEFLATE algorithm, which is the engine behind GZIP, ZIP, and the PNG image format. Within multimedia, it is used in JPEG for compressing the coefficients after the discrete cosine transform and in MP3 for audio data. Early fax machine standards, such as those from the International Telecommunication Union, employed modified versions for bilevel image compression. Its integration into foundational UNIX utilities and the Berkeley Software Distribution helped propagate its use across operating systems and networking protocols for efficient data transmission.

Category:Lossless compression algorithms Category:1952 in computing