Author: Arkadi Kagan arkadi_kagan@hotmail.com Document: Entropy Compression Methods.

• Shannon-Fano Coding.

  
  The Shannon-Fano coding is differ in the way that Minimal-Prefix code is created.
  
  1. Sort symbols by probabilities to be found in the source stream.
  
  _{Start recursion:}
  2. Divide list of sorted symbols in two parts. There must be an equal probability that arbitrary symbol from the source stream ( if it is in the relevant range ) can be found in the left or right part of the list.
  3. Create node A of Shannon-Fano tree.
  4. Recursively create nodes corresponding to the left and right parts of the list.
  5. Assign left and right children to node A.
  6. Return node A as a result of the recursive function.

• Static Huffman Coding.

  
  The tree for static Huffman Coding is proved [1] to provide with an optimal Prefix Code for any given input stream.
  1. Create a list of sorted nodes corresponding to probabilities for each symbol. Probability of a symbol is assigned to be equal to the node weight.
  
  _{Start of loop:}
  2. Find and remove two nodes with smallest probabilities. Mark nodes A and B.
  3. Create new node with weight[node] = weight[A] + weight[B].
  4. Assign left and right children of node to A and B.
  5. Insert the new node back to the sorted list.
  6. Repeat the loop until the list consist of the only last node.
  On each loop in the process of creating Huffman Tree it is possible to decide what child will be the left and what will be right. In advance if some symbols or sum of symbols have equal weights, it is possible to select each of them when minimal-weight node is searched. Therefore it is possible to create dozen different Huffman Trees. Each tree will be valid Huffman Tree and therefore can be used for compression.
  Now we have a problem to pass statistics data in order for Decoder to be able to build exactly the same tree of the same shape as Encoder do.
  
  It can be proved that special shape of Huffman Tree called Canonical can be entirely defined by lengths of codes for each symbol. For typical 256 symbol alphabet the single symbol code length can not exceed 8 bits. This is in contrast to count of occurrences or floating-point probability that can be arbitrary big or can require arbitrary tight precision. The list of code lengths is redundant data that can be compressed by itself too. In the common case it can be RLE but some more sophisticated compressions can be used else.
  

  Canonical Huffman Tree:

  Canonical Huffman Tree follow two basic rules:
  1. Shorter codes filled with zeros to the right have a numerical higher value than longer codes.
  2. Withing the same length numerical values of symbols increase with alphabet.
  In order to obtain lengths of codes there is no other way but building Huffman tree. I will be glad to be corrected if this my statement is wrong.
  Given the lengths for each symbol code it is possible to get actual code for Canonical Huffman Coding like this:
  • Mark Lⁿ_kn code number k_n of length n.
  • k_n is a number of symbols coded by n bits.
  • Let m be the length of the longest code.
  • L^m₀ = 0^m.
  • L^m₁ = 0^m + 1.
  • L^m_km = 0^m + k_m.
  • L^m-1₀ = (L^m_km >> 1) + 1.
  • L^m-1_km-1 = L^m-1₀ + k_m-1.
  • L¹₀ = (L²_k2 >> 1) + 1.
  • L¹_k1 = L¹₀ + k₁.
  
  

  Encoding Static Huffman Code.

  
  Without relation of how Huffman Codes are calculated, there is a common scheme of encoding the Static Huffman Code.
  • Build Huffman Tree and calculate codes.
  
  Start the encoding loop here.
  • Read the next input symbol s.
  • Find or calculate code for symbol s - code[s].
  • Output code[s].
  • Continue the encoding loop.

  Decoding Static Huffman Code.

  
  Decoding is symmetric to encoding, however, here it is:
  • Build Huffman Tree and/or calculate codes.
  
  Start the decoding loop here.
  • Find a code corresponding to the given bits stream, starting from the current position.
    Suppose found code is corresponding to symbol s. The length of code[s] is l bits.
  • Output symbol s.
  • Adjust current point in the input stream by l bits.
  • Continue the decoding loop.

