Python压缩运行长度编码

Question

我正在尝试学习行程长度编码，并在网上找到了这个挑战，但我做不出来。它要求你编写一个压缩函数compression(strg)，它将长度为64的二进制字符串strg作为输入，并返回另一个二进制字符串作为输出。输出的二进制字符串应该是输入字符串的行程长度编码。

例如，对于输入字符串'1010101001010101101010100101010110101010010101011010101001010101'，函数应该返回'1010101001010101*4'。

这是我的代码，但它无法找到模式：

from itertools import *

def compression(strg):
    return [(len(list(group)),name) for name, group in groupby(strg)]

我需要一些帮助来解决这个问题。

- user1681664

---

Run-length encoding（RLE）可以找到固定大小块的重复。我猜你需要在这里检测16位块的运行情况。这应该是问题规范的一部分。 - Rafał Dowgird

Answer 1

我认为你混淆了RLE和Lempel / Ziv滑动窗口压缩。

RLE仅适用于重复字符：WWWWWWWW => W8 LZ具有滑动窗口，可以像你所描述的那样捕捉模式。

David MacKay的网站包括Python中的示例压缩代码，包括LZ。

- user688635

Answer 2

这是最长重复子串问题的一个示例。经典解决方案是使用后缀树数据结构。

对于短字符串，可以使用正则表达式的形式：

import re

s1='1010101001010101101010100101010110101010010101011010101001010101'

i=2
l=s1
j=len(l)/2
while i<len(s1):
    m=re.search('^(.{'+str(j)+'})\\1$',l)
    if m:
        l=m.group(1)
        i,j=i+1,len(l)/2
        continue
    else:
        print '{0} * {1} = {2}'.format(l,i,s1)
        break

打印输出结果。请注意，这仅适用于从中间对称的字符串——这种类型的问题的一个小子集。要压缩其他类型的字符串，您需要一个代表性的语法来描述被替换的元素是如何被替代的。

- dawg

Answer 3

以下链接详细解释了这个问题的答案：

使用run-length编码通过def compress(S)函数进行图像压缩

希望这能清楚地解释字符串和二进制压缩的运行长度编码。此编码不使用任何re和itertools导入。

- ohid