4

我正在尝试使用http://en.literateprograms.org/Huffman_coding_%28Python%29中的代码在 Python 3 中编写霍夫曼编码， 但它不起作用。如果我在 Python 2.7 中运行代码，它运行良好。

以下几行是问题所在：

heapq.heapify(trees)
while len(trees) > 1:
    childR, childL = heapq.heappop(trees), heapq.heappop(trees)
    parent = (childL[0] + childR[0], childL, childR)
    heapq.heappush(trees, parent)

我得到一个TypeError in heapq.heappush(u,parent): "unorderable types: tuple() < str()"

所以我已经寻找了一个解决方案，我认为，我必须实现一个_lt_函数。可能两个或多个节点具有相同的频率，然后 heapq 尝试比较元组，我认为，他无法比较元组的元组。但我不知道我必须在哪里以及如何创建一个比较方法来解决这个问题？有人可以帮忙吗？;-)

4

2 回答 2

3

我刚刚遇到了完全相同的问题，将一些旧代码从 Python 2 移植到 Python 3，以及使用heapq. 问题确实是，有时堆中的两个条目具有相同的概率，但是一旦某些符号被合并，就会形成不同结构的“元组树”。

示例：如果堆包含(0.2, ("A", "B))然后(0.2, (("C", "D"), "E")))Python 尝试比较字符串和元组。Python 2 只会根据类型名称对不匹配的类型进行“排序”，这没有多大意义，但也不会妨碍算法。另一方面，Python 3 更加严格并且会引发异常。

我的解决方法是在累积概率和“元组树”之间的元组中添加另一个元素，以避免比较实际值。例如，您可以使用元组的 thehash或 the repr，或者一些随机数或不断增加的计数器。

我知道这是一个非常丑陋的 hack，但除非您想使用一些自定义__cmp__函数定义自己的树节点类，否则这似乎是唯一的方法。如果有人有更好的想法，请随时发表评论。

于 2015-09-18T19:22:58.390 回答
0

原因是在 python3x 中你不能比较两种不同类型的项目：

>>> "foo" < 1
Traceback (most recent call last):
  File "<ipython-input-5-de2fb49cc8c4>", line 1, in <module>
    "foo" < 1
TypeError: unorderable types: str() < int()
于 2013-05-04T11:36:33.240 回答