3

作为练习，我尝试使用 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)]

我发现我在避免这种逐个/订购错误方面真的很糟糕 - 我将来如何解决这个问题？

4

2 回答 2

2

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

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)

排序是没有意义的——总是弹出当前最小的元素。所以pop两次，而且lo <= hi一定是真的。

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

更多的

关于：

它给顶部节点最长的代码字而不是最后的叶子，

这不是“偏离 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

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

于 2013-11-17T01:53:18.063 回答
1

我怀疑问题出在以下部分：-

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)

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

注意：将比较功能从比较代码更改为比较权重。

于 2013-11-16T05:17:15.760 回答