About Shannon Fano codes
Shannon Fano coding technique is one of the first algorithms which purpose is to create code words with minimum redundancy. The basic idea is in creating code words with variable code length, like in the case of Huffman codes, which were invented few years later. Practically speaking, Shannon Fano coding technique has plenty common things with Huffman coding ( which has greater practical use ).
As it was mentioned, Shannon Fano coding is based on variable length code words. This means that some particular symbols of message ( which is to be coded ) may be represented with shorter code word than other symbols of the message. The criterion for estimating the length of some code word is the probability of incidence for symbol which is represented by that code word. As the probability gets higher, the code word become shorter.
Although Shannon Fano coding produce code words that doesn't have same code length, it provides such code in which the code words are uniquely decodable. Yet, the code words must be uniquely decodable, exclusive of the order in which the code words are lined up.
Symbols |
Code words |
| A | 0 |
| B | 10 |
| C | 11 |
So the sequence 1000011 can be uniquely decodeable as " BAAAC "
Building
Shannon Fano codes
The algorithm for making code words is :
Line up the symbols by falling probability of incidence
Divide the symbols in two groups, so that both groups have equal or almost equal sum of the probabilities
Assign value 0 to the first group, and value 1 to the second
For each of the both groups go to step 2
Example
Assume that we have the following text:
"EXAMPLE OF SHANNON FANO"
First, we calculate the probabilities of each symbol in the text as
follows:
| Symbol | Codewords |
| E | 2/23 |
| X | 1/23 |
| A | 3/23 |
| M | 1/23 |
| P | 1/23 |
| L | 1/23 |
| O | 3/23 |
| F | 2/23 |
| S | 1/23 |
| H | 1/23 |
| N | 4/23 |
| space | 3/23 |
Now we create the coding tree:
