12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667 |
- #!/usr/bin/ruby
- # https://rosettacode.org/wiki/huffman_coding
- func walk(Hash n, String s, Hash h) {
- if (n.has(:a)) {
- h{n{:a}} = s
- printf("%3s: %s\n", n{:a}, s)
- return nil
- }
- walk(n{:0}, s+'0', h) if n.has(:0)
- walk(n{:1}, s+'1', h) if n.has(:1)
- }
- func make_tree(Array bytes) {
- var nodes = bytes.freq.sort.map_2d { |b,f|
- Hash(a => b, freq => f)
- }
- loop {
- nodes.sort_by!{|h| h{:freq} }
- var(x, y) = (nodes.shift, nodes.shift)
- if (defined(x)) {
- if (defined(y)) {
- nodes << Hash(:0 => x, :1 => y, :freq => x{:freq}+y{:freq})
- }
- else {
- nodes << Hash(:0 => x, :freq => x{:freq})
- }
- }
- nodes.len > 1 || break
- }
- var n = nodes.first
- walk(n, '', n{:tree} = Hash())
- return n
- }
- func encode(bytes, t) {
- t = t{:tree}
- bytes.map { t{_} }.join
- }
- func decode(enc, tree) {
- var out = []
- var prefix = ''
- enc.each {|bit|
- prefix += bit
- if (tree.has(prefix)) {
- out << tree{prefix}
- prefix = ''
- }
- }
- return out
- }
- var text = "this is an example for huffman encoding"
- var bytes = text.bytes
- var tree = make_tree(bytes)
- var enc = encode(bytes, tree)
- say enc
- say decode(enc, tree{:tree}.flip).decode('utf8')
|