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 i {\displaystyle i} is given the codeword length l i = ⌈ − log 2 p i ⌉ {\displaystyle l_{i}=\lceil -\log _{2}p_{i}\rceil } . 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:
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, Goldie and Pinch, Jones and Jones, and Han and Kobayashi. It is called Shannon coding by Yeung. Fano's (1949) method, using binary division of probabilities, is called Shannon–Fano coding by Salomon and Gupta. 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 p 1 , p 2 , … , p n {\displaystyle p_{1},p_{2},\dots ,p_{n}} the desired codeword lengths are l i = ⌈ − log 2 p i ⌉ {\displaystyle l_{i}=\lceil -\log _{2}p_{i}\rceil } . Here, ⌈ x ⌉ {\displaystyle \lceil x\rceil } is the ceiling function, meaning the smallest integer greater than or equal to x {\displaystyle x} . 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 p 1 ≥ p 2 ≥ ⋯ ≥ p n {\displaystyle p_{1}\geq p_{2}\geq \cdots \geq p_{n}} . Then, the cumulative probabilities are defined as
c 1 = 0 , c i = ∑ j = 1 i − 1 p j for i ≥ 2 , {\displaystyle c_{1}=0,\qquad c_{i}=\sum _{j=1}^{i-1}p_{j}{\text{ for }}i\geq 2,}
… excerpt ends here. Continue reading the full article.