• Adaptive Huffman Coding.

  
  The main disadvantage of Static Huffman Coding is a need to care statistics information together with encoded stream of symbols. Adaptive scheme allow to avoid transmitting statistics data. Statistics information is gathered in the same pass and Huffman tree is updated accordinly. This way Encoder and Decoder both build Huffman tree while reading stream of data.
  Advantages of Adaptive Huffman Coding, as always with Adaptive Codings, are coming by cost of optimality and therefore by cost of compression rate.
  This algorithm is found by Gallager and improved by Knuth [5].
  1. Start with a fixed Huffman Tree.
     
     • A tree with single special node O.
       This variant is preferred by most authors for simplicity and efficiency. Weight of node O is subject to discussion. Some implementations use value zero to encode O with longest code.
     • The full balanced tree, providing equal probability for each symbol.
       This variant thought to get less compression but I did not found based prove if it is right. The opposite can be true. For sure this variant require more wasted memory and CPU time for reordering tree.
     Adaptive Huffman Coding require advanced properties from the tree nodes:
     • All nodes are indexed.
     • Indexes are sorted by node weights.
     • The first index is for leaf node of symbol with longest code.
     • The last index is for root node.
     • Nodes of each tree level are sorted by weights.
     • The tree is valid Huffman tree with all corresponding properties.
  _{Start of main loop:}
  2. Read next input symbol A.
  3. Check if A already exist in the tree. If started with Balanced tree it exist always.
  4. If A is not found in the tree:
     • Output code for pseudo symbol O.
     • Output uncompressed code for symbol A.
     • Create tree node for symbol A with weight corresponding to zero occurrence.
     • Create new node P.
     • Set weight(P) = weight(A) + weight(O).
     • Place node P instead of node O, including parent pointer and place in the indexes list.
     • Assign left and right children of node P to be nodes O and A. Decide what node is left or right in order to keep nodes sorted.
     • Update list of indexes to include new nodes O and A.
     Else
     • Output current code for node A.
  5. Update Adaptive Huffman Tree:
     _{Start of loop:}
     • Increase weight of node A.
     • If weight of A is bigger than next node by index:
       • Find node N with weight(N) > weight(A).
       • Sign predecessor of N in index list B.
       • Exchange nodes A and B including place in list of indexes and parent node but not children nodes.
     • Set A to its parent or NULL if not exist.
     • Continue the loop until A is not NULL.
  6. Continue the main loop until input symbols are available.

  Decoding Adaptive Huffman Code.

  
  The decoding process is generally symmetric to encoding.
  1. Start with a fixed Huffman Tree. The tree must have the same special properties like it was defined for encoding. The initialization of the tree must be similar to one used for encoding.
  
  Start the decoding loop.
  2. Find a code, corresponding to the bits stream starting from the current input bit stream position. Sign it code[s] of length l.
  3. If s is a special symbol O,
     • Read single uncoded symbol A.
     • Output symbol A.
     • Create tree node for symbol A with weight corresponding to zero occurrences.
     • Create new node P.
     • Set weight(P) = weight(A) + weight(O).
     • Place node P instead of node O, including parent pointer and place in the index list.
     • Assign left and right children of node P to be nodes O and A. Decide what node is left or right in order to keep nodes sorted.
     • Update list of nodes to include new nodes O and A.
     else
     • Output the found symbol s.
     • Assign variable A to be the same symbol s.
  4. Update the Adaptive Huffman Tree exactly like it was done for encoding.
  5. Continue the decoding loop.

• Define base[], symb[] and off[] arrays.
• base[i] is amount of codes of length i.
• symb[] is an array of symbols sorted by two keys:
  1. Length of code
  2. Numerical symbol value.
• offs[i] is index in symb[] array.
  symb[offs[i]] = Lⁱ₀
  In other words symb[offs[i]] is first symbol with code length i.

_{Start of the loop:}
• code = next input bit.
• length = 1.
• while code < base[length]
  • code = code << 1.
  • code += next input bit.
  • length = length + 1.
• symbol = symb[offs[length] + code - base[length]].
• Continue loop.

Multilevel Structure of CodeBook.

• On the first level we find the first, for example up to 8, bits of code.
• On the second level we find the next 8 bits and therefore overall codes with length up to 16 bits per code. The first part of code must be taken from the first level node and the last part is taken from the current level node.
• The next levels are not likely to ever appear with 256 symbols of 8-bits alphabet. But nobody give guarantee that longer codes not exist - they do and must be handled.

Limitation of Maximal Code Length.

• Sign L` the maximal allowed length of Huffman code.
• Sign L the current maximal length of Huffman code and therefore the height of Huffman Tree.
• Sign RN<sub>i</sub> the rightmost leaf node on level i.
• Sign LN<sub>i</sub> the leftmost leaf node on level i.
• We have a task to make L` < L therefore lets start from level L.

Start the main loop here.
• Place RN_L instead of its parent. The sibling node of RN_L we sign S.
• Find level j that have leafs and j < (L-1).
• Find LN_j.
• Replace LN_j with new node P.
• Make S and LN_j the children of node P.
• Repeat until riches the required height of Huffman Tree.
  Notice that loop is removing leafs from the bottom level first and then continue to the next level.

General notes:

• The list of probabilities do not have to contain symbols that are not in use.
• Instead of probabilities it is more practical to keep count of occurrences of symbol in the source stream. The only operation that is performed on probability is comparison of two symbol probabilities. This simple operation can be done on symbol counters without calculation of actual probabilities.