Python, SUM von mehrfach

Question

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

---

jetzt Meine Ausgabe ist:

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

ich brauche:

Output gleiche wie jetzt, aber auch SUMME = 2 * 0,124167 + 3 * 0,0969225 +3 * 0,0820011 + 2 * 0,0768052 + 2 * 0,0368052 ... = ?; Soo in diesem Fall, SUM = 1.;

erste Anzahl von len (prefix) und zweite Anzahl von exampleData

eine Lösung?

---

---

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) 

me Dieses

die geben Fehler

Answer 1

Ich glaube, ich sehe, was Sie nach. Zuerst fand ich es nützlich, um Ihre Frequenztabelle in ein Wörterbuch zu konvertieren, also:

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

Dann können Sie diese an die Funktion übergeben, die den Baum-Traversal ausdruckt. Ich veränderte Ihre Funktion dieses Frequenzdaten zu verwenden und die Summe zu verfolgen:

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) 

Dann können Sie einfach es so nennen in Ihre Hauptfunktion:

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

Dieses eine Summe von 0,9470124 gibt, die ich denke, stimmt mit Ihren Beispieldaten.

Der vollständige Code wird:

#!/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