lempelziv压缩算法的实现

Question

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

AAAABBCDEABCDABCAAABCDEEEEEECBBBBBBDDAAE

代码：

^{pr2}$

但结果是：

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

我的想法是使用字符串（文本）中的索引号，并检查被切片的子字符串是否退出keys dictionary或nut（如果不存在的话）添加它。如果它存在，继续并通过添加下一个字符来检查子字符串。在

你能帮我看看我的错误在哪里吗？在

PS：我知道internet上有一些lempel-ziv python代码，但我必须使用这些代码。在

PPS: 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)

输出：

^{pr2}$

算法参考： https://www.youtube.com/watch?v=EgreLYa-81Y