Lempel-ziv Compression Algorithm Implemention

I wrote the following code for implementing lempel-ziv compression algorithm for the following sample string: AAAABBCDEABCDABCAAABCDEEEEEECBBBBBBDDAAE Code: keys=[] text = open('t

Solution 1:

I would use the dictionary instead of a list for lookup. Then the conversion from dictionary to list is straight forward if required

input_str = 'AAAABBCDEABCDABCAAABCDEEEEEECBBBBBBDDAAE'

keys_dict = {}

ind = 0
inc = 1while True:
    ifnot (len(input_str) >= ind+inc):
        break
    sub_str = input_str[ind:ind + inc]
    print sub_str,ind,inc
    if sub_str in keys_dict:
        inc += 1else:
        keys_dict[sub_str] = 0
        ind += inc
        inc = 1
        # print'Adding %s' %sub_str

print list(keys_dict)

Output:

['A', 'AA', 'C', 'B', 'E', 'D', 'BB', 'BC', 'BCD', 'BBB', 'ABC', 'DA', 'EE', 'AB', 'EC', 'BD', 'EEE', 'AAA', 'DAA']

Reference for Algorithm: https://www.youtube.com/watch?v=EgreLYa-81Y