In the field of data compression, Shannon–Fano coding is a technique for constructing a prefix code based on a set of symbols and their probabilities (estimated or measured). It is suboptimal in the sense that it does not achieve the lowest possible expected code word length like Huffman coding; however unlike Huffman coding, it does guarantee that all code word lengths are within one bit of their theoretical ideal − logP(x). The technique was pr...
more
In the field of data compression, Shannon–Fano coding is a technique for constructing a prefix code based on a set of symbols and their probabilities (estimated or measured). It is suboptimal in the sense that it does not achieve the lowest possible expected code word length like Huffman coding; however unlike Huffman coding, it does guarantee that all code word lengths are within one bit of their theoretical ideal − logP(x). The technique was proposed in Claude Elwood Shannon's "A Mathematical Theory of Communication," his 1948 article introducing the field of information theory. The method was attributed to Robert Fano, who later published it as a technical report. Shannon–Fano coding should not be confused with Shannon coding , the coding method used to prove Shannon's noiseless coding theorem, or with Shannon–Fano–Elias coding (also known as Elias coding) , the precursor to arithmetic coding.
In Shannon–Fano coding, the symbols are arranged in order from most probable to least...
less
