Shannon–Fano coding: Difference between revisions

Revision as of 17:31, 26 December 2020

Revision as of 17:08, 14 January 2021

Line 1:

In the field of [[data compression]], '''Shannon–Fano coding''', named after [[Claude Shannon]] and [[Robert Fano]], is a name given to two different but related techniques for constructing a [[prefix code]] based on a set of symbols and their probabilities (estimated or measured).

In the field of [[data compression]], '''Shannon–Fano coding''', named after [[Claude Shannon]] and [[Robert Fano]], is a name given to two different but 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 <math>i</math> is given the codeword length <math>l_i = \lceil - \log_2 p_i\rceil</math>. 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]].

Line 18 ⟶ 17:

</blockquote>

Shannon's (1948) method, using predefined word lengths, is called '''Shannon–Fano coding''' by Cover and Thomas,<ref>Thomas M. Cover and Joy A. Thomas (2006), ''Elements of Information Theory'' (2nd ed.), Wiley–Interscience. "Historical Notes" to Chapter 5.</ref>, Goldie and Pinch,<ref>Charles M. Goldie and Richard G. E. Pinch (1991), ''Communication Theory'', Cambridge University Press. Section 1.6.</ref>, Jones and Jones,<ref>Gareth A. Jones and J. Mary Jones (2012), ''Information and Coding Theory'' (Springer). Section 3.4.</ref>, and Han and Kobayashi.<ref>Te Sun Han and Kingo Kobayashi (2007), ''Mathematics of Information and Coding'', American Mathematical Society. Subsection 3.7.1.</ref> It is called '''Shannon coding''' by Yeung.<ref>Raymond W Yeung (2002), ''A First Course in Information Theory'', Springer. Subsection 3.2.2.</ref>

Fano's (1949) method, using binary division of probabilities, is called '''Shannon–Fano coding''' by Salomon<ref>David Salomon (2013), ''Data Compression: The Complete Reference'', Springer. Section 2.6.</ref> and Gupta.<ref>Prakash C. Gupta (2006), ''Data Communications and Computer Networks'', Phi Publishing. Subsection 1.11.5.</ref> It is called '''Fano coding''' by Krajči et al.<ref name="Kraj" />.

==Shannon's code: predefined word lengths==

Line 305 ⟶ 304:

==Comparison with other coding methods==

Neither Shannon–Fano algorithm is guaranteed to generate an optimal code. For this reason, Shannon–Fano codes are almost never used; [[Huffman coding]] is almost as computationally simple and produces prefix codes that always achieve the lowest possible expected code word length, under the constraints that each symbol is represented by a code formed of an integral number of bits. This is a constraint that is often unneeded, since the codes will be packed end-to-end in long sequences. If we consider groups of codes at a time, symbol-by-symbol Huffman coding is only optimal if the probabilities of the symbols are [[Statistical independence|independent]] and are some power of a half, i.e., <math>\textstyle 1 / 2^k</math>. In most situations, [[arithmetic coding]] can produce greater overall compression than either Huffman or Shannon–Fano, since it can encode in fractional numbers of bits which more closely approximate the actual information content of the symbol. However, arithmetic coding has not superseded Huffman the way that Huffman supersedes Shannon–Fano, both because arithmetic coding is more computationally expensive and because it is covered by multiple patents.{{cncitation needed|date=March 2014}}

===Huffman coding===

Line 350 ⟶ 349:

In this case D & E have the lowest frequencies and so are allocated 0 and 1 respectively and grouped together with a combined probability of 0.282. The lowest pair now are B and C so they're allocated 0 and 1 and grouped together with a combined probability of 0.333. This leaves BC and DE now with the lowest probabilities so 0 and 1 are prepended to their codes and they are combined. This then leaves just A and BCDE, which have 0 and 1 prepended respectively and are then combined. This leaves us with a single node and our algorithm is complete.

The code lengths for the different characters this time are 1 bit for A and 3 bits for all other characters.

:{| class="wikitable"

Line 381 ⟶ 380:

* {{cite journal | first = R.M. | last = Fano | title = The transmission of information | work = Technical Report No. 65 | year = 1949 | publisher = [[Research Laboratory of Electronics at MIT]] | ___location = Cambridge (Mass.), USA | url = https://archive.org/details/fano-tr65.7z}}

* {{cite journal | first = C.E. | last = Shannon | url = https://archive.org/details/ost-engineering-shannon1948 | title = A Mathematical Theory of Communication | journal = [[Bell System Technical Journal]] | volume = 27 | pages = 379–423 |date=July 1948}}

{{DEFAULTSORT:Shannon-Fano coding}}