LZW.py

from io import StringIO


def compress(uncompressed):
    """Compress a string to a list of output symbols."""

    # Build the dictionary.
    dict_size = 256
    dictionary = dict((chr(i), i) for i in range(dict_size))
    # in Python 3: dictionary = {chr(i): i for i in range(dict_size)}

    w = ""
    result = []
    for c in uncompressed:
        wc = w + c
        if wc in dictionary:
            w = wc
        else:
            result.append(dictionary[w])
            # Add wc to the dictionary.
            dictionary[wc] = dict_size
            dict_size += 1
            w = c

    # Output the code for w.
    if w:
        result.append(dictionary[w])
    return result, dictionary


def decompress(compressed, dictionary):
    output = ""
    for k in compressed:
        output = output + get_key(k, dictionary)
    return output

def get_key(val, dictionary):
    for key, value in dictionary.items():
        if val == value:
            return key