我的代码:
import heapq
def makeHuffTree(symbolTupleList):
trees = list(symbolTupleList)
heapq.heapify(trees)
while len(trees) > 1:
childR, childL = heapq.heappop(trees), heapq.heappop(trees)
parent = (childL[0] + childR[0], childL, childR)
heapq.heappush(trees, parent)
return trees[0]
def printHuffTree(huffTree, prefix = ''):
if len(huffTree) == 2:
print huffTree[1], prefix, len(prefix) <--------------------------
else:
printHuffTree(huffTree[1], prefix + '0')
printHuffTree(huffTree[2], prefix + '1')
exampleData = [ <-------------------------------
(0.124167 , 'e'),
(0.0969225 , 't'),
(0.0820011 , 'a'),
(0.0768052 , 'i'),
(0.0368052 , 'h')
]
""" some test code
exampleData[i] = exampleData[i] + (len(prefix),)
sum(i[1]*i[0] for i in exampleData) <-this is wrong...
"""
if __name__ == '__main__':
huffTree = makeHuffTree(exampleData)
printHuffTree(huffTree)
我现在的输出是:
^{pr2}$我需要:
输出与现在相同,但甚至 和=2*0.124167+3*0.0969225+3*0.0820011+2*0.0768052+2*0.0368052…=?; 在本例中,SUM=1.0123256
第一个数字来自len(前缀),第二个数字来自示例数据
有什么解决办法吗?在
EDIT2:
import heapq
def makeHuffTree(symbolTupleList):
trees = list(symbolTupleList)
heapq.heapify(trees)
while len(trees) > 1:
childR, childL = heapq.heappop(trees), heapq.heappop(trees)
parent = (childL[0] + childR[0], childL, childR)
heapq.heappush(trees, parent)
return trees[0]
def printHuffTree2(freqs, huffTree, prefix = ''):
if len(huffTree) == 2:
letter = huffTree[1]
val = len(prefix)*freqs[letter]
print '%s: %s\t%u * %f = %f' % \
(huffTree[1], prefix, len(prefix), freqs[letter], val)
return val
else:
lhs = printHuffTree2(freqs, huffTree[1], prefix + '0')
rhs = printHuffTree2(freqs, huffTree[2], prefix + '1')
return (lhs+rhs)
exampleData = [
(0.124167 , 'e'),
(0.0969225 , 't'),
(0.0820011 , 'a'),
(0.0768052 , 'i'),
(0.0368052 , 'h')
]
freqs = dict([(b,a) for (a,b) in exampleData])
"""
exampleData[i] = exampleData[i] + (len(prefix),)
sum(i[1]*i[0] for i in exampleData)
"""
if __name__ == '__main__':
huffTree = makeHuffTree(exampleData)
printHuffTree2(huffTree)
这给我错误的
我想我知道你在找什么了。首先,我发现将频率表转换为字典非常有用,因此:
然后您可以将其传递给打印出树遍历的函数。我修改了您的函数以使用此频率数据并跟踪总和:
^{pr2}$然后在主函数中可以这样调用它:
这给出了一个0.9470124的总和,我认为根据您的示例数据,这是正确的。在
完整代码变为:
相关问题 更多 >
编程相关推荐