我的任务是对霍夫曼树进行编码和解码。我在创建我的树时遇到了问题,我被卡住了。
不要介意打印语句 - 它们只是供我测试并查看我的函数运行时输出的内容。
对于第一个 for 循环,我从主 block 中用于测试的文本文件中获取了所有值和索引。
在第二个 for 循环中,我将所有内容都插入到优先级队列中。
我对下一步该去哪里一头雾水 - 我正在尝试制作节点,但我对如何取得进展感到困惑。有人可以告诉我我这样做是否正确吗?
def _create_code(self, frequencies):
'''(HuffmanCoder, sequence(int)) -> NoneType
iterate over index into the sequence keeping it 256 elements long, '''
#fix docstring
p = PriorityQueue()
print frequencies
index = 0
for value in frequencies:
if value != 0:
print value #priority
print index #elm
print '-----------'
index = index + 1
for i in range(len(frequencies)):
if frequencies[i] != 0:
p.insert(i, frequencies[i])
print i,frequencies[i]
if p.is_empty():
a = p.get_min()
b = p.get_min()
n1 = self.HuffmanNode(None, None, a)
n2 = self.HuffmanNode(None, None, b)
print a, b, n1, n2
while not p.is_empty():
p.get_min()
我手动插入了前两个来开始我的树,对吗?
我如何继续前进?我知道它的想法,只是在代码方面我很困惑。
顺便说一句,这是使用python。我试着查看维基百科,我知道步骤,我只需要代码方面的帮助以及我应该如何继续前进,谢谢!
HuffmanNode 来自这个嵌套类:
class HuffmanNode(object):
def __init__(self, left=None, right=None, root=None):
self.left = left
self.right = right
self.root = root
最佳答案
维基百科中的霍夫曼算法会准确地告诉您如何创建节点树,因此您的程序可以基于该算法或其他类似算法。这是一个带有注释的 Python 程序,显示了相应的维基百科算法步骤。测试数据为英文文本中字母出现的频率。
创建节点树后,您需要向下遍历以将哈夫曼代码分配给数据集中的每个符号。由于这是家庭作业,因此该步骤由您决定,但递归算法是处理它的最简单和最自然的方法。只有六行代码。
import queue
class HuffmanNode(object):
def __init__(self, left=None, right=None, root=None):
self.left = left
self.right = right
self.root = root # Why? Not needed for anything.
def children(self):
return((self.left, self.right))
freq = [
(8.167, 'a'), (1.492, 'b'), (2.782, 'c'), (4.253, 'd'),
(12.702, 'e'),(2.228, 'f'), (2.015, 'g'), (6.094, 'h'),
(6.966, 'i'), (0.153, 'j'), (0.747, 'k'), (4.025, 'l'),
(2.406, 'm'), (6.749, 'n'), (7.507, 'o'), (1.929, 'p'),
(0.095, 'q'), (5.987, 'r'), (6.327, 's'), (9.056, 't'),
(2.758, 'u'), (1.037, 'v'), (2.365, 'w'), (0.150, 'x'),
(1.974, 'y'), (0.074, 'z') ]
def create_tree(frequencies):
p = queue.PriorityQueue()
for value in frequencies: # 1. Create a leaf node for each symbol
p.put(value) # and add it to the priority queue
while p.qsize() > 1: # 2. While there is more than one node
l, r = p.get(), p.get() # 2a. remove two highest nodes
node = HuffmanNode(l, r) # 2b. create internal node with children
p.put((l[0]+r[0], node)) # 2c. add new node to queue
return p.get() # 3. tree is complete - return root node
node = create_tree(freq)
print(node)
# Recursively walk the tree down to the leaves,
# assigning a code value to each symbol
def walk_tree(node, prefix="", code={}):
return(code)
code = walk_tree(node)
for i in sorted(freq, reverse=True):
print(i[1], '{:6.2f}'.format(i[0]), code[i[1]])
在字母表数据上运行时,生成的霍夫曼代码为:
e 12.70 100
t 9.06 000
a 8.17 1110
o 7.51 1101
i 6.97 1011
n 6.75 1010
s 6.33 0111
h 6.09 0110
r 5.99 0101
d 4.25 11111
l 4.03 11110
c 2.78 01001
u 2.76 01000
m 2.41 00111
w 2.37 00110
f 2.23 00100
g 2.02 110011
y 1.97 110010
p 1.93 110001
b 1.49 110000
v 1.04 001010
k 0.75 0010111
j 0.15 001011011
x 0.15 001011010
q 0.10 001011001
z 0.07 001011000
关于python - 如何为霍夫曼编码和解码创建一棵树?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11587044/