a bit of algo: LZW Compression

LZW compression is a magic show. I am left awe-struck as the algorithm compresses and uncompresses bits of data. The magic is not in the fact that it does compress the data, no, that's the boring part. The magic is in the simplicity and elegance of it.

Compression
Given a string "bananababa", the algorithm starts with a code table. We initialize the code table with the following entries:

0 - a
1 - b
2 - n

This is called the initial code table.

LZW then iterates through the letters in the string while also updating the code table. The algorithm is simply:

buffer := empty;
for c in str:
    if buffer + c is in code_table:
        buffer := buffer + c;
    else:
        output code_table[buffer];
        add (next_index_number++, buffer + c) into code_table;
        buffer := c;
output code_table[buffer];

That's it! So with our example "bananababa", we get: