Shannon–Fano coding: Difference between revisions

Revision as of 14:29, 27 May 2020

Revision as of 17:31, 26 December 2020

Line 5:

* '''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 [[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 |url=https://pdfs.semanticscholar.org/4253/7898a836d0384c6689a3c098b823309ab723.pdf |accessdateaccess-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 205:

| url = http://www.pkware.com/documents/casestudies/APPNOTE.TXT

| title = <tt>APPNOTE.TXT</tt> - .ZIP File Format Specification

| accessdateaccess-date = 2008-01-06

| publisher = PKWARE Inc

| date = 2007-09-28

Line 311:

{{Main|Huffman coding}}

A few years later, [[David A. Huffman]] (1949)<ref>{{Cite journal | last1 = Huffman | first1 = D. |authorlink1author-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 379:

==References==

* {{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 | ref =harv | 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}}