View source for Huffman code

An algorithm for the construction of optimal (i.e., minimum redundancy) variable-length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h1103401.png" />-ary codes (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h1103402.png" />) for finite memoryless information sources with known statistics was proposed by D. Huffman in 1952 (see [[#References|[a1]]], [[#References|[a2]]]). (The algorithm refines the Morse alphabet, as it associates the shortest codewords to the most probable source letters.)

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h1103403.png" /> be such a source with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h1103404.png" /> letters, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h1103405.png" />, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h1103406.png" /> be the probability that the source emits letter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h1103407.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h1103408.png" />). Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h1103409.png" /> be a uniquely decipherable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034011.png" />-ary code for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034012.png" /> (i.e., a set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034013.png" /> sequences <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034014.png" /> from an alphabet of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034015.png" /> symbols) and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034016.png" /> be the length (or number of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034017.png" />-ary symbols) of codeword <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034018.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034019.png" />) associated to the letter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034020.png" />. The difference

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034021.png" /></td> </tr></table>

between the average length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034022.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034023.png" /> and the source entropy (cf. also [[Entropy|Entropy]]) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034024.png" /> is called the redundancy of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034025.png" />. A Huffman code <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034026.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034027.png" /> minimizes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034028.png" /> (hence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034029.png" />) over the set of all uniquely decipherable codes for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034030.png" />.

In the binary case (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034031.png" />), the algorithm consists in the construction of a sequence of  "reduced"  sources <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034032.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034033.png" /> is obtained from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034034.png" /> by merging the two least probable letters of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034035.png" /> into one letter of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034036.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034037.png" />) and leaving all other letters unchanged (ties are broken arbitrarily). The probability of the new letter is the sum of the probabilities of the merged letters. The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034038.png" /> mergings can be represented by a binary code tree in which each letter of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034039.png" /> corresponds to a leaf and each codeword is the sequence of binary labels of the path from root to leaf. (If the code alphabet has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034040.png" /> letters, each reduced source is obtained by merging the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034041.png" /> least probable letters of the previous source, except possibly in the first step, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034042.png" /> letters have to be grouped together, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034043.png" /> being the remainder of the division of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034044.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034045.png" />. The resulting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034046.png" />-ary code tree is labeled and again the codewords are the sequences of labels from root to leaves.)

Owing to the arbitrary resolution of possible ties in grouping the least probable sequences at each step, for a given source <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034047.png" /> there may be several distinct Huffman codes, but two such codes are considered (essentially) different only if the corresponding sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034048.png" /> of codeword lengths do not coincide. However, the average length of all Huffman codes for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034049.png" /> is the same.

More formally, consider the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034050.png" /> of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034051.png" />-order probability distributions (cf. [[Probability distribution|Probability distribution]]) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034052.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034053.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034054.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034055.png" />). The informational divergence (also called the [[Kullback–Leibler information|Kullback–Leibler information]]) between two probability distributions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034056.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034057.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034058.png" /> is the non-negative quantity <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034059.png" />. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034060.png" /> vanishes if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034061.png" />, hence it can be considered as an oriented pseudo-distance (cf. also [[Pseudo-metric|Pseudo-metric]]) in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034062.png" />. Now, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034063.png" /> is the set of codeword lengths of a Huffman code <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034064.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034065.png" />, the redundancy <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034066.png" /> is equal to the informational divergence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034067.png" /> between the source probability distribution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034068.png" /> and the  "dyadic"  probability distribution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034069.png" />.

The optimality of Huffman codes can now be restated by saying that to any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034070.png" /> (i.e., to any source <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034071.png" />), the algorithm associates (one of) the dyadic probability distribution(s)  "closest"  to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034072.png" /> in the sense of the pseudo-metric <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034073.png" />.

In several practical situations the statistics of the source is not perfectly known or varies over time, and the necessity arises of updating the Huffman code when the new(ly known) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110340/h11034074.png" /> becomes  "closer"  to a dyadic probability distribution different from the previous one (see [[#References|[a3]]], [[#References|[a4]]]).

See also [[Coding and decoding|Coding and decoding]]; [[Information theory|Information theory]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  D.A. Huffman,   "A method for the construction of minimum redundancy codes"  ''Proc. I.R.E.'' , '''40'''  (1952)  pp. 1098–1101</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  R. Gallager,   "Variations on a theme by Huffman"  ''IEEE Trans. Inform. Theory'' , '''IT–24'''  (1978)  pp. 668–674</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  G. Longo,   G. Galasso,   "An application of informational divergence to Huffman codes"  ''IEEE Trans. Inform. Theory'' , '''IT–28'''  (1982)  pp. 36–43</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  D.A. Lelewer,   D.S. Hirschberg,   "Data compression"  ''ACM Comput. Surv.'' , '''19'''  (1987)  pp. 261–296</TD></TR></table>