I have tried to use BinaryHeap of Phobos2. As a warming up exercise I am
translating this little Python program to D2 using Phobos2 only, a very basic
Huffman encoder:
from heapq import heappush, heappop, heapify
from collections import defaultdict
def encode(freqs):
"""Huffman encode the given dict mapping symbols to weights"""
heap = [[float(wt), [sym, '']] for sym,wt in freqs.iteritems()]
heapify(heap)
while len(heap) > 1:
lo = heappop(heap)
hi = heappop(heap)
for i in lo[1:]:
i[1] = '0' + i[1]
for i in hi[1:]:
i[1] = '1' + i[1]
lohi = [lo[0] + hi[0]] + lo[1:] + hi[1:]
heappush(heap, lohi)
return sorted(heappop(heap)[1:], key=lambda x: (len(x[-1]), x))
astring = "this is an example for huffman encoding"
freqs = defaultdict(int)
for c in astring:
freqs[c] += 1
huff = encode(freqs)
print "SYMBOL\tWEIGHT\tHUFFMAN CODE"
for h in huff:
print "'%s'\t%s\t%s" % (h[0], freqs[h[0]], h[1])
That outputs is:
SYMBOL WEIGHT HUFFMAN CODE
' ' 6 101
'n' 4 010
'a' 3 1001
'e' 3 1100
'f' 3 1101
'h' 2 0001
'i' 3 1110
'm' 2 0010
'o' 2 0011
's' 2 0111
'g' 1 00000
'l' 1 00001
'p' 1 01100
'r' 1 01101
't' 1 10000
'u' 1 10001
'x' 1 11110
'c' 1 111110
'd' 1 111111
(Note that the python heap isn't object oriented, I'd like to write it in C for
Python2.6, in the meantime if you need OOP you can use
http://code.activestate.com/recipes/502295/ ).
Regarding BinaryHeap of Phobos2:
This may be a dumb question: How do you push/add an item to such heap (to
translate the heappush)? I have found no info in the docs.
I suggest to add one or two examples of the acquire(Range r) method, because I
don't understand its purpose.
I suggest to add to the std.algorithm module something like:
BinaryHeap!(Range) binaryHeap(Range)(Range arr) {
return BinaryHeap!(Range)(arr);
}
Otherwise most of the times you have to use:
auto heap = BinaryHeap!(typeof(arr))(arr);
(In the following few months I'll probably post many more notes about Phobos2).
Bye,
bearophile
