next up previous
Next: Huffman Coding Up: Lossless Compression Algorithms (Entropy Previous: Basics of Information Theory

The Shannon-Fano Algorithm

This is a basic information theoretic algorithm. A simple example will be used to illustrate the algorithm:

       Symbol     A    B    C    D    E
      ----------------------------------
       Count     15    7    6    6    5

Encoding for the Shannon-Fano Algorithm:

1. Sort symbols according to their frequencies/probabilities, e.g., ABCDE.

2. Recursively divide into two parts, each with approx. same number of counts.

      Symbol   Count   log(1/p)     Code     Subtotal (# of bits)
     ------   -----   --------   ---------  --------------------
        A      15       1.38          00              30
        B       7       2.48         01             14
        C       6       2.70         10             12
        D       6       2.70        110             18
        E       5       2.96        111             15
                                 TOTAL (# of bits): 89



Dave Marshall
10/4/2001