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

Example Shannon-Fano Coding


To create a code tree according to Shannon and Fano an ordered table is required providing the frequency of any symbol. Each part of the table will be divided into two segments. The algorithm has to ensure that either the upper and the lower part of the segment have nearly the same sum of frequencies. This procedure will be repeated until only single symbols are left.


Symbol  Frequency Code   Code   Total
                  Length        Length
------------------------------------------
   A       24       2     00     48
   B       12       2     01     24
   C       10       2     10     20
   D        8       3     110    24
   E        8       3     111    24
------------------------------------------
  total: 62 symbols   SF coded: 140 Bit
         linear (3 Bit/Symbol): 186 Bit


Example Shannon-Fanocode tree


The original data can be coded with an average length of 2.26 bit. Linear coding of 5 symbols would require 3 bit per symbol. But, before generating a Shannon-Fano code tree the table must be known or it must be derived from preceding data.


 <   ^   > 

Shannon-Fano Coding Shannon-Fano Coding Algorithm Encoding