python huffman编码异常不可排序类型

Question

我正在尝试使用来自 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 尝试比较元组，我认为，他无法比较元组的元组。但是我不知道我必须在哪里以及如何创建一个比较方法来解决这个问题？有人可以帮忙吗？ ;-)

Answer 1

我刚遇到完全同样的问题，将一些旧代码从 Python 2 移植到 Python 3，其中包括使用 heapq 的霍夫曼编码算法。问题确实是有时堆中的两个条目具有相同的概率，但是一旦合并了一些符号，就会有不同结构的“元组树”。

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

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

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