Shannon–Fano coding: Difference between revisions

Revision as of 01:46, 26 October 2017

Revision as of 02:03, 26 October 2017

Line 1:

[[File:Fano-en.svg|thumb|300x300px|Simple example of encoding 6 symbols]]

In the field of [[data compression]], '''Shannon–Fano coding''', named after [[Claude Shannon]] and [[Robert Fano]], is a technique for constructing a [[prefix code]] based on a set of symbols and their probabilities (estimated or measured). It is [[Optimization (mathematics)|suboptimal]] in the sense that it does not achieve the lowest possible expected code word length like [[Huffman coding]]; however it still guarantees that all code word lengths are within one bit of their theoretical ideal <math>{-\log} P(x)</math>.{{cn|date=October 2016}}. What's good CS157.

The technique was proposed in Shannon's "[[A Mathematical Theory of Communication]]", his 1948 article introducing the field of [[information theory]]. The method was attributed to Fano, who later published it as a [[technical report]].<ref>{{harvnb|Fano|1949}}</ref>