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:

Receive one bit at a time
Examine the first bit to see if it's a valid code
If it is not, the first 2 bits are examined to see if they make a valid code
If not, the first 3 bits are checked, and so on
Eventually a character is recognized and the process is repeated
beginning with the first bit following the character.

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

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