Algorithms For Dummies

 

   

  PART 4 

 Struggling with Big Data

5. 

The next letter has already appeared before; it’s an A. The next letter is a B, 

which makes the AB letter combination; this also appears in the symbolic table. 

However, the next letter is a C, which makes a new sequence and which the 

algorithm now encodes as 258.

6. 

The final three letters are another set of ABC, so the code for them is 258 again. 

Consequently, the encoded output for ABABCABCABC is

Compressed: [65, 66, 256, 67, 258, 258]

All the learning and encoding operations translated into final compression data 

consisting of just six numeric codes (costing 8 bits each) against the initial 11 test 

letters. The encoding results in a good compression ratio of about half the initial 

data: 6/11 = 0.55.

Retrieving the original text from the compressed data requires a different, inverse 

procedure, which accounts for the only situation when LZW decoding may fail to 

reconstruct  the  symbolic  table  when  a  sequence  starts  and  ends  with  the 

same character. This particular case is taken care of by Python using an if-then- 

else command block, so you can safely use the algorithm to encode and decode 

anything:

def lzw_decompress(encoded):

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

    current = encoded[0]

    output = reverse_dictionary[current]

    print ('Decompressed %s ' % output)

    print ('>%s' % output)

    for element in encoded[1:]:

        previous = current

        current = element

        if current in reverse_dictionary:

            s = reverse_dictionary[current]

            print ('Decompressed %s ' % s)

            output 

+= s

            print ('>%s' % output)

            new_index = max(reverse_dictionary.keys()) 

+ 1

            reverse_dictionary[new_index

            ] = reverse_dictionary[previous] 

+ s[0]

            print ('New dictionary entry %s at index %s' %

                    (reverse_dictionary[previous] 

+ s[0],

                     new_index))

---

CHAPTER 14