In the field of data compression, Shannon–Fano coding, named after Claude Shannon and Robert Fano, is one of two related techniques for constructing a prefix code based on a set of symbols and their probabilities (estimated or measured).
Shannon's method chooses a prefix code where a source symbol is given the codeword length . One common way of choosing the codewords uses the binary expansion of the cumulative probabilities. This method was proposed in Shannon's "A Mathematical Theory of Communication" (1948), his article introducing the field of information theory. Fano's method divides the source symbols into two sets ("0" and "1") with probabilities as close to 1/2 as possible. Then those sets are themselves divided in two, and so on, until each set contains only one symbol. The codeword for that symbol is the string of "0"s and "1"s that records which half of the divides it fell on. This method was proposed in a later (in print) technical report by Fano (1949).
Shannon–Fano codes are suboptimal in the sense that they do not always achieve the lowest possible expected codeword length, as Huffman coding does. However, Shannon–Fano codes have an expected codeword length within 1 bit of optimal. Fano's method usually produces encoding with shorter expected lengths than Shannon's method. However, Shannon's method is easier to analyse theoretically.
Shannon–Fano coding should not be confused with Shannon–Fano–Elias coding (also known as Elias coding), the precursor to arithmetic coding.
Naming
Regarding the confusion in the two different codes being referred to by the same name, Krajči et al. write:Stanislav Krajči, Chin-Fu Liu, Ladislav Mikeš and Stefan M. Moser (2015), "Performance analysis of Fano coding", 2015 IEEE International Symposium on Information Theory (ISIT). Around 1948, both Claude E. Shannon (1948) and Robert M. Fano (1949) independently proposed two different source coding algorithms for an efficient description of a discrete memoryless source. Unfortunately, in spite of being different, both schemes became known under the same name Shannon–Fano coding.
There are several reasons for this mixup. For one thing, in the discussion of his coding scheme, Shannon mentions Fano’s scheme and calls it “substantially the same” (Shannon, 1948, p. 17 [reprint]). For another, both Shannon’s and Fano’s coding schemes are similar in the sense that they both are efficient, but suboptimal prefix-free coding schemes with a similar performance.
Shannon's (1948) method, using predefined word lengths, is called Shannon–Fano coding by Cover and Thomas,Thomas M. Cover and Joy A. Thomas (2006), Elements of Information Theory (2nd ed.), Wiley–Interscience. "Historical Notes" to Chapter 5. Goldie and Pinch,Charles M. Goldie and Richard G. E. Pinch (1991), Communication Theory, Cambridge University Press. Section 1.6. Jones and Jones,Gareth A. Jones and J. Mary Jones (2012), Information and Coding Theory (Springer). Section 3.4. and Han and Kobayashi.Te Sun Han and Kingo Kobayashi (2007), Mathematics of Information and Coding, American Mathematical Society. Subsection 3.7.1. It is called Shannon coding by Yeung.Raymond W Yeung (2002), A First Course in Information Theory, Springer. Subsection 3.2.2.
Fano's (1949) method, using binary division of probabilities, is called Shannon–Fano coding by SalomonDavid Salomon (2013), Data Compression: The Complete Reference, Springer. Section 2.6. and Gupta.Prakash C. Gupta (2006), Data Communications and Computer Networks, Phi Publishing. Subsection 1.11.5. It is called Fano coding by Krajči et al.
Shannon's code: predefined word lengths
Shannon's algorithm
Shannon's method starts by deciding on the lengths of all the codewords, then picks a prefix code with those word lengths.
Given a source with probabilities the desired codeword lengths are . Here, is the ceiling function, meaning the smallest integer greater than or equal to .
Once the codeword lengths have been determined, we must choose the codewords themselves. One method is to pick codewords in order from most probable to least probable symbols, picking each codeword to be the lexicographically first word of the correct length that maintains the prefix-free property.
A second method makes use of cumulative probabilities. First, the probabilities are written in decreasing order . Then, the cumulative probabilities are defined as
so and so on. The codeword for symbol is chosen to be the first binary digits in the binary expansion of .
Example
This example shows the construction of a Shannon–Fano code for a small alphabet. There are 5 different source symbols. Suppose 39 total symbols have been observed with the following frequencies, from which we can estimate the symbol probabilities.
{| class="wikitable" style="text-align: center;" ! Symbol ! A ! B ! C ! D ! E |- ! Count | 15 | 7 | 6 | 6 | 5 |- ! Probabilities | 0.385 | 0.179 | 0.154 | 0.154 | 0.128
This source has entropy bits.
For the Shannon–Fano code, we need to calculate the desired word lengths .
{| class="wikitable" style="text-align: center;" ! Symbol ! A ! B ! C ! D ! E |- ! Probabilities | 0.385 | 0.179 | 0.154 | 0.154 | 0.128 |- ! | 1.379 | 2.480 | 2.700 | 2.700 | 2.963 |- ! Word lengths | 2 | 3 | 3 | 3 | 3
We can pick codewords in order, choosing the lexicographically first word of the correct length that maintains the prefix-free property. Clearly A gets the codeword 00. To maintain the prefix-free property, B's codeword may not start 00, so the lexicographically first available word of length 3 is 010. Continuing like this, we get the following code:
{| class="wikitable" style="text-align: center;" ! Symbol ! A ! B ! C ! D ! E |- ! Probabilities | 0.385 | 0.179 | 0.154 | 0.154 | 0.128 |- ! Word lengths | 2 | 3 | 3 | 3 | 3 |- ! Codewords | 00 | 010 | 011 | 100 | 101
Alternatively, we can use the cumulative probability method.
{| class="wikitable" style="text-align: center;" ! Symbol ! A ! B ! C ! D ! E |- ! Probabilities | 0.385 | 0.179 | 0.154 | 0.154 | 0.128 |- ! Cumulative probabilities | 0.000 | 0.385 | 0.564 | 0.718 | 0.872 |- ! ...in binary | 0.00000 | 0.01100 | 0.10010 | 0.10110 | 0.11011 |- ! Word lengths | 2 | 3 | 3 | 3 | 3 |- ! Codewords | 00 | 011 | 100 | 101 | 110
Note that although the codewords under the two methods are different, the word lengths are the same. We have lengths of 2 bits for A, and 3 bits for B, C, D and E, giving an average length of
which is within one bit of the entropy.
Expected word length
For Shannon's method, the word lengths satisfy
Hence the expected word length satisfies
Here, is the entropy, and Shannon's source coding theorem says that any code must have an average length of at least . Hence we see that the Shannon–Fano code is always within one bit of the optimal expected word length.
Fano's code: binary splitting
Outline of Fano's code
In Fano's method, the symbols are arranged in order from most probable to least probable, and then divided into two sets whose total probabilities are as close as possible to being equal. All symbols then have the first digits of their codes assigned; symbols in the first set receive "0" and symbols in the second set receive "1". As long as any sets with more than one member remain, the same process is repeated on those sets, to determine successive digits of their codes. When a set has been reduced to one symbol this means the symbol's code is complete and will not form the prefix of any other symbol's code.
The algorithm produces fairly efficient variable-length encodings; when the two smaller sets produced by a partitioning are in fact of equal probability, the one bit of information used to distinguish them is used most efficiently. Unfortunately, Shannon–Fano coding does not always produce optimal prefix codes; the set of probabilities {0.35, 0.17, 0.17, 0.16, 0.15} is an example of one that will be assigned non-optimal codes by Shannon–Fano coding.
Fano's version of Shannon–Fano coding is used in the IMPLODE compression method, which is part of the ZIP file format.
The Shannon–Fano tree
A Shannon–Fano tree is built according to a specification designed to define an effective code table. The actual algorithm is simple:
For a given list of symbols, develop a corresponding list of probabilities or frequency counts so that each symbol’s relative frequency of occurrence is known. Sort the lists of symbols according to frequency, with the most frequently occurring symbols at the left and the least common at the right. Divide the list into two parts, with the total frequency counts of the left part being as close to the total of the right as possible. The left part of the list is assigned the binary digit 0, and the right part is assigned the digit 1. This means that the codes for the symbols in the first part will all start with 0, and the codes in the second part will all start with 1. Recursively apply the steps 3 and 4 to each of the two halves, subdividing groups and adding bits to the codes until each symbol has become a corresponding code leaf on the tree.
Example
We continue with the previous example.
{| class="wikitable" style="text-align: center;" ! Symbol ! A ! B ! C ! D ! E |- ! Count | 15 | 7 | 6 | 6 | 5 |- ! Probabilities | 0.385 | 0.179 | 0.154 | 0.154 | 0.128
All symbols are sorted by frequency, from left to right (shown in Figure a). Putting the dividing line between symbols B and C results in a total of 22 in the left group and a total of 17 in the right group. This minimizes the difference in totals between the two groups.
With this division, A and B will each have a code that starts with a 0 bit, and the C, D, and E codes will all start with a 1, as shown in Figure b. Subsequently, the left half of the tree gets a new division between A and B, which puts A on a leaf with code 00 and B on a leaf with code 01.
After four division procedures, a tree of codes results. In the final tree, the three symbols with the highest frequencies have all been assigned 2-bit codes, and two symbols with lower counts have 3-bit codes as shown table below:
{| class="wikitable" style="text-align: center;" ! Symbol ! A ! B ! C ! D ! E |- ! Probabilities | 0.385 | 0.179 | 0.154 | 0.154 | 0.128 |- ! First division | colspan="2" | 0 | colspan="3" | 1 |- ! Second division | rowspan="2" style="vertical-align:top"; | 0 | rowspan="2" style="vertical-align:top"; | 1 | rowspan="2" style="vertical-align:top"; | 0 | colspan="2" | 1 |- ! Third division | 0 | 1 |- ! Codewords | 00 | 01 | 10 | 110 | 111
This results in lengths of 2 bits for A, B and C and per 3 bits for D and E, giving an average length of
We see that Fano's method, with an average length of 2.28, has outperformed Shannon's method, with an average length of 2.62.
Expected word length
It is shown by Krajči et al that the expected length of Fano's method has expected length bounded above by , where is the probability of the least common symbol. Szewczyk (2026)Szewczyk, K. (2026). A Gallager-Type Redundancy Bound for Binary Shannon-Fano Coding. arXiv preprint arXiv:2607.04192. claims the following tighter bound dependent on , the probability of the most likely symbol:
and the crossover points , , and are chosen algebraically as the crossing point of the respective curves.
Comparison with other coding methods