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

Algorithm Encoding


  create table providing frequencies
 -----------------------------------------------
  sort symbols according to frequency
  in descending order
 -----------------------------------------------
  start with the entire table
 -----------------------------------------------
      division:
     -------------------------------------------
      seek pointer to the first and
      last symbol ot the segment
     -------------------------------------------
      divide the segment into two parts, both
      nearly equal in sum of frequencies
     -------------------------------------------
      add a binary 0 to the code words of the
      upper part and a 1 to the lower part
     -------------------------------------------
      search for the next segment containing
      more than two symols and repeat division
 -----------------------------------------------
  coding of the origination data according to
  to code words in the table
 -----------------------------------------------

The decoding process follows the general algorithm for interpretation of binary code trees.


 <   ^   > 

 Interpretation of Code Trees 

Shannon-Fano Coding Example Shannon-Fano Coding Step-by-Step Construction