作为练习,我正在尝试使用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)]
我发现我很难避免这种一位数/排序错误——将来我该如何解决这个问题?
lo, hi = sorted([heappop(tree), heappop(tree)])
。这里的两个元素都是节点,而你已经为节点定义了__cmp__
作为cmp(self.code, a.code)
,但你还没有设置代码,所以它总是比较两个空字符串。我不确定堆是否真的是你需要的东西,你只是把元素当作从最小到最大排序的列表吗?我忘记了霍夫曼编码的工作原理,所以我不确定这是否是正确的方法。 - Patrick Collins