Structured Computer Organization, 2nd Edition, by Tanenmoto
Frequency Dependent Codes: The Huffman Code (1952)

• When large amounts of text are stored or transmitted, it pays look for ways
  to compress the text into a smaller number of bits.
  The time needed to transmit a message is proportional to the number of bits
  in the message.
  Compacted data require fewer bits to store, transmission times are reduced.
  
  
• One way of compacting the data is to eliminate the restriction that all
  character codes must be the same length.
  If the codes for common letters such as "e" and "t" were shorter than the codes
  for rare letters such as "q" and "x", the total number of bits needed to store
  or transmit the text would be decreased.
  
  
• Huffman code: a frequency-dependent code
  
  
• Example: Construct the Huffman code for the digits 0,1,2,...,9
  based on the following probabilities:
  

      Digit       0     1    2    3    4    5    6    7    8    9  
      Frequency  .20  .25   .15  .08  .07  .06  .05  .05  .05  .04
  

  
  
  
• NOTE: In order to use the Huffman encoding method for a particular
  application, the frequencies of use for each character must be known.
  
  
• The code developed in this example is appropriate only for those
  transmissions where 0s represent about 20% of the characters, 1s 25%, etc.
  
  
• Step 1:Write down the probability of each character under the character:
  (the order in which the characters are listed in not important.

        0    1     2    3    4    5    6    7    8    9
      .20  .25   .15  .08  .07  .06  .05  .05  .05  .04
  

  
  
  
• Next, the two smallest probabilities are found and a new probability equal to the sum of the two smallest ones is added to the table:

        0    1     2    3    4    5    6    7    8     9
      .20  .25   .15  .08  .07  .06  .05  .05  .05*  .04*
                                                 \   /
                                                  .09
  

  
  
• The process of finding the two smallest unmarked probabilities and creating
  a new one is repeated:

        0    1     2    3    4    5    6     7    8     9
      .20  .25   .15  .08  .07* .06* .05*  .05*  .05*  .04*
                       \     \   /     \    /       \   /
                         \    .13       .10          .09
                           \                        /
                             \                    /
                               \                / 
                                 \            /      
                                     .17
  
  

  
  
• The "leaves" of the tree can be rearranged for a visual construction:
  

      0     4    5     6     7          1     2     3     8     9
     .20   .07  .06   .05   .05        .25   .15   .08   .05   .04
      |    0\    /1   0\    /1          |      |     \   0 \   /1
      |      .13        .10             |      |   0  \     .09
      |        \        /               |      |        \    / 1
      |        0\      /1               |      |          .17
      |           .23                   |     0 \        /
      |          /                      |         \     / 1
      |        /                        |           .32
     0|      /1                       0  \         /
       \   /                              \      / 1
        .43                                 .57
            \                              /
              \                          /
              0  \                     / 1
                    \                / 
                        
                          1.00
  
  

  
  
  
• In the above figure, the characters (in this case digits) have been
  rearranged for clarity.
  To derive the code for a character, start at the root of the tree (1.00)
  and follow the path to the character, writing down a 0 for every left branch
  taken and a 1 for every right branch.
  
  
• For example, to get from the root to the character 6, first go left to .43
  and write down 0. Then go right to .23 and write down a 1, giving 01 so far.
  Then go right again, giving 011. Finally go left, giving 0110.
  
  
• Here's the complete code:

    Digit        Huffman Code         Path from 1.00 to Character
     0               00                     .43,.20
     1               10                     .57,.25
     2              110                     .57,.32,.15
     3             1110                     .57,.32,.17,.08
     4             0100                     .43,.23,.13,.07
     5             0101                     .43,.23,.13,.06
     6             0110                     .43,.23,.10,.05
     7             0111                     .43,.23,.10,.05
     8            11110                     .57,.32,.17,.09,.05
     9            11111                     .57,.32,.17,.09,.04
  

  
  
• The shortest codes, 00 and 10, are assigned to the two most common
  characters, whereas the two longest codes are assigned to relatively
  infrequently occuring characters.
  This situation is contrasted with one where each character is assigned a
  4-bit code.
  
  
• In other words, the characters in the Huffman scheme are assigned a variable
  number of bits, depending on the relative frequency within the file (or a
  "standard" set of files)
  
  
• Characters 0, 1, and 2 together account for 60% of the characters to be
  transmitted and all three are shorter than 4 bits.
  In this example, 45% of the characters will require 2 bits, 15% will require
  3 bits, 31% will require 4 bits, and 9% will require 5 bits.
  This averages to 3.04 bits per character (less than 4 bits per character
  without using Huffman)
  
  
• A list of 1,000,000 numbers would require 3,040,000 bits using this code,
  whereas 4,000,000 would be needed using the 4-bit code.
  
  
• The character code generated by this algorithm is not unique.
  For example, by interchanging the positions of the 8 and 9, we get
  11111 for 8 and 11110 for 9, instead of the other way around.
  
  
• Also, replacing all the 1s by 0s and vice versa produces a new code.
  However, none of these transformations affects the information density of the
  code, because what matters is how many bits each character is assigned.
  
  
• Decoding process for the Huffman code:
  
  1. Receive one bit at a time
  2. Examine the first bit to see if it's a valid code
  3. If it is not, the first 2 bits are examined to see if they make a valid code
  4. If not, the first 3 bits are checked, and so on
  5. Eventually a character is recognized and the process is repeated
     beginning with the first bit following the character.