Editing Shannon–Fano coding (section)

==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.<ref name="LiDrew2014">{{cite book|author1=Ze-Nian Li|author2=Mark S. Drew|author3=Jiangchuan Liu|title=Fundamentals of Multimedia|url=https://books.google.com/books?id=R6vBBAAAQBAJ|date=9 April 2014|publisher=Springer Science & Business Media|isbn=978-3-319-05290-8}}</ref>

===Huffman coding===

{{Main|Huffman coding}}

A few years later, [[David A. Huffman]] (1952)<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:
## Remove the two nodes of lowest probability or frequency from the queue
## Prepend 0 and 1 respectively to any code already assigned to these nodes
## Create a new internal node with these two nodes as children and with probability equal to the sum of the two nodes' probabilities.
## Add the new node to the queue.
# The remaining node is the root node and the tree is complete.

===Example with Huffman coding===
[[File:HuffmanCodeAlg.png|right|thumb|300px|Huffman Algorithm]]

We use the same frequencies as for the Shannon–Fano example above, viz:

:{| class="wikitable" style="text-align: center;"
! Symbol
! A
! B
! C
! D
! E
|-
! Count
| 15
| 7
| 6
| 6
| 5
|-
! Probabilities
| 0.385
| 0.179
| 0.154
| 0.154
| 0.128
|}

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"
! Symbol
! A 
! B 
! C 
! D 
! E
|- 
! Codewords
| 0
| 100 
| 101 
| 110 
| 111
|}

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.