Shannon–Fano coding: Difference between revisions

Revision as of 06:22, 28 February 2023

Latest revision as of 20:17, 15 July 2025

(13 intermediate revisions by 9 users not shown)

Line 1:

{{Short description|Data compression algorithms}}

In the field of [[data compression]], '''Shannon–Fano coding''', named after [[Claude Shannon]] and [[Robert Fano]], is aone name given toof 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]].

* '''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 [[Optimization (mathematics)|suboptimal]] in the sense that they do not always achieve the lowest possible expected codeword length, as [[Huffman coding]] does.<ref name="Kaur">{{cite journal |last1=Kaur |first1=Sandeep |last2=Singh |first2=Sukhjeet |title=Entropy Coding and Different Coding Techniques |journal=Journal of Network Communications and Emerging Technologies |date=May 2016 |volume=6 |issue=5 |page=5 |s2cid=212439287 |url=https://pdfs.semanticscholar.org/4253/7898a836d0384c6689a3c098b823309ab723.pdf |archive-url=https://web.archive.org/web/20191203151816/https://pdfs.semanticscholar.org/4253/7898a836d0384c6689a3c098b823309ab723.pdf |url-status=dead |archive-date=2019-12-03 |access-date=3 December 2019}}</ref> 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]].

Line 11:

==Naming==

Regarding the confusion in the two different codes being referred to by the same name, Krajči et al. write:<ref name="Kraj">Stanislav Krajči, Chin-Fu Liu, Ladislav Mikeš and Stefan M. Moser (2015), "Performance analysis of Fano coding", ''2015 IEEE International Symposium on Information Theory (ISIT)''.</ref> write:

<blockquote>

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]).<ref>{{Cite book |url=https://archive.org/details/sim_att-technical-journal_1948-07_27_3/page/402/ |title=The Bell System Technical Journal 1948-07: Vol 27 Iss 3 |date=1948-07-01 |publisher=AT & T Bell Laboratories |pages=403 |language=en}}</ref> 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.

</blockquote>

Line 41:

===Example===

This example shows the construction of a Shannon–Fano code for a small alphabet. There are 5 different source symbols. Suppose 39 total symbols have been observed with the following frequencies, from which we can estimate the symbol probabilities.

:{| class="wikitable" style="text-align: center;"

Line 311:

{{Main|Huffman coding}}

A few years later, [[David A. Huffman]] (19491952)<ref>{{Cite journal | last1 = Huffman | first1 = D. |author-link1=David A. Huffman| title = A Method for the Construction of Minimum-Redundancy Codes | doi = 10.1109/JRPROC.1952.273898 | journal = [[Proceedings of the IRE]]| volume = 40 | issue = 9 | pages = 1098–1101 | year = 1952 | url = http://compression.ru/download/articles/huff/huffman_1952_minimum-redundancy-codes.pdf}}</ref> gave a different algorithm that always produces an optimal tree for any given symbol probabilities. While Fano's Shannon–Fano tree is created by dividing from the root to the leaves, the Huffman algorithm works in the opposite direction, merging from the leaves to the root.

# Create a leaf node for each symbol and add it to a [[priority queue]], using its frequency of occurrence as the priority.

# While there is more than one node in the queue:

Line 370:

This results in the lengths of 1 bit for A and per 3 bits for B, C, D and E, giving an average length of

:<math display="block">\frac{1\,\text{bit}\cdot 15 + 3\,\text{bits} \cdot (7+6+6+5)}{39\, \text{symbols}} \approx 2.23\,\text{bits per symbol.}</math>

We see that the Huffman code has outperformed both types of Shannon–Fano code, which had expected lengths of 2.62 and 2.28.

Line 379:

==References==

* {{cite journal | first = R.M. | last = Fano | title = The transmission of information | workjournal = 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 |[reprint with journalcorrections] |journal= [[Bell System Technical Journal]] | volume = 27 | pages = 379–423 |date=July 1948|doi=10.1002/j.1538-7305.1948.tb01338.x }}

{{Compression methods}}

{{DEFAULTSORT:Shannon-Fano coding}}

[[Category:Lossless compression algorithms]]

[[Category:Claude Shannon]]

[[Category:Entropy coding]]

[[Category:LosslessData compression algorithms]]