python - 霍夫曼编码问题

Question

作为练习，我尝试使用霍夫曼树对一些符号进行编码，但使用我自己的类而不是 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)]

我发现我真的很不擅长避免这种逐一错误/排序错误 - 将来我该如何解决这个问题？

Answer 1

这段代码中有不止一个古怪之处 ;-)，但我认为您的主要问题是:

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

堆操作使用比较方法对堆进行排序，但出于某种原因，您告诉它排序 Node s 由他们的代码的当前长度。您几乎肯定希望堆按权重排序它们，对吧？这就是霍夫曼编码的工作原理。

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__应该修复，进行更改并编辑问题以提供一些输入和您希望获得的确切输出。

更多

关于:

it gives the top nodes the longest codewords instead of the final leaves,

这不是“差 1”的事情，它更像是“倒退”的事情 ;-) 霍夫曼编码首先查看权重最小的节点。节点从堆中弹出的时间越晚，权重就越高，其代码应该越短。但是随着过程的进行，您正在使代码变得越来越长。随着流程的进行，它们应该会越来越短。

您不能在构建树时执行此操作。事实上，在树构建过程完成之前，代码是不可知的。

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

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

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