Python，理解霍夫曼代码

Question

我试图理解“Rosetta 代码”用 python 编写的霍夫曼代码。以下是代码的一小部分。

def encode(symb2freq):
    heap = [[wt, [sym, ""]] for sym, wt in symb2freq.items()] #What does this do?

我假设变量heap是一个列表。但是 wt 和 sym 是什么？

Answer 1

sym2freq 是一个字典，其中包含一些符号的键及其符号频率的值。例如，如果您有字符串“aaabacba”，字典将如下所示

sym2freq = {'a': 5, 'b': 2, 'c': 1}

那是因为我们有 5 倍的字母 a、2 倍的字母 b 和 1 倍的字母 c。

字典有方法items()，它将返回每个键及其各自值的元组。在我们的例子中，它将返回

>>> sym2freq.items()
(('a', 5), ('b', 2), ('c', 1))

理解列表的 for sym, wt in symb2freq.items() 部分只是解包。每次我们从上面获取一个元组时，我们都会将第一个对象分配给变量 sym ，将第二个对象分配给变量 wt 。选择名称 sym 和 wt 纯粹是为了反射(reflect)所代表的值，即符号和权重(频率)。

>>> sym, wt = ('a', 5)
>>> print sym
'a'
>>> print wt
5

由于列表理解将创建结构 [wt, [sym, ""]] 的列表，因此您最终会得到该列表

>>> encode(sym2freq)
[[5, ['a', '']], [2, ['b', '']], [1, ['c', '']]]

我们从符号频率字典转向像列表堆这样的结构的原因是我们可以根据符号的频率对符号进行排序，正如您正在学习的那样，这是一部分构建霍夫曼树。