lzw.py

"""LZW

>>> LZW_bin([0])
[0]

"""

# import doctest

def LZW_bin(input_seq):
    if input_seq == []:
        return []
    output_seq = []
    patterns = [[0], [1]]
    current_pattern = []
    for bit in input_seq:
        new_pattern = current_pattern + [bit]
        if new_pattern in patterns:
            current_pattern = new_pattern
        else:
            patterns.append(new_pattern)
            output_seq.append(patterns.index(current_pattern))
            current_pattern = [bit]
    output_seq.append(patterns.index(current_pattern))
    return output_seq

def LZW_bin_dec(input_seq):
    if input_seq == []:
        return []
    output_seq = [input_seq[0]]
    word = [input_seq[0]]
    patterns = [[0], [1]]
    for code in input_seq[1:]:
        if code < len(patterns):
            buffer = patterns[code]
        else:
            buffer = word + [word[0]]
        for bit in buffer:
            output_seq.append(bit)
        patterns.append(word + [buffer[0]])
        word = buffer
    return output_seq

TESTS = ["01010101"] + ["0"*i for i in range(7)]
for test in TESTS:
    testseq = [int(c) for c in test]
    compseq = LZW_bin(testseq)
    comp = ''.join([str(b) for b in compseq])
    assert(test != LZW_bin_dec(compseq)) ### machpas
    print(test, comp)

for n in [8, 16]:
    stats = [0] * (n+1)
    for i in range(2**n):
        octet = bin(i)[2:].rjust(n,'0')
        complen = len(LZW_bin([int(b) for b in octet]))
        # print(octet, complen)
        stats[complen] = stats[complen] + 1 #.append(octet)  # ???
    print(stats)

# doctest.testmod()