霍夫曼编码问题

Question

作为练习，我正在尝试使用Huffman树对一些符号进行编码，但是使用自己的类而不是Python内置的数据类型。

这是我的节点类：

class Node(object):
    left = None
    right = None
    weight = None
    data = None
    code = ''
    length = len(code)

    def __init__(self, d, w, c):
        self.data = d
        self.weight = w
        self.code = c

    def set_children(self, ln, rn):
        self.left = ln
        self.right = rn

    def __repr__(self):
        return "[%s,%s,(%s),(%s)]" %(self.data,self.code,self.left,self.right)

    def __cmp__(self, a):
        return cmp(self.code, a.code)

    def __getitem__(self):
        return self.code

这里是编码函数：

def encode(symbfreq):
    tree = [Node(sym,wt,'') for sym, wt in symbfreq]
    heapify(tree)
    while len(tree)>1:
        lo, hi = sorted([heappop(tree), heappop(tree)])
        lo.code = '0'+lo.code
        hi.code = '1'+hi.code
        n = Node(lo.data+hi.data,lo.weight+hi.weight,lo.code+hi.code)
        n.set_children(lo, hi)
        heappush(tree, n)
    return tree[0]

注意，data字段最终将包含节点子项中的所有项目的set()。 在我正确编码之前，它只包含一个总和。

以下是我以前用于对树进行编码的函数：

def encode(symbfreq):
    tree = [[wt, [sym, ""]] for sym, wt in symbfreq]
    heapq.heapify(tree)
    while len(tree)>1:
        lo, hi = sorted([heapq.heappop(tree), heapq.heappop(tree)], key=len)
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        heapq.heappush(tree, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    return sorted(heapq.heappop(tree)[1:], key=lambda p: (len(p[-1]), p))

然而，我注意到我的新过程是不正确的：它将顶部节点赋予最长的编码，而不是最终的叶子节点，并且对于输入符号的排列不会产生相同的树形结构，即以下内容不会产生相同的树形结构（使用新编码函数运行时）：

input1 = [(1,0.25),(0,0.25),(0,0.25),(0,0.125),(0,0.125)]
input2 = [(0,0.25),(0,0.25),(0,0.25),(1,0.125),(0,0.125)]

我发现我很难避免这种一位数/排序错误——将来我该如何解决这个问题？

- Tom Kealy

---

你能发布一些错误输出吗？特别是最后一部分。 - Patrick Collins

一眼看上去，我怀疑你的错误在这里 lo, hi = sorted([heappop(tree), heappop(tree)])。这里的两个元素都是节点，而你已经为节点定义了 __cmp__ 作为 cmp(self.code, a.code)，但你还没有设置代码，所以它总是比较两个空字符串。我不确定堆是否真的是你需要的东西，你只是把元素当作从最小到最大排序的列表吗？我忘记了霍夫曼编码的工作原理，所以我不确定这是否是正确的方法。 - Patrick Collins

@PatrickCollins 我在我的原始“无类”代码中使用了堆，因为它总是首先弹出最低权重的项目（这就是创建哈夫曼树的方式）。问题是从第一段代码转换到一个类，我犯了一个错误，我无法纠正 - 因为我不理解__cmp__。 - Tom Kealy

如果你使用数据结构的唯一原因是为了确保它已排序，那么我不明白与使用已排序列表相比的优势在哪里。原始算法中树形数据结构的重点是为了提供更快的解码而不是编码。 - Patrick Collins

@PatrickCollins 我将其用作统计算法的数据结构 - 这对于已排序的列表是行不通的。 - Tom Kealy

Answer 1

这段代码中有不止一个奇怪的地方；-），但我认为你的主要问题在于这个：

def __cmp__(self, a):
    return cmp(self.code, a.code)

堆操作使用比较方法对堆进行排序，但是你告诉它按照节点当前代码长度来排序。你很可能希望堆根据它们的权重进行排序，对吗？这就是霍夫曼编码的工作方式。

def __cmp__(self, a):
    return cmp(self.weight, a.weight)

对于剩下的部分，很难理解，因为你的5个符号中有4个相同（四个0和一个1）。你怎么可能知道它是否正常工作呢？

在循环内部，这是很紧张的：

lo, hi = sorted([heappop(tree), heappop(tree)])

由于修复了__cmp__，现在更容易了：

lo = heappop(tree)
hi = heappop(tree)

排序是无意义的 - 当前最小的元素总是被弹出。因此，弹出两次，lo <= hi必须为真。

我想说的更多 ;-)，但在这一点上，我对你最终想要实现什么感到困惑。如果您同意应修复__cmp__，请进行更改并编辑问题，以同时提供一些输入和您希望获得的确切输出。

