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