Algorithms For Dummies

 Struggling with Big Data

book text compression because humans often use the same words when writing. 

In  addition,  LZW  can  operate  on  streaming  data,  but  Huffman  can’t;  Huffman 

needs the full dataset to build its mapping table.

As  the  algorithm  skims  through  the  data-bit  stream,  it  learns  sequences  of 

 characters from it and assigns each sequence to a short code. Thus, when later 

reencountering the same series of characters, LZW can compress them using a 

simpler encoding. The interesting aspect of this algorithm is that it starts from a 

symbolic  table  made  of  single  characters  (usually  the  ASCII  table)  and  then  it 

enlarges  that  table  using  the  character  sequences  it  learns  from  the  data  it 

compresses.

Moreover, LZW doesn’t need to store the learned sequences in a table for decom-

pression;  it  can  rebuild  them  easily  by  reading  the  compressed  data.  LZW  can 

reconstruct the steps it took when compressing the original data and the sequences 

it encoded. This capability comes at a price; LZW isn’t efficient at first. It works 

best with large pieces of data or text (a characteristic common to other compres-

sion algorithms).

LZW  isn’t  a  complex  algorithm,  but  you  need  to  see  a  number  of  examples  to 

understand it fully. You can find quite a few good tutorials at 

http://marknelson. 

us/2011/11/08/lzw-revisited/

 and 

http://www.matthewflickinger.com/lab/ 

whatsinagif/lzw_image_data.asp

. The second tutorial explains how to use LZW 

to compress images. The following example shows a Python implementation. (You 

can find the complete code for this example in the LZW section of the 

A4D; 14; 

Compression.ipynb

  file  of  the  downloadable  source  code  for  this  book;  see  the 

Introduction for details).

def lzw_compress(text):

    dictionary = {chr(k): k for k in range(256)}

    encoded = list()

    s = text[0]

    for c in text[1:]:

        if s

+c in dictionary:

            s = s

+c

        else:

            print ('> %s' %s)

            encoded.append(dictionary[s])

            print ('found: %s compressed as %s' %

                   (s,dictionary[s]))

            dictionary[s

+c] = max(dictionary.values()) + 1

            print ('New sequence %s indexed as %s' %

                   (s

+c, dictionary[s+c]))

            s = c

---

CHAPTER 14