python - lempel-ziv压缩算法实现

Question

我为以下示例字符串编写了以下代码来实现 lempel-ziv 压缩算法:

AAAABBCDEABCDABCAAABCDEEEEEECBBBBBBDDAAE

代码:

keys=[]
text = open('test').read() # contain of the string: AAAABBCDEABCDABCAAABCDEEEEEECBBBBBBDDAAE
index=0
t=time.time()

def sub_strin_check(text,index_num):
    n = 1
    while True:
        substring = text[index_num:index_num+n]
        if substring not in keys :
            print(substring)
            keys.append(substring)

            # print(keys[-1])
            return (index_num+n)
        else:
            n = n+1
            continue

while True:
    try:
        if text[index] not in keys:
            # print (index)
            keys.append(text[index])

            print(keys.append(text[index]),text[index])
    except:
        break
    else:
        try:
            index = sub_strin_check(text,index)
            print(index)

            print(index)
            index = index + 1
        except:
            break

res = str(keys)
print(res)

with open("result","w") as f:
        f.write(res)

但结果是:

['A', 'A', 'AA', 'AB', 'C', 'C', 'CD', 'ABC', 'ABCA', 'ABCD', 'E', 'E', 'EE', 'EEC', 'B', 'B', 'BB', 'BBD', 'AAE']

我的想法是使用 string(text) 中的索引号，并检查被切片的子字符串是否存在于 keys 字典中，如果不存在则添加它。如果存在，则继续并通过添加下一个字符来检查子字符串。

请帮忙看看我的错误在哪里？

PS:我知道网上有一些 lempel-ziv python 代码，但我必须使用这个代码。

附: lempel ziv 算法以这种方式工作。检查给定字符串中的第一个字符，如果它不存在于键(字典)中，如果它存在于检查字符串中的下一个字符，并检查这个新的子字符串，如果它不存在，则添加子字符串，如果存在于键中，则添加下一个字符，此过程继续...例如，对于我的字符串，输出应为:[A,AA,AB,B,C,D,ABC,AAA,BC,DE,E,EE,EEE,CB ,BB,BBB,DD,AAE]

Answer 1

我会使用字典而不是列表进行查找。然后如果需要的话，从字典到列表的转换是直接的

input_str = 'AAAABBCDEABCDABCAAABCDEEEEEECBBBBBBDDAAE'

keys_dict = {}

ind = 0
inc = 1
while True:
    if not (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 += 1
    else:
        keys_dict[sub_str] = 0
        ind += inc
        inc = 1
        # print 'Adding %s' %sub_str

print list(keys_dict)

输出:

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

算法引用: https://www.youtube.com/watch?v=EgreLYa-81Y