霍夫曼编码问题

这是我的节点类：

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]

(请注意,数据字段最终将包含节点子节点中所有项目的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)]

我发现我真的很想避免这种“一站式” /“有序的”错误-将来我该如何解决？

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__应该修复,请进行更改并编辑问题,以提供一些输入和希望获得的确切输出. 更多 关于：

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

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

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