Data Compression


Criteria

Survey Formats

Basics

Compression Methods

Shannon-Fano

Example

Algorithm

Step-by-Step

SF versus Huffman

Huffman

Lempel-Ziv (LZ)

Arithmetic Coding

Run Length Encoding

Burrows-Wheeler (BWT)

Implementations

Data Formats


Glossary

Index


Download


www.BinaryEssence.com

Shannon-Fano versus Huffman


The point is whether another method would provide a better code efficiency. According to information theory a perfect code should offer an average code length of 2.176 bit or 134,882 bit in total.


For comparison purposes the former example will be endcoded by the Huffman algorithm:


Huffman code


            Shannon-Fano    Huffman
Sym.  Freq. code len. tot.  code len. tot.
------------------------------------------
 A     24    00   2    48    0    1    24
 B     12    01   2    24    100  3    36
 C     10    10   2    20    101  3    30
 D      8    110  3    24    110  3    24
 E      8    111  3    24    111  3    24
------------------------------------------
total 186             140             138
(linear 3 bit code)

The Shannon-Fano code does not offer the best code efficiency for the exemplary data structure. This is not necessarily the case for any frequency distribution. But, the Shannon-Fano coding provides a similar result compared with Huffman coding at the best. It will never exceed Huffman coding. The optimum of 134,882 bit will not be matched by both.


 <   ^   > 

Shannon-Fano Coding Step-by-Step Construction Huffman Coding