| Char | Freq | Code |
|---|---|---|
| space | 7 | 111 |
| a | 4 | 010 |
| e | 4 | 000 |
| f | 3 | 1101 |
| h | 2 | 1010 |
| i | 2 | 1000 |
| m | 2 | 0111 |
| n | 2 | 0010 |
| s | 2 | 1011 |
| t | 2 | 0110 |
| l | 1 | 11001 |
| o | 1 | 00110 |
| p | 1 | 10011 |
| r | 1 | 11000 |
| u | 1 | 00111 |
| x | 1 | 10010 |
Incomputer science andinformation theory, aHuffman code is a particular type of optimalprefix code that is commonly used forlossless data compression. The process of finding or using such a code isHuffman coding, an algorithm developed byDavid A. Huffman while he was aSc.D. student atMIT, and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes".[1]
The output from Huffman's algorithm can be viewed as avariable-length code table for encoding a source symbol (such as a character in a file). The algorithm derives this table from the estimated probability or frequency of occurrence (weight) for each possible value of the source symbol. As in otherentropy encoding methods, more common symbols are generally represented using fewer bits than less common symbols. Huffman's method can be efficiently implemented, finding a code in timelinear to the number of input weights if these weights are sorted.[2] However, although optimal among methods encoding symbols separately, Huffman codingis not always optimal among all compression methods – it is replaced witharithmetic coding[3] orasymmetric numeral systems[4] if a better compression ratio is required.
In 1951,David A. Huffman and hisMITinformation theory classmates were given the choice of a term paper or a finalexam. The professor,Robert M. Fano, assigned aterm 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-sortedbinary tree and quickly proved this method the most efficient.[5]
In doing so, Huffman outdid Fano, who had worked withClaude Shannon to develop a similar code. Building the tree from the bottom up guaranteed optimality, unlike the top-down approach ofShannon–Fano coding.
Huffman coding uses a specific method for choosing the representation for each symbol, resulting in aprefix code (sometimes called "prefix-free codes", that is, the bit string representing some particular symbol is never a prefix of the bit string representing any other symbol). Huffman coding is such a widespread method for creating prefix codes that the term "Huffman code" is widely used as a synonym for "prefix code" even when such a code is not produced by Huffman's algorithm.
 | This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Huffman coding" – news ·newspapers ·books ·scholar ·JSTOR(December 2021) (Learn how and when to remove this message) |
Input.
Alphabet, which is the symbol alphabet of size.
Tuple, which is the tuple of the (positive) symbol weights (usually proportional to probabilities), i.e..
Output.
Code, which is the tuple of (binary) codewords, where is the codeword for.
Goal.
Let be the weighted path length of code. Condition: for any code.
We give an example of the result of Huffman coding for a code with five characters and given weights. We will not verify that it minimizesL over all codes, but we will computeL and compare it to theShannon entropyH of the given set of weights; the result is nearly optimal.
| Input (A,W) | Symbol (ai) | a | b | c | d | e | Sum |
|---|---|---|---|---|---|---|---|
| Weights (wi) | 0.10 | 0.15 | 0.30 | 0.16 | 0.29 | = 1 | |
| OutputC | Codewords (ci) | 010 | 011 | 11 | 00 | 10 | |
| Codeword length (in bits) (ℓi) | 3 | 3 | 2 | 2 | 2 | ||
| Contribution to weighted path length (ℓiwi ) | 0.30 | 0.45 | 0.60 | 0.32 | 0.58 | L(C) = 2.25 | |
| Optimality | Probability budget (2−ℓi) | 1/8 | 1/8 | 1/4 | 1/4 | 1/4 | = 1.00 |
| Information content (in bits) (−log2wi) ≈ | 3.32 | 2.74 | 1.74 | 2.64 | 1.79 | ||
| Contribution to entropy (−wi log2wi) | 0.332 | 0.411 | 0.521 | 0.423 | 0.518 | H(A) = 2.205 |
For any code that isbiunique, meaning that the code isuniquely decodeable, the sum of the probability budgets across all symbols is always less than or equal to one. In this example, the sum is strictly equal to one; as a result, the code is termed acomplete code. If this is not the case, one can always derive an equivalent code by adding extra symbols (with associated null probabilities), to make the code complete while keeping itbiunique.
As defined byShannon (1948), the information contenth (in bits) of each symbolai with non-null probability is
TheentropyH (in bits) is the weighted sum, across all symbolsai with non-zero probabilitywi, of the information content of each symbol:
(Note: A symbol with zero probability has zero contribution to the entropy, since. So for simplicity, symbols with zero probability can be left out of the formula above.)
As a consequence ofShannon's source coding theorem, the entropy is a measure of the smallest codeword length that is theoretically possible for the given alphabet with associated weights. In this example, the weighted average codeword length is 2.25 bits per symbol, only slightly larger than the calculated entropy of 2.205 bits per symbol. So not only is this code optimal in the sense that no other feasible code performs better, but it is very close to the theoretical limit established by Shannon.
In general, a Huffman code need not be unique. Thus the set of Huffman codes for a given probability distribution is a non-empty subset of the codes minimizing for that probability distribution. (However, for each minimizing codeword length assignment, there exists at least one Huffman code with those lengths.)
| Symbol | Code |
|---|---|
| a1 | 0 |
| a2 | 10 |
| a3 | 110 |
| a4 | 111 |
The technique works by creating abinary tree of nodes. These can be stored in a regulararray, the size of which depends on the number of symbols,. A node can be either aleaf node or aninternal node. Initially, all nodes are leaf nodes, which contain thesymbol itself, theweight (frequency of appearance) of the symbol and optionally, a link to aparent node which makes it easy to read the code (in reverse) starting from a leaf node. Internal nodes contain aweight, links totwo child nodes and an optional link to aparent node. As a common convention, bit '0' represents following the left child and bit '1' represents following the right child. A finished tree has up to leaf nodes and internal nodes. A Huffman tree that omits unused symbols produces the most optimal code lengths.
The process begins with the leaf nodes containing the probabilities of the symbol they represent. Then, the process takes the two nodes with smallest probability, and creates a new internal node having these two nodes as children. The weight of the new node is set to the sum of the weight of the children. We then apply the process again, on the new internal node and on the remaining nodes (i.e., we exclude the two leaf nodes), we repeat this process until only one node remains, which is the root of the Huffman tree.
The simplest construction algorithm uses apriority queue where the node with lowest probability is given highest priority:
Since efficient priority queue data structures require O(logn) time per insertion, and a tree withn leaves has 2n−1 nodes, this algorithm operates in O(n logn) time, wheren is the number of symbols.
If the symbols are sorted by probability, there is alinear-time (O(n)) method to create a Huffman tree using twoqueues, the first one containing the initial weights (along with pointers to the associated leaves), and combined weights (along with pointers to the trees) being put in the back of the second queue. This assures that the lowest weight is always kept at the front of one of the two queues:
Once the Huffman tree has been generated, it is traversed to generate a dictionary which maps the symbols to binary codes as follows:
The final encoding of any symbol is then read by a concatenation of the labels on the edges along the path from the root node to the symbol.
In many cases, time complexity is not very important in the choice of algorithm here, sincen here is the number of symbols in the alphabet, which is typically a very small number (compared to the length of the message to be encoded); whereas complexity analysis concerns the behavior whenn grows to be very large.
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 minimize variance, simply break ties between queues by choosing the item in the first queue. This modification will retain the mathematical optimality of the Huffman coding while both minimizing variance and minimizing the length of the longest character code.
Generally speaking, the process of decompression is simply a matter of translating the stream of prefix codes to individual byte values, usually by traversing the Huffman tree node by node as each bit is read from the input stream (reaching a leaf node necessarily terminates the search for that particular byte value). Before this can take place, however, the Huffman tree must be somehow reconstructed. In the simplest case, where character frequencies are fairly predictable, the tree can be preconstructed (and even statistically adjusted on each compression cycle) and thus reused every time, at the expense of at least some measure of compression efficiency. Otherwise, the information to reconstruct the tree must be sent a priori. A naive approach might be to prepend the frequency count of each character to the compression stream. Unfortunately, the overhead in such a case could amount to several kilobytes, so this method has little practical use. If the data is compressed usingcanonical encoding, the compression model can be precisely reconstructed with just bits of information (whereB is the number of bits per symbol). Another method is to simply prepend the Huffman tree, bit by bit, to the output stream. For example, assuming that the value of 0 represents a parent node and 1 a leaf node, whenever the latter is encountered the tree building routine simply reads the next 8 bits to determine the character value of that particular leaf. The process continues recursively until the last leaf node is reached; at that point, the Huffman tree will thus be faithfully reconstructed. The overhead using such a method ranges from roughly 2 to 320 bytes (assuming an 8-bit alphabet). Many other techniques are possible as well. In any case, since the compressed data can include unused "trailing bits" the decompressor must be able to determine when to stop producing output. This can be accomplished by either transmitting the length of the decompressed data along with the compression model or by defining a special code symbol to signify the end of input (the latter method can adversely affect code length optimality, however).
The probabilities 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 requires that afrequency table must be stored with the compressed text. See the Decompression section above for more information about the various techniques employed for this purpose.
Huffman's original algorithm is optimal for a symbol-by-symbol coding with a known input probability distribution, i.e., separately encoding unrelated symbols in such a data stream. However, it is not optimal when the symbol-by-symbol restriction is dropped, or when theprobability mass functions are unknown. Also, if symbols are notindependent and identically distributed, a single code may be insufficient for optimality. Other methods such asarithmetic coding often have better compression capability.
Although both aforementioned methods can combine an arbitrary number of symbols for more efficient coding and generally adapt to the actual input statistics, arithmetic coding does so without significantly increasing its computational or algorithmic complexities (though the simplest version is slower and more complex than Huffman coding). Such flexibility is especially useful when input probabilities are not precisely known or vary significantly within the stream. However, Huffman coding is usually faster and arithmetic coding was historically a subject of some concern overpatent issues. Thus many technologies have historically avoided arithmetic coding in favor of Huffman and other prefix coding techniques. As of mid-2010, the most commonly used techniques for this alternative to Huffman coding have passed into the public domain as the early patents have expired.
For a set of symbols with a uniform probability distribution and a number of members which is apower of two, Huffman coding is equivalent to simple binaryblock encoding, e.g.,ASCII coding. This reflects the fact that compression is not possible with such an input, no matter what the compression method, i.e., doing nothing to the data is the optimal thing to do.
Huffman coding is optimal among all methods in any case where each input symbol is a known independent and identically distributed random variable having a probability that isdyadic. Prefix codes, and thus Huffman coding in particular, tend to have inefficiency on small alphabets, where probabilities often fall between these optimal (dyadic) points. The worst case for Huffman coding can happen when the probability of the most likely symbol far exceeds 2−1 = 0.5, making the upper limit of inefficiency unbounded.
There are two related approaches for getting around this particular inefficiency while still using Huffman coding. Combining a fixed number of symbols together ("blocking") often increases (and never decreases) compression. As the size of the block approaches infinity, Huffman coding theoretically approaches the entropy limit, i.e., optimal compression.[7] However, blocking arbitrarily large groups of symbols is impractical, as the complexity of a Huffman code is linear in the number of possibilities to be encoded, a number that is exponential in the size of a block. This limits the amount of blocking that is done in practice.
A practical alternative, in widespread use, isrun-length encoding. This technique adds one step in advance of entropy coding, specifically counting (runs) of repeated symbols, which are then encoded. For the simple case ofBernoulli processes,Golomb coding is optimal among prefix codes for coding run length, a fact proved via the techniques of Huffman coding.[8] A similar approach is taken by fax machines usingmodified Huffman coding. However, run-length coding is not as adaptable to as many input types as other compression technologies.
Many variations of Huffman coding exist,[9] some of which use a Huffman-like algorithm, and others of which find optimal prefix codes (while, for example, putting different restrictions on the output). Note that, in the latter case, the method need not be Huffman-like, and, indeed, need not even bepolynomial time.
Then-ary Huffman algorithm uses the {0, 1,...,n − 1} alphabet to encode message and build ann-ary tree. This approach was considered by Huffman in his original paper. The same algorithm applies as for binary () codes, except that then least probable symbols are taken together, instead of just the 2 least probable. Note that forn greater than 2, not all sets of source words can properly form ann-ary tree for Huffman coding. In these cases, additional 0-probability place holders must be added. This is because the tree must form ann to 1 contractor;[clarification needed] for binary coding, this is a 2 to 1 contractor, and any sized set can form such a contractor. If the number of source words is congruent to 1 modulon − 1, then the set of source words will form a proper Huffman tree.
A variation calledadaptive Huffman coding involves calculating the probabilities dynamically based on recent actual frequencies in the sequence of source symbols, and changing the coding tree structure to match the updated probability estimates. It is used rarely in practice, since the cost of updating the tree makes it slower than optimizedadaptive arithmetic coding, which is more flexible and has better compression.
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 that the weights form atotally orderedcommutative monoid, meaning a way to order weights and to add them. TheHuffman template algorithm enables one to use any kind of weights (costs, frequencies, pairs of weights, non-numerical weights) and one of many combining methods (not just addition). Such algorithms can solve other minimization problems, such as minimizing, a problem first applied to circuit design.
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. Thepackage-merge algorithm solves this problem with a simplegreedy approach very similar to that used by Huffman's algorithm. Its time complexity is, where is the maximum length of a codeword. No algorithm is known to solve this problem in or time, unlike the presorted and unsorted conventional Huffman problems, respectively.
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 isN digits will always have a cost ofN, 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 without this assumption: the letters of the encoding alphabet may have non-uniform lengths, due to characteristics of the transmission medium. An example is the encoding alphabet ofMorse 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. No algorithm is known to solve this in the same manner or with the same efficiency as conventional Huffman coding, though it has been solved byRichard M. Karp[10] whose solution has been refined for the case of integer costs by Mordecai J. Golin.[11]
In the standard Huffman coding problem, it is assumed that any codeword can correspond to any input symbol. In the alphabetic version, the alphabetic order of inputs and outputs must be identical. Thus, for example, could not be assigned code, but instead should be assigned either or. This is also known as theHu–Tucker problem, afterT. C. Hu andAlan Tucker, the authors of the paper presenting the first-time solution to this optimal binary alphabetic problem,[12] which has some similarities to Huffman algorithm, but is not a variation of this algorithm. A later method, theGarsia–Wachs algorithm ofAdriano Garsia andMichelle L. Wachs (1977), uses simpler logic to perform the same comparisons in the same total time bound. These optimal alphabetic binary trees are often used asbinary search trees.[13]
If weights corresponding to the alphabetically ordered inputs are in numerical order, the Huffman code has the same lengths as the optimal alphabetic code, which can be found from calculating these lengths, rendering Hu–Tucker coding unnecessary. The code resulting from numerically (re-)ordered input is sometimes called thecanonical Huffman code and is often the code used in practice, due to ease of encoding/decoding. The technique for finding this code is sometimes calledHuffman–Shannon–Fano coding, since it is optimal like Huffman coding, but alphabetic in weight probability, likeShannon–Fano coding. The Huffman–Shannon–Fano code corresponding to the example is, which, having the same codeword lengths as the original solution, is also optimal. But incanonical Huffman code, the result is.
Arithmetic coding and Huffman coding produce equivalent results — achieving entropy — when every symbol has a probability of the form 1/2k. In other circumstances, arithmetic coding can offer better compression than Huffman coding because — intuitively — its "code words" can have effectively non-integer bit lengths, whereas code words in prefix codes such as Huffman codes can only have an integer number of bits. Therefore, a code word of lengthk only optimally matches a symbol of probability 1/2k and other probabilities are not represented optimally; whereas the code word length in arithmetic coding can be made to exactly match the true probability of the symbol. This difference is especially striking for small alphabet sizes.[citation needed]
Prefix codes nevertheless remain in wide use because of their simplicity, high speed, andlack of patent coverage. They are often used as a "back-end" to other compression methods.Deflate (PKZIP's algorithm) and multimediacodecs such asJPEG andMP3 have a front-end model andquantization followed by the use of prefix codes; these are often called "Huffman codes" even though most applications use pre-defined variable-length codes rather than codes designed using Huffman's algorithm.
