-
Notifications
You must be signed in to change notification settings - Fork 0
/
huffman.coffee
87 lines (76 loc) · 1.88 KB
/
huffman.coffee
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
huffman_encoding_table = (counts) ->
# counts is a hash where keys are characters and
# values are frequencies;
# return a hash where keys are codes and values
# are characters
build_huffman_tree = ->
# returns a Huffman tree. Each node has
# cnt: total frequency of all chars in subtree
# c: character to be encoded (leafs only)
# children: children nodes (branches only)
q = min_queue()
for c, cnt of counts
q.enqueue cnt,
cnt: cnt
c: c
while q.size() >= 2
a = q.dequeue()
b = q.dequeue()
cnt = a.cnt + b.cnt
node =
cnt: cnt
children: [a, b]
q.enqueue cnt, node
root = q.dequeue()
root = build_huffman_tree()
codes = {}
encode = (node, code) ->
if node.c?
codes[code] = node.c
else
encode node.children[0], code + "0"
encode node.children[1], code + "1"
encode(root, "")
codes
min_queue = ->
# This is very non-optimized; you could use a binary heap for better
# performance. Items with smaller priority get dequeued first.
arr = []
enqueue: (priority, data) ->
i = 0
while i < arr.length
if priority < arr[i].priority
break
i += 1
arr.splice i, 0,
priority: priority
data: data
dequeue: ->
arr.shift().data
size: -> arr.length
_internal: ->
arr
freq_count = (s) ->
cnts = {}
for c in s
cnts[c] ?= 0
cnts[c] += 1
cnts
rpad = (s, n) ->
while s.length < n
s += ' '
s
examples = [
"this is an example for huffman encoding"
"abcd"
"abbccccddddddddeeeeeeeee"
]
for s in examples
console.log "---- #{s}"
counts = freq_count(s)
huffman_table = huffman_encoding_table(counts)
codes = (code for code of huffman_table).sort()
for code in codes
c = huffman_table[code]
console.log "#{rpad(code, 5)}: #{c} (#{counts[c]})"
console.log()