55 lines
1.0 KiB
Plaintext
55 lines
1.0 KiB
Plaintext
func walk(n, s, h) {
|
|
if (n.contains(:a)) {
|
|
h{n{:a}} = s
|
|
say "#{n{:a}}: #{s}"
|
|
return nil
|
|
}
|
|
walk(n{:0}, s+'0', h)
|
|
walk(n{:1}, s+'1', h)
|
|
}
|
|
|
|
func make_tree(text) {
|
|
var letters = Hash()
|
|
text.each { |c| letters{c} := 0 ++ }
|
|
var nodes = letters.keys.map { |l|
|
|
Hash(a => l, freq => letters{l})
|
|
}
|
|
|
|
var n = Hash()
|
|
while (nodes.sort_by!{|c| c{:freq} }.len > 1) {
|
|
n = Hash(:0 => nodes.shift, :1 => nodes.shift)
|
|
n{:freq} = (n{:0}{:freq} + n{:1}{:freq})
|
|
nodes.append(n)
|
|
}
|
|
|
|
walk(n, "", n{:tree} = Hash())
|
|
return n
|
|
}
|
|
|
|
func encode(s, t) {
|
|
t = t{:tree}
|
|
s.chars.map{|c| t{c} }.join
|
|
}
|
|
|
|
func decode (enc, tree) {
|
|
var n = tree
|
|
var out = ""
|
|
|
|
enc.each {|bit|
|
|
n = n{bit}
|
|
if (n.contains(:a)) {
|
|
out += n{:a}
|
|
n = tree
|
|
}
|
|
}
|
|
|
|
return out
|
|
}
|
|
|
|
var text = "this is an example for huffman encoding"
|
|
var tree = make_tree(text)
|
|
var enc = encode(text, tree)
|
|
|
|
say enc
|
|
say decode(enc, tree)
|