Python中的游程长度编码

Question

我正在尝试编写一个简单的python算法来解决此问题。您能否帮我弄清楚为什么我的代码无法正常工作：

问题：

如果有重复的字符超过4次，则整个重复字符集应用斜杠“ /”代替，后跟一个2位数，即该重复字符的长度以及该字符。例如，“ aaaaa”将被编码为“ / 05a”。不应替换少于4个字符的字符，因为执行编码不会减少字符串的长度。

我的代码：

def runLengthEncode (plainText):
    res=''
    a=''
    for i in plainText:
        if a.count(i)>0:
            a+=i
        else:
            if len(a)>4:
                res+="/" + str(len(a)) + a[0][:1]
            else:
                res+=a
                a=i
    return(res)

Answer 1

我在这里看到了许多很棒的解决方案，但没有一个让我觉得非常pythonic。所以我正在为我今天为这个问题编写的一个实现做出贡献。

def run_length_encode(data: str) -> Iterator[Tuple[str, int]]:
    """Returns run length encoded Tuples for string"""
    # A memory efficient (lazy) and pythonic solution using generators
    return ((x, sum(1 for _ in y)) for x, y in groupby(data))

这将返回一个带有字符和实例数的元组生成器，但也可以很容易地修改为返回一个字符串。这样做的一个好处是，如果您不需要用尽整个搜索空间，那么它都是惰性计算的，并且不会消耗比所需更多的内存或 CPU。

如果您仍然想要字符串编码，可以很容易地为该用例修改代码，如下所示：

def run_length_encode(data: str) -> str:
    """Returns run length encoded string for data"""
    # A memory efficient (lazy) and pythonic solution using generators
    return "".join(f"{x}{sum(1 for _ in y)}" for x, y in groupby(data))

这是适用于所有长度的更通用的运行长度编码，而不仅仅是超过 4 个字符的编码。但是，如果需要，这也可以很容易地通过字符串的条件进行调整。

Answer 2

除了a=i在编码序列后进行设置以及在打印到字符串中时为int设置宽度之外，还可以进行其他设置。您还可以执行以下利用pythons的操作groupby。format在构造字符串时使用它也是一个好主意。

from itertools import groupby

def runLengthEncode (plainText):
    res = []

    for k,i in groupby(plainText):
        run = list(i)
        if(len(run) > 4):
            res.append("/{:02}{}".format(len(run), k))
        else:
            res.extend(run)

    return "".join(res)

Answer 3

Rosetta Code 有很多实现，应该很容易适应您的用例。

这是带有正则表达式的 Python 代码：

from re import sub

def encode(text):
    '''
    Doctest:
        >>> encode('WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW')
        '12W1B12W3B24W1B14W'    
    '''
    return sub(r'(.)\1*', lambda m: str(len(m.group(0))) + m.group(1),
               text)

def decode(text):
    '''
    Doctest:
        >>> decode('12W1B12W3B24W1B14W')
        'WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW'
    '''
    return sub(r'(\d+)(\D)', lambda m: m.group(2) * int(m.group(1)),
               text)

textin = "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW"
assert decode(encode(textin)) == textin

Answer 4

只需观察行为：

>>> runLengthEncode("abcd")
'abc'

最后一个字符被忽略。您必须附加您收集的内容。

>>> runLengthEncode("abbbbbcd")
'a/5b/5b'

糟糕，编码后出现问题。a=i即使您找到了足够长的序列，您也应该进行设置。