39 lines
924 B
Text
39 lines
924 B
Text
|
T Element
|
|||
|
|
Int weight
|
|||
|
|
[(Char, String)] symbols
|
|||
|
|
|
|||
|
|
F (weight, symbols)
|
|||
|
|
.weight = weight
|
|||
|
|
.symbols = symbols
|
|||
|
|
|
|||
|
|
F <(other)
|
|||
|
|
R (.weight, .symbols) < (other.weight, other.symbols)
|
|||
|
|
|
|||
|
|
F encode(symb2freq)
|
|||
|
|
V heap = symb2freq.map((sym, wt) -> Element(wt, [(sym, ‘’)]))
|
|||
|
|
minheap:heapify(&heap)
|
|||
|
|
|
|||
|
|
L heap.len > 1
|
|||
|
|
V lo = minheap:pop(&heap)
|
|||
|
|
V hi = minheap:pop(&heap)
|
|||
|
|
|
|||
|
|
L(&sym) lo.symbols
|
|||
|
|
sym[1] = ‘0’sym[1]
|
|||
|
|
|
|||
|
|
L(&sym) hi.symbols
|
|||
|
|
sym[1] = ‘1’sym[1]
|
|||
|
|
|
|||
|
|
minheap:push(&heap, Element(lo.weight + hi.weight, lo.symbols [+] hi.symbols))
|
|||
|
|
|
|||
|
|
R sorted(minheap:pop(&heap).symbols, key' p -> (p[1].len, p))
|
|||
|
|
|
|||
|
|
V txt = ‘this is an example for huffman encoding’
|
|||
|
|
V symb2freq = DefaultDict[Char, Int]()
|
|||
|
|
L(ch) txt
|
|||
|
|
symb2freq[ch]++
|
|||
|
|
|
|||
|
|
V huff = encode(symb2freq)
|
|||
|
|
print("Symbol\tWeight\tHuffman Code")
|
|||
|
|
L(p) huff
|
|||
|
|
print("#.\t#.\t#.".format(p[0], symb2freq[p[0]], p[1]))
|