Lempel Ziv Welch

lzw.py

def encode(string):
	result = []
	for c in string:
		result.append(ord(c))
	return result

def compress(string):
	dictionary = {chr(i):i for i in range(97,123)}
	last = 256
	result = []
	
	p = ""
	for c in string:
		pc = p + c
		if pc in dictionary:
			p = pc
		else:
			result.append(dictionary[p])
			dictionary[pc] = last
			last += 1
			p = c
	if p:
		result.append(dictionary[p])
	
	return result
	
def decompress(arr):
	dictionary = {i:chr(i) for i in range(97,123)}
	last = 256
	result = []
	
	p = arr.pop(0)
	for c in arr:
		pc = dictionary[p] + dictionary[c][0]
		if pc in dictionary:
			p = pc
		else:
			dictionary[last] = pc
			last += 1
			result.append(dictionary[p])
			p = c
	if p:
		result.append(dictionary[p])
		
	return ''.join(result)
	
data = "thisisthe"
print "Original data:",encode(data)
compressed = compress(data)
print "Compressed Data:",compressed
decompressed = decompress(compressed)
print "Decompressed Data:",decompressed