Algorithms For Dummies

  Compressing Data 

     277

    encoded.append(dictionary[s])

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

           %(s,dictionary[s]))

    return encoded

In this example, the algorithm scans the text by checking the text a character at a 

time.  It  begins  by  encoding  characters  using  the  initial  symbolic  table,  which  is 

actually the ASCII table in this case. The best way to see how this code works is to see 

a series of output messages and then analyze what has taken place, as shown here:

text = "ABABCABCABC"

compressed = lzw_compress(text)

print('\nCompressed: %s \n' % compressed)

> A

found: A compressed as 65

New sequence AB indexed as 256

> B

found: B compressed as 66

New sequence BA indexed as 257

> AB

found: AB compressed as 256

New sequence ABC indexed as 258

> C

found: C compressed as 67

New sequence CA indexed as 259

> ABC

found: ABC compressed as 258

New sequence ABCA indexed as 260

found: ABC compressed as 258

Here is a quick synopsis of what these output messages mean:

1. 

The first letter, A, appears in the initial symbolic table, so the algorithm encodes 

it as 65.

2. 

The second letter, B, is different from A but also appears in the initial symbolic 

table, so the algorithm encodes it as 66.

3. 

The third letter is another A, so the algorithm reads the next letter, which is a B, 

and encodes the two-letter combination, AB, as 256.

4. 

The fourth letter, a C, is different from any of the previous letters and also 

appears in the initial symbolic table, so the algorithm encodes it as 67.

---

278