Example of the LZW algorithm

This is probably old stuff for most of you, but here is my Python implementation of the LZW algorithm.

# The initial LZW tables that maps codes to strings and vice-versa. code_to_str = [chr(i) for i in range(256)] str_to_code = dict((chr(i), i) for i in range(256)) def compress(seq): ''' Returns an LZW compressed list of the input character sequence. ''' output = [] table = dict(str_to_code) s = '' for ch in seq: it = s + ch if it in table: s = it else: output.append(table[s]) table[it] = len(table) s = ch output.append(table[s]) return output def decompress(seq): ''' Returns a decompressed list of the LZW compressed input. ''' table = code_to_str[:] prevcode = seq[0] output = [] output.append(table[prevcode]) for code in seq[1:]: try: entry = table[code] except IndexError: # The lzw special case when code is not yet defined. entry = table[prevcode] entry += entry[0] output.append(entry) table.append(table[prevcode] + entry[0]) prevcode = code return output

Used like this:

data = open('somefile.txt').read() data = compress(data) print decompress(data)

Explanation for how the algorithm works can be found in other places on the net.