huffman_coding.sf

#!/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')