Download code

From LiteratePrograms

Jump to: navigation, search

Back to Huffman_coding_(Python)

Download for Windows: single file, zip

Download for UNIX: single file, zip, tar.gz, tar.bz2

huffmanCode.py

 1 # Copyright (c) 2010 the authors listed at the following URL, and/or
 2 # the authors of referenced articles or incorporated external code:
 3 # http://en.literateprograms.org/Huffman_coding_(Python)?action=history&offset=20081223225116
 4 # 
 5 # Permission is hereby granted, free of charge, to any person obtaining
 6 # a copy of this software and associated documentation files (the
 7 # "Software"), to deal in the Software without restriction, including
 8 # without limitation the rights to use, copy, modify, merge, publish,
 9 # distribute, sublicense, and/or sell copies of the Software, and to
10 # permit persons to whom the Software is furnished to do so, subject to
11 # the following conditions:
12 # 
13 # The above copyright notice and this permission notice shall be
14 # included in all copies or substantial portions of the Software.
15 # 
16 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18 # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
19 # IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
20 # CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
21 # TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
22 # SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
23 # 
24 # Retrieved from: http://en.literateprograms.org/Huffman_coding_(Python)?oldid=15672
25 
26 import heapq
27 
28 def makeHuffTree(symbolTupleList):
29    trees = list(symbolTupleList)
30 
31    heapq.heapify(trees)
32    while len(trees) > 1:
33       childR, childL = heapq.heappop(trees), heapq.heappop(trees)
34       parent = (childL[0] + childR[0], childL, childR)
35       heapq.heappush(trees, parent)
36 
37    return trees[0]
38 
39 def printHuffTree(huffTree, prefix = ''):
40    if len(huffTree) == 2:
41       print huffTree[1], prefix
42 
43    else:
44       printHuffTree(huffTree[1], prefix + '0')
45       printHuffTree(huffTree[2], prefix + '1')
46 
47 exampleData = [
48   (0.124167  , 'e'),   
49   (0.0969225 , 't'),   
50   (0.0820011 , 'a'),   
51   (0.0768052 , 'i'),   
52   (0.0764055 , 'n'),   
53   (0.0714095 , 'o'),   
54   (0.0706768 , 's'),   
55   (0.0668132 , 'r'),   
56   (0.0448308 , 'l'),   
57   (0.0363709 , 'd'),   
58   (0.0350386 , 'h'),   
59   (0.0344391 , 'c'),   
60   (0.028777  , 'u'),   
61   (0.0281775 , 'm'),   
62   (0.0235145 , 'f'),   
63   (0.0203171 , 'p'),   
64   (0.0189182 , 'y'),   
65   (0.0181188 , 'g'),   
66   (0.0135225 , 'w'),   
67   (0.0124567 , 'v'),   
68   (0.0106581 , 'b'),   
69   (0.00393019, 'k'),   
70   (0.00219824, 'x'),   
71   (0.0019984 , 'j'),   
72   (0.0009325 , 'q'),   
73   (0.000599  , 'z')   
74 ]
75 
76 
77 if __name__ == '__main__':
78    huffTree = makeHuffTree(exampleData)
79    printHuffTree(huffTree)
80


Retrieved from "http://en.literateprograms.org/Special:Downloadcode"
Views
Personal tools