更多

关于：

它将最高节点赋予最长的码字，而不是最终叶子，

这不是一个“差1”问题，而是一个“反向”的问题;-) Huffman编码首先查看具有最小权重的节点。从堆中弹出节点越晚，其权重越高，其代码就应该越短。但是您正在使代码变得越来越长，随着过程的进行，它们应该变得越来越短。

您不能在构建树的同时做到这一点。实际上，在树构建过程完成之前，代码是无法知道的。

因此，与其猜测意图等等，我将提供一些可工作的代码，您可以随意修改。我将包括一个示例输入及其输出：

from heapq import heappush, heappop, heapify

class Node(object):
    def __init__(self, weight, left, right):
        self.weight = weight
        self.left = left
        self.right = right
        self.code = None

    def __cmp__(self, a):
        return cmp(self.weight, a.weight)

class Symbol(object):
    def __init__(self, name, weight):
        self.name = name
        self.weight = weight
        self.code = None

    def __cmp__(self, a):
        return cmp(self.weight, a.weight)

def encode(symbfreq):
    # return pair (sym2object, tree), where
    # sym2object is a dict mapping a symbol name to its Symbol object,
    # and tree is the root of the Huffman tree
    sym2object = {sym: Symbol(sym, w) for sym, w in symbfreq}
    tree = sym2object.values()
    heapify(tree)
    while len(tree) > 1:
        lo = heappop(tree)
        hi = heappop(tree)
        heappush(tree, Node(lo.weight + hi.weight, lo, hi))
    tree = tree[0]

    def assigncode(node, code):
        node.code = code
        if isinstance(node, Node):
            assigncode(node.left, code + "0")
            assigncode(node.right, code + "1")
    assigncode(tree, "")

    return sym2object, tree

i = [('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5)]
s2o, t = encode(i)
for v in s2o.values():
    print v.name, v.code

这将打印：

a 010
c 00
b 011
e 11
d 10

所以，正如我们所希望的那样，权重最高的符号具有最短的代码。

- Tim Peters

---

谢谢！这是一个用于硬币称重问题的算法，其中伪造币被赋予值1。我能否将字典修改为元组，因为我有重复的值。 - Tom Kealy

当然可以！并不是必须使用dict；将符号映射到Symbol对象的字典对于大多数应用程序来说只是方便。例如，您可以将sym2object = ...更改为symbols = tuple(Symbol(sym, w) for sym, w in symbfreq)，然后将下一行替换为tree = list(symbols)。如果您编辑您的问题以给出输入及其所需输出的确切示例，我可以尝试给您提供确切的代码。 - Tim Peters

谢谢你的提议，但是今天我自己设法解决了需要的问题。 - Tom Kealy

很抱歉再次打扰您，但排序应该确保原始数组的相对位置不会因编码过程而改变（即第0个bin中的数据放置在最左侧叶子中）。我该如何实现这一点？我已经编辑了问题以反映我所需要的内容。 - Tom Kealy

请提出一个新的问题 - 这个问题已经很长而且令人困惑 ;-) 与其试图“描述”您想要的内容，不如举出确切的输入和输出示例。我不理解您的描述。 - Tim Peters

Answer 2

我猜测问题出在这个段落中：-

lo.code = '0'+lo.code
hi.code = '1'+hi.code

无论是高节点还是低节点都可以成为中间节点，但需要在叶子节点处更新代码，因为那里才是实际符号的位置。我认为在构建哈夫曼树时不应维护任何代码，而应该通过遍历在哈夫曼树构建后获取每个符号的代码。

这是我的伪代码：

 tree = ConstructHuffman(); // Same as your current but without code field

 def encode(tree,symbol): 
     if tree.data == symbol : 
         return None
     else if tree.left.data.contains(symbol) :
         return '0' + encode(tree.left,symbol)
     else : 
        return '1' + encode(tree.right,symbol)

使用上述编码方法计算所有符号的代码，然后您可以使用它们进行编码。

注意：将比较函数从比较代码更改为比较权重。

- Vikram Bhat