Python，理解哈夫曼码

Question

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

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

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

Answer 1

sym为符号，wt为权重

Answer 2

这是一个有趣的问题。想象一个有五个字母的字典，其中键是字母，值是频率：

a = {'a':1, 'b':2, 'c':3, 'd':4, 'e':5}

然后映射它，使其成为具有频率的列表列表，以及以字母开头的列表到堆变量中，如下所示：

[[1, ['a', '']], [2, ['b', '']], [3, ['c', '']], [4, ['d', '']], [5, ['e', '']]]

然后当你堆化它时，你会得到：

[[1, ['a', '']],
 [3, ['c', '']],
 [2, ['b', '']],
 [5, ['e', '']],
 [4, ['d', '']]]

只需使用有效的字典逐步解决问题，以便像维基百科页面上给出的那样进行编码，您将能够看到每一步的作用。或者使用一个简单的示例，从我给出的示例开始，然后慢慢增加元素的数量，直到您使用真实的文档。

rosetta 代码正在做的是遍历堆并根据频率将数字添加到您在字母后看到的空白字符串，直到每个字母都映射到二进制解释。所以最后你会有这样的事情：

 [['e', '101'], 
  ['d', '010'], 
  ['c', '1001'], 
  ['b', '1100'], 
  ['a', '1101']]

其中出现频率最高的字母需要的位数最少。

Answer 3

这是一个list comprehension。这就是说

例如，[bar(x) for x in foo] 生成一个列表，将 bar(x) 应用于列表中的每个值。

Answer 4

sym2freq 是一个字典，键是一些符号，它们的值是符号的频率。例如，如果您有字符串 'aaabacba'，字典将如下所示

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

那是因为我们有 5 次字母 a，2 次字母 b 和 1 次字母 c。

字典有方法 items()，它将 return 每个键及其相应值的元组。在我们的例子中，它将 return

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

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

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

并且由于列表理解将创建结构列表 [wt, [sym, ""]]，您最终将得到列表

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

我们之所以从符号频率字典变成像列表这样的结构 heap 是因为我们可以根据频率对符号进行分类，正如您正在学习的那样，它是构建哈夫曼树。

Python, understanding Huffman code