1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556 |
- #!/usr/bin/ruby
- func walk(n, s, h) {
- n.exists('a') && (
- h{n{'a'}} = s;
- say "#{n{'a'}}: #{s}";
- return();
- );
- walk(n{'0'}, s+'0', h);
- walk(n{'1'}, s+'1', h);
- }
- func make_tree(text) {
- var letters = Hash.new;
- text.each { |c| letters{c} \\= 0 ++ };
- var nodes = letters.keys.map { |l|
- Hash.new('a' => l, 'freq' => letters{l})
- };
- var n = Hash.new;
- while (nodes.sort!{|a,b| a{'freq'} <=> b{'freq'} }.len > 1) {
- n = Hash.new('0' => nodes.shift, '1' => nodes.shift);
- n{'freq'} = (n{'0'}{'freq'} + n{'1'}{'freq'});
- nodes.append(n);
- }
- walk(n, '', n{'tree'} = Hash.new);
- return n;
- }
- func encode(s, t) {
- t = t{'tree'};
- s.split(1).join('' => {|c| t{c}});
- }
- func decode (enc, tree) {
- var n = tree;
- var out = '';
- enc.each {|bit|
- n = n{bit};
- n.has_key('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);
|