Shannon-Fano Coding Algorithm

Shannon-Fano coding refers to either of two related algorithms for building a prefix code, a set of variable-length codewords for a group of symbols, based on how often each symbol occurs, so that more frequent symbols get shorter codes. Claude Shannon's version, described in his foundational 1948 paper A Mathematical Theory of Communication, calculates each codeword's length directly from the symbol's probability and then assigns codes according to cumulative probability; Robert Fano's version, published in a 1949 technical report, instead works top down, repeatedly splitting the symbol list into two groups with probabilities as close to equal as possible and assigning a 0 or 1 to each half until every symbol has its own code. Both versions produce codes that come within one bit of the theoretical optimum but are not actually optimal, unlike David Huffman's 1952 algorithm, which builds its code from the leaves upward rather than splitting from the root downward and always produces the best possible prefix code for a given set of probabilities; this is why Shannon-Fano coding, though historically important, is almost never used in practice today.