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']

我的想法是在字符串（文本）中使用索引号，并检查切割出的子字符串是否存在于键字典中，如果不存在，则添加它。如果存在，则继续检查子字符串并添加下一个字符。请帮忙看看我的错误在哪里？

PS：我知道互联网上有一些Lempel-Ziv Python代码，但我必须使用这个代码。

PPS：Lempel Ziv算法的工作方式如下。 首先检查给定字符串中的第一个字符是否存在于键（字典）中，如果不存在，则检查字符串中的下一个字符，并检查此新子字符串是否存在于键中。如果不存在，则添加子字符串；如果存在，则添加下一个字符并继续此过程...例如，对于我的字符串，输出应该是：[A,AA,AB,B,C,D,ABC,AAA,BC,DE,E,EE,EEE,CB,BB,BBB,DD,AAE]。

- anon

---

你的“预期”输出是什么？ - Christian Dean

Lempel-Ziv算法的工作原理如下：检查给定字符串中的第一个字符，如果不存在于键（字典）中，则检查字符串的下一个字符并检查此新子字符串；如果不存在，则添加子字符串；如果存在于键中，则添加下一个字符，并继续这个过程...例如，对于我的字符串，输出应该是：A，AA，AB，B，C，D，ABC，AAA，BC，DE，E，EE，EEE，CB，BB，BBB，DD，AAE。 - anon

请更明确地指定所针对的算法：LZ77或LZ78，还是其他算法？ - greybeard

标记 [tag:python]，[tag:python-2.7] 和 [tag:python-3.x] 看起来有些过度了 - 请查看标签描述。 - greybeard

我的错误在哪里？我认为问题出在没有记录sub_strin_check(text, index)的返回值。（你想让“else: sub_strin_check()”成为“if text[index] not in keys:”或第一个“try”语句的一部分吗？） - greybeard

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

- dhishan

---

我会使用字典进行查找，为什么不用set？ - greybeard

字典具有恒定的查找时间，而列表是一个具有O(n)的数组。列表在查找方面较慢，而字典则是为此工作而设计的。 - dhishan

字典有 [这个]，而列表有 [那个] - 这可能解释了为什么不选择 list，但是：为什么不选择 set？字典就是为这个工作而生的 - 哪个工作？元素的？并不完全是。键值对的值？当然是。 - greybeard

其实，我同意你的观点。集合和字典在内部都使用了哈希。这意味着常数时间查找。所以两者都可以选择。我之前错误地认为集合是不可变的，并且会影响性能。无论如何，我对集合的理解是错误的。然而，你需要使用set()来初始化集合。[]默认表示列表，{}表示字典。 - dhishan

很高兴能够帮助。如果上面的代码能够完成任务，请将其标记为已回答。 - dhishan

根据您在YT上的参考，答案不应该是[A，AA，C，..]，而应该是[A，AA，B，..]？ - user305883