In computer science, Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol (such as a character in a file) where the variable-length code table has been derived in a particular way based on the estimated probability of occurrence for each possible value of the source symbol. It was developed by David A. Huffman as a Ph.D. student at MIT in 1952, and published in A Method for the Construction of Minimum-Redundancy Codes. Huffman was Professor Emeritus of Computer Science at the Baskin School of Engineering at the University of California, Santa Cruz until his death from cancer in 1999.

Huffman coding uses a specific method for choosing the representation for each symbol, resulting in a prefix-free code (that is, the bit string representing some particular symbol is never a prefix of the bit string representing any other symbol) that expresses the most common characters using shorter strings of bits than are used for less common source symbols. Huffman was able to design the most efficient compression method of this type: no other mapping of individual source symbols to unique strings of bits will produce a smaller average output size when the actual symbol frequencies agree with those used to create the code. (Huffman coding is such a widespread method for creating prefix-free codes that the term "Huffman code" is widely used as a synonym for "prefix-free code" even when such a code was not produced by Huffman's algorithm.)

For a set of symbols with a uniform probability distribution and a number of members which is a power of two, Huffman coding is equivalent to simple binary block encoding.

Assertions of the optimality of Huffman coding should be phrased carefully, because its optimality can sometimes accidentally be over-stated. For example, arithmetic coding ordinarily has better compression capability, because it does not require the use of an integer number of bits for encoding each source symbol. LZW coding can also often be more efficient, particularly when the input symbols are not independently-distributed, because it does not depend on encoding each input symbol one at a time (instead, it batches up a variable number of input symbols into each encoded syntax element). The efficiency of Huffman coding also depends heavily on having a good estimate of the true probability of the value of each input symbol.

History

---

In 1951, David Huffman and his MIT information theory classmates were given the choice of a term paper or a final exam. The professor, Robert M. Fano, assigned a term paper on the problem of finding the most efficient binary code. Huffman, unable to prove any codes were the most efficient, was about to give up and start studying for the final when he hit upon the idea of using a frequency-sorted binary tree, and quickly proved this method the most efficient.

In doing so, the student outdid his professor, who had worked with information theory inventor Claude Shannon to develop a similar code. Huffman avoided the major flaw of Shannon-Fano coding by building the tree from the bottom up instead of from the top down.

Problem definition

---

Informal description

Given. A set of symbols and their costs.
Find. A prefix free binary character code (a sets of codewords) with minimum weighted path length.
Note-1. A code wherein each character is represented by a unique binary string (codeword) is called a binary character code.
Note-2. A prefix free code is a code having the property that no codeword is a prefix of any other codeword.
Note-3. In the standard Huffman coding problem, it is assumed that each symbol in the set from which the code words are constructed has an equal cost to transmit: a code word whose length is N digits will always have a cost of N, no matter how many of those digits are 0s, how many are 1s, etc. When working under this assumption, minimizing the total cost of the message and minimizing the total number of digits are the same thing.

Formalized description

Input.
Alphabet $A\; =\; \backslash left\backslash \{a\_\{1\},a\_\{2\},\backslash cdots,a\_\{n\}\backslash right\backslash \}$, which is the symbol alphabet of size $n$.
Set $C\; =\; \backslash left\backslash \{c\_\{1\},c\_\{2\},\backslash cdots,c\_\{n\}\backslash right\backslash \}$, which is the set of the symbol costs, i.e. $c\_\{i\}\; =\; \backslash mathrm\{cost\}\backslash left(a\_\{i\}\backslash right),\; 1\backslash leq\; i\; \backslash leq\; n$.

Output.
Code $H\backslash left(A,C\backslash right)\; =\; \backslash left\backslash \{h\_\{1\},h\_\{2\},\backslash cdots,h\_\{n\}\backslash right\backslash \}$, which is the set of (binary) codewords, where $h\_\{i\}$ is the codeword for $a\_\{i\},\; 1\; \backslash leq\; i\; \backslash leq\; n$.

Goal.
Let $S\backslash left(H\backslash right)\; =\; \backslash sum\_\{i=1\}^\{n\}\{c\_\{i\}\backslash times\backslash mathrm\{length\}\backslash left(h\_\{i\}\backslash right)\}$ be the weighted path length of code $H$. Condition: $S\backslash left(H\backslash right)\; \backslash leq\; S\backslash left(T\backslash right)$ for any code $T\backslash left(A,C\backslash right)$.

Samples

Sample-1

---

Input	Alphabet	a	b	c	d	e	f	g	h	i
	Costs	10	15	5	15	20	5	15	30	5
Output	Codewords	000	010	0010	011	111	00110	110	10	00111
	Weighted path length	10 * 3	15 * 3	5 * 4	15 * 3	20 * 3	5 * 5	15 * 3	30 * 2	5 * 5	= 355

Basic technique

---

The technique works by creating a binary tree of nodes. These can be stored in a regular array, the size of which depends on the number of symbols(N). A node can be either a leaf node or an internal node. Initially, all nodes are leaf nodes, which contain the symbol itself, the weight (frequency of appearance) of the symbol and optionally, a link to a parent node which makes it easy to read the code (in reverse) starting from a leaf node. Internal nodes contain symbol weight, links to two child nodes and the optional link to a parent node. As a common convention, bit '0' represents following the left child and bit '1' represents following the right child. A finished tree has N leaf nodes and N−1 internal nodes.

A fast way to create a Huffman tree is to use the heap data structure, which keeps the nodes in partially sorted order according to a predetermined criterion. In this case, the node with the lowest weight is always kept at the root of the heap for easy access.

Creating the tree:

1. Start with as many leaves as there are symbols.
2. Push all leaf nodes into the heap.
3. While there is more than one node in the heap:
   1. Remove two nodes with the lowest weight from the heap.
   2. If the heap was storing copies of node data rather than pointers to nodes in final storage for the tree, move these nodes to final storage.
   3. Create a new internal node, with the two just-removed nodes as children (either node can be either child) and the sum of their weights as the new weight.
   4. Update the parent links in the two just-removed nodes to point to the just-created parent node.
   5. Push the new node into the heap.
4. The remaining node is the root node; the tree has now been generated.

It is generally beneficial to minimize the variance of codeword length. For example, a communication buffer receiving Huffman-encoded data may need to be larger to deal with especially long symbols if the tree is especially unbalanced. To reduce variance every newly generated node must be favored among same weight nodes and placed as high as possible. This modification will retain the mathematical optimality of the Huffman coding while minimizing the length of the longest character code.

Main properties

---

The frequencies used can be generic ones for the application domain that are based on average experience, or they can be the actual frequencies found in the text being compressed. (This variation requires that a frequency table or other hint as to the encoding must be stored with the compressed text; implementations employ various tricks to store tables efficiently.)

Huffman coding is optimal when the probability of each input symbol is a negative power of two. Prefix-free codes tend to have slight inefficiency on small alphabets, where probabilities often fall between these optimal points. "Blocking", or expanding the alphabet size by coalescing multiple symbols into "words" of fixed or variable length before Huffman coding, can help a bit, especially when adjacent symbols are correlated (as in the case of natural language text). Except in some cases with very short codewords, Huffman encoding is robust with respect to inaccuracies in estimated codeword frequencies: the effect of inappropriately long codewords is almost exactly cancelled out by the effect of inappropriately short codewords. The worst case for Huffman coding can happen when the probability of a symbol exceeds 2^-1 = 0.5, making the upper limit of inefficiency unbounded. These situations often respond well to a form of blocking called run-length encoding.

Extreme cases of Huffman codes are connected with Fibonacci and Lucas numbers and Wythoff array.

Arithmetic coding produces slight gains over Huffman coding, but in practice these gains have seldom been large enough to offset arithmetic coding's higher computational complexity and patent royalties. (As of November 2001, IBM owns patents on the core concepts of arithmetic coding in several jurisdictions.)

Variations

---

Adaptive Huffman coding

A variation called adaptive Huffman coding calculates the frequencies dynamically based on recent actual frequencies in the source string. This is somewhat related to the LZ family of algorithms.

Length-limited Huffman coding

Length-limited Huffman coding is a variant where the goal is still to achieve a minimum weighted path length, but there is an additional restriction that the length of each codeword must be less than a given constant.

Huffman template algorithm

Most often, the weights used in implementations of Huffman coding represent numeric probabilities, but the algorithm given above does not require this; it requires only a way to order weights and to add them. The Huffman template algorithm enables one to use non-numerical weights (costs, frequencies).

n-ary Huffman coding

The n-ary Huffman algorithm uses the {0, 1, ..., n − 1} alphabet to encode message and build an n-ary tree.

Huffman coding with unequal letter costs

In the standard Huffman coding problem, it is assumed that each symbol in the set that the code words are constructed from has an equal cost to transmit: a code word whose length is N digits will always have a cost of N, no matter how many of those digits are 0s, how many are 1s, etc. When working under this assumption, minimizing the total cost of the message and minimizing the total number of digits are the same thing.

Huffman coding with unequal letter costs is the generalization in which this assumption is no longer assumed true: the letters of the encoding alphabet may have non-uniform lengths, due to characteristics of the transmission medium. An example is the encoding alphabet of Morse code, where a 'dash' takes longer to send than a 'dot', and therefore the cost of a dash in transmission time is higher. The goal is still to minimize the weighted average codeword length, but it is no longer sufficient just to minimize the number of symbols used by the message.

Applications

---

Arithmetic coding can be viewed as a generalization of Huffman coding. Although arithmetic coding offers better compression performance than Huffman coding, Huffman coding is still in wide use because of its simplicity, high speed and lack of encumbrance by patents.

Huffman coding today is often used as a "back-end" to some other compression method. DEFLATE (PKZIP's algorithm) and multimedia codecs such as JPEG and MP3 have a front-end model and quantization followed by Huffman coding.

See also

---

• Modified Huffman coding - used in fax machines
• Shannon-Fano coding
• Data compression

References

---

• Huffman's original article: D.A. Huffman, "A method for the construction of minimum-redundancy codes" (PDF), Proceedings of the I.R.E., sept 1952, pp 1098-1102
• Background story: Profile: David A. Huffman, Scientific American, Sept. 1991, pp. 54-58
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 16.3, pp.385–392.

External links

---

• Program for explaining the Huffman Coding procedure.
• Huffman Code Applet
• n-ary Huffman Template Algorithm
• Huffman codes' connection with Fibonacci and Lucas numbers
• Fibonacci connection between Huffman codes and Wythoff array
• Sloane A098950 Minimizing k-ordered sequences of maximum height Huffman tree
• Computing Huffman codes on a Turing Machine
• Mordecai J. Golin, Claire Kenyon, Neal E. Young "Huffman coding with unequal letter costs" (PDF), STOC 2002: 785-791
• Huffman Coding, implemented in python
• List of Huffman compression resources, papers, libraries
• Huffman Coding: A CS2 Assignment a good introduction to Huffman coding
• A quick tutorial on generating a Huffman tree
• Pointers to Huffman coding visualizations

Lossless compression algorithms | Coding theory

Huffmanovo kódování | Shannon-Fano-Kodierung | Codificación Huffman | Codage de Huffman | 허프만 코딩 | Codifica di Huffman | קוד הופמן | Huffmancodering | ハフマン符号 | Kodowanie Huffmana | Codificação de Huffman | Huffmanin koodaus | Алгоритм Хаффмана | Huffmankodning | รหัสฮัฟแมน และ รหัสแชนนอน-ฟาโน | 哈夫曼树