Algorithms For Dummies

  Compressing Data 

     273

Instead of using 6 bytes to represent the data, you now need only 4 bytes. To use this 

approach, you limit the maximum count to 255 consecutive values, which means:

 

»

You can encode each sequence in a byte.

 

»

The first value is a zero when the sequence starts from 1 instead of 0.

 

»

When a block of values is longer than 255 elements, you insert a 0 value (so 

the decoder switches to the other value for 0 counts and then starts counting 

the first value again).

This algorithm, run-length encoding (RLE), is very effective if your data has many 

long  repetitions.  This  algorithm  enjoyed  great  success  in  the  1980s  because  it 

could  reduce  fax  transmission  times.  Fax  machines  worked  on  just  black-and- 

white images, and by land-line telephone, shrinking the long sequences of zeros 

and ones that made up images and text proved to be convenient. Though busi-

nesses seldom use fax machines now, scientists still use RLE for DNA compression 

in  combination  with  the  Burrows-Wheeler  Transform  (an  advanced  algorithm 

that  you  can  read  about  at 

http://marknelson.us/1996/09/01/bwt/

),  which 

rearranges (in a reversible way) the genome sequence in long runs of the same 

nucleotide. You also find RLE used for compression of other data formats, such as 

JPEG  and  MPEG  (see 

http://motorscript.com/mpeg-jpeg-compression/

  for 

additional details).

Data characteristics rule the success of a compression algorithm. By knowing how 

algorithms  work  and  exploring  your  data  characteristics,  you  can  choose  the 

best-performing  algorithm  or  combine  more  algorithms  in  an  effective  way. 

Using multiple algorithms together creates an ensemble of algorithms.