Python, SUM de multiplier

Question

Mon code:

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) 

---

Ma sortie est maintenant:

e 00 2 
i 010 3 
h 011 3 
t 10 2 
a 11 2 

J'ai besoin:

sortie comme maintenant, mais même SUM = 2 * 0,124167 + 3 * 0,0969225 +3 * 0,0820011 + 2 * 0,0768052 + 2 * 0,0368052 ... = ?; soo dans ce cas, SUM = 1.;

premier numéro est de len (préfixe) et le second nombre est de exampleData

Toute solution?

---

---

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) 

Ce

de me donner l'erreur

Answer 1

Je pense que je vois ce que vous êtes après. Tout d'abord, je l'ai trouvé utile de convertir votre table de fréquence à un dictionnaire, ainsi:

freqs = dict([(b,a) for (a,b) in exampleData]) 

Ensuite, vous pouvez passer ce à la fonction qui imprime le traversal des arbres. J'ai modifié votre fonction à utiliser ces données de fréquence et de suivre la somme:

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) 

Ensuite, vous pouvez simplement l'appeler comme ça dans votre fonction principale:

huffTree = makeHuffTree(exampleData) 
tot = printHuffTree2(freqs, huffTree) 
print 'Sum = ', tot 

Cela donne une somme de 0,9470124 que je pense est correct compte tenu de vos données d'exemple.

Le code complet devient:

#!/usr/bin/env python 

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') 

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) 

def buildHuffTree(huffTree, prefix = ''): 
    if len(huffTree) == 2: 
     return (huffTree[1], prefix, len(prefix)) 
    else: 
     return (buildHuffTree(huffTree[1], prefix + '0'), 
       buildHuffTree(huffTree[2], prefix + '1')) 

if __name__ == '__main__': 

    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]) 

    huffTree = makeHuffTree(exampleData) 
    tot = printHuffTree2(freqs, huffTree) 
    print 'Sum = ', tot