1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283 |
- #!/usr/bin/ruby
- # Implementation of the Adaptive Huffman Coding.
- # See also:
- # https://rosettacode.org/wiki/huffman_coding
- func walk(Hash n, String s, Hash h) {
- if (n.has(:a)) {
- h{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 mktree_from_freq(Hash freqs) {
- var nodes = freqs.sort.flip.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(Array bytes, Array alphabet) {
- var freq = alphabet.freq
- var enc = []
- bytes.each {|b|
- var tree = mktree_from_freq(freq)
- ++freq{b}
- enc << tree{:tree}{b}
- }
- return enc.join
- }
- func decode(String enc, Array alphabet) {
- var out = []
- var prefix = ''
- var freq = alphabet.freq
- var tree = mktree_from_freq(freq){:tree}.flip
- enc.each {|bit|
- prefix += bit
- if (tree.has(prefix)) {
- out << tree{prefix}
- ++freq{tree{prefix}}
- tree = mktree_from_freq(freq){:tree}.flip
- prefix = ''
- }
- }
- return out
- }
- var text = "this is an example for huffman encoding"
- var bytes = text.bytes
- say var enc = encode(bytes, bytes.uniq)
- say var dec = decode(enc, bytes.uniq).pack('C*')
- assert_eq(dec, text)
|