2.3.2 Sample-2

Input.
Symbol alphabet A = {a, b, c, d, e, f, g, h, i},
Set of costs C = {3, 21, 2, 1, 8, 34, 1, 13, 5}.

Output.
Code H(A,C) = {000001, 01, 0000001, 00000000, 0001, 1, 00000001, 001, 00001}.
Sum S(H) = 3*6 + 21*2 + 2*7 + 1*8 + 8*4 + 34*1 + 1*8 + 13*3 + 5*5 = 220.

3 Basic technique

The technique works by creating a binary tree of nodes. These can be stored in a regular arrayIn computer programming, an array also known as a vector or list, is one of the simplest data structures. Arrays hold a fixed number of equally-sized data elements, generally of the same data type. Individual elements are accessed by index using a consecu, 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 heapThis page discusses the heap data structure. For the place where memory is dynamically allocated from, see dynamic memory allocation. In computer science a heap is a specialized tree-based data structure. Its base datatype (used for node keys) must be an 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. Put the two nodes into the tree, noting their location.
   3. If parent links are used, set the children of any internal nodes to point at their parents.
   4. Create a new internal node, using the two nodes as children and their combined weight as the weight.
   5. Push the new node into the heap.
4. The remaining node is the root node.

Note: it may be beneficial to generate codes with minimum length variance, since in the worst case when several long codewords have to be transmitted in a row it may lead to unwanted side effects(for example if we use a buffer and constant rate transmitter, it increases the mimimum buffer size). To reduce variance every newly generated node must be favored among same weight nodes and placed as high as possible. This will balance the length, keeping same average rate.

4 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 these 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. Expanding the alphabet size by coalescing multiple symbols into "words" before Huffman coding can help a bit. The worst case for Huffman coding can happen when the probability of a symbol exceeds 2^-1 making the upper limit of inefficiency unbounded. To prevent this, run-length encodingRun-length encoding (RLE is a very simple form of data compression in which runs of data (that is, sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original ru can be used to preprocess the symbols.

Extreme cases of Huffman codes are connected with Fibonacci and Lucas numbersIn mathematics, the Fibonacci numbers form a sequence defined recursively by: : In words: you start with 0 and 1, and then produce the next Fibonacci number by adding the two previous Fibonacci numbers. The first Fibonacci numbers (sequence A000045 in OEI and Wythoff array.

Arithmetic codingArithmetic coding is a method for lossless data compression. It is a form of entropy encoding, but where other entropy encoding techniques separate the input message into its component symbols and replace each symbol with a code word, arithmetic coding en produces slight gains over Huffman coding, but in practice these gains have not been large enough to offset arithmetic coding's higher computational complexity and patentA patent is a set of exclusive rights granted by a government to an inventor or applicant for a limited amount of time (normally 20 years from the filing date). The term "patent" originates from the term patere which means to lay open (to public inspectio royaltiesRoyalty may refer to either: the royal family of a country with a monarchy the payment made to the owner of a copyright, patent, or trademark, for the use thereof. ( As of November 2001, IBM owns patents on the core concepts of arithmetic coding in several jurisdictions.)

5 Variations

5.1 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.

5.2 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).

5.3 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.

5.4 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.

6 Applications

Arithmetic coding can be viewed as a generalization of Huffman coding.

Although arithmetic coding offers better performance than Huffman coding, Huffman coding is still in wide use because of its simplicity 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.

7 External links

• Huffman's original article: D.A. Huffman, "A method for the construction of minimum-redundancy codes", Proceedings of the I.R.E., sept 1952, pp 1098-1102
• Background story: Profile: David A. Huffman, Scientific American, Sept. 1991, pp. 54-58
• 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", STOC 2002: 785-791

Lossless compression algorithms

<Hide>