page_title: Shannon–Fano coding
section_title: Example with Huffman coding
hierarchical_section_title: Shannon–Fano coding / Comparison with other coding methods / Example with Huffman coding
caption_attribution_description: Huffman Code Beispiel Ablauf
context_page_description: 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.
  Shannon's method chooses a prefix code where a source symbol is given the codeword length. 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", his article introducing the field of information theory.
  Fano's method divides the source symbols into two sets 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.
  Shannon–Fano codes are suboptimal in the sense that they do not always achieve the lowest possible expected codeword length, as Huffman coding does. However, Shannon–Fano codes have an expected codeword length within 1 bit of optimal.
context_section_description: We use the same frequencies as for the Shannon–Fano example above, viz:
  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. 
  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
  We see that the Huffman code has outperformed both types of Shannon–Fano code, which had expected lengths of 2.62 and 2.28.
caption: Huffman Algorithm
exif: {}