Python, сумма умножения

Question

Мой код:

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)

---

Мой вывод сейчас:

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

Мне нужно:

Вывод такой же, каксейчас, но даже SUM = 2 * 0,124167 + 3 * 0,0969225 +3 * 0,0820011 + 2 * 0,07808052 + 2 * 0,0368052 ... = ?;в этом случае SUM = 1.0123256;

первое число от len (префикс) , а второе число от exampleData

Есть решение?

---

---

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)

Это дает мне ошибку

Answer 1

Я думаю, что вижу, что вы после. Во-первых, я нашел полезным преобразовать вашу таблицу частот в словарь, таким образом:

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

Затем вы можете передать это функции, которая распечатывает обход дерева. Я изменил вашу функцию, чтобы использовать эти данные частоты и отслеживать сумму:

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)

Тогда вы можете просто вызвать его в своей основной функции:

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

Это дает сумму 0,9470124, которую я считаю правильной, учитывая ваши данные в качестве примера.

Полный код становится:

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