运行长度编码代码

Question

我对编码还很陌生，所以选择 python 作为我的第一门编码语言。我正在进行一项名为运行长度编码的练习。经过一番搜索，我找到了解决方案，但我很难理解代码。有人可以破解这段代码并用简单的语言解释一下吗？谢谢。

string = 'WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB'
x=''.join(['{}{}'.format(k, sum(1 for _ in g)) for k, g in groupby(string)])

Answer 1

首先要做的是将表达式分解成更小的表达式：

bits = ['{}{}'.format(k, sum(1 for _ in g)) for k, g in groupby(string)]
x=''.join(bits)

第二个很简单：我们有一些位列表，每个位都是一个字符串，我们只需将它们连接成一个大字符串。

第一个是列表理解。每个列表理解都可以重写为围绕 append 的 for 语句，所以让我们这样做：

bits = []
for k, g in groupby(string):
    bits.append('{}{}'.format(k, sum(1 for _ in g)))

如果您以前从未见过 groupby，groupby 部分可能看起来很棘手，但如果您单独调用它，应该很明显：

for k, g in groupby(string):
    print(k, list(g))

这给你：

W ['W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W']
B ['B']
W ['W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W']
B ['B', 'B', 'B']
W ['W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W']
B ['B']

换句话说，每个组 g 都是运行个相等的元素，而 k 就是它们都相等的部分。

现在让我们分解一下内部语句：

bits.append('{}{}'.format(k, sum(1 for _ in g)))

分为：

count = sum(1 for _ in g)
bit = '{}{}'.format(k, count)
bits.append(bit)

希望最后两行很明显。所以，这只剩下第一个了。

我们在生成器表达式上调用 sum。生成器表达式就像列表推导式一样但是是惰性的，我们不关心这里的惰性，所以我们可以像上面一样分解它：

things = []
for _ in g:
    things.append(1)
count = sum(things)

所以现在 sum(1 for _ in g) 的作用应该很明显了：它只是 g 中事物的数量。事实上，它就像调用 len(g)，除了它适用于任意迭代器，包括惰性迭代器，而不仅仅是序列。

这是计算可能惰性可迭代对象的惯用方法——但我们可以将其替换为（以牺牲一点性能为代价）：

count = len(list(g))

所以，把它们重新组合起来：

使用groupby将字符串转换成一堆组，每组都是一遍又一遍重复的相同字符。
每一个：
- 计算该组的长度。
- 使用键 'W' 和 W 组有 12 个成员的事实，创建一个类似于 'W12' 的字符串。
- 将其附加到列表中。
获取 ['W12', 'B1', 'W12', 'B3', 'W24', 'B1'] 的列表并将其加入字符串 'W12B1W12B3W24B1'.

Answer 2

考虑 s = 'WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB'。
您的代码相当于：

x=''.join(['{}{}'.format(k, len(list(g))) for k, g in groupby(s)])

x=''.join([str(k) + str(len(list(g))) for k, g in groupby(s)])

l=[]
for k, g in groupby(s):
    l.append(str(k) + str(len(list(g))))

x= ""
for s in l:
    x += s

根据文档，“groupby 生成一个迭代器，该迭代器 returns 来自 iterable 的连续键和组”。

举个例子更容易理解

print(*[(k,list(g)) for k, g in groupby(s)], sep="\n")

输出：

('W', ['W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W'])
('B', ['B'])
('W', ['W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W'])
('B', ['B', 'B', 'B'])
('W', ['W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W', 'W'])
('B', ['B'])

实际上，groupby 返回的迭代器中的每个元素都是一个 char c，迭代器指向所有连续 chars c.

的列表

在您的代码中，您首先创建一个包含所有对的列表（c，c 连续出现的次数）：

x1 = ['{}{}'.format(k, len(list(g))) for k, g in groupby(s)]
# ['W12', 'B1', 'W12', 'B3', 'W24', 'B1']

然后将列表中的所有元素连接在一起以创建一个字符串

x2 = "".join(x1)
# W12B1W12B3W24B1

运行长度编码代码

Run Length Encoding the code

python

run-length-encoding

python-3.x