huffman.rb

class Node
    attr_accessor :name, :prob, :children, :code

    def initialize name, prob, children = [], code = nil
        @name = name
        @prob = prob
        @children = children
        @code = code
    end

end


def make_bin_tree queue
    while queue.size > 1
        queue.sort_by!{|e| -e.prob}
        right = queue.pop
        left = queue.pop
        queue.push(Node.new("(#{left.name},#{right.name})", left.prob + right.prob, [left, right]) )
    end
    queue
end

def huffmanize tree
    list = []

    dfs = -> (sub_tree, code, depth) {
        if sub_tree.children == []
            sub_tree.code = code
            list << sub_tree
        else
            sub_tree.children.each_with_index{ |e, i|
                dfs.(e, code + i.to_s , depth + 1)
            }
        end
    }
    dfs.(tree[0], "", 0)

    list.sort_by{|e| e.name}
end

def print_huffman huf
    huf.each{ |e|
        puts "#{e.name} : #{e.code} (#{e.prob})"
    }
end

def mean_code_length huf
    sum = 0
    huf.each{ |e|
        sum += e.code.size * e.prob
    }
    sum
end


def generate_run length, zero_prob, one_prob
    q = []
    (0..length-1).each{ |e|
        q << Node.new( e > 3 ? "0^#{e} 1" : "0" * e + "1", one_prob * zero_prob ** e)
    }
    q << Node.new("0^#{length}", zero_prob ** length)
    q
end

def ran_mean_length length, zero_prob, one_prob
    sum = 0
    (0..length-1).each{ |e|
        sum += (e + 1)  * one_prob * zero_prob ** e
    }
    sum += length * zero_prob ** length

end

p_4_5_i.rb

arr = [0.950, 0.030, 0.015, 0.005]

q = []
arr.each_with_index{|e, i|
    q << Node.new(i.to_s, e)
}

tree = make_bin_tree q
p tree[0].name
huf = huffmanize tree
print_huffman huf
p mean_code_length(huf)

p_4_5_ii

a = 0.950

b = 0.030
c = 0.015
d = 0.005
q = []
sum = 0

5.times{ |i|
    q << Node.new("A" * i + "B", a ** i * b)
    sum += (i + 1) * a ** i * b
    q << Node.new("A" * i + "C", a ** i * c)
    sum += (i + 1) * a ** i * c
    q << Node.new("A" * i + "D", a ** i * d)
    sum += (i + 1) * a ** i * d
}
q << Node.new("AAAAA", a ** 5)
sum += a ** 5 * 5

p q

tree = make_bin_tree q
p tree[0].name
huf = huffmanize tree
print_huffman huf
p mean_code_length(huf)
p sum
p mean_code_length(huf)  / sum

p_4_5_iii

q = generate_run 15, 0.9725, 0.0275

tree = make_bin_tree q
p tree[0].name
huf = huffmanize tree
print_huffman huf
p mean_code_length(huf)
p mean_code_length(huf)  / ran_mean_length(15, 0.9725, 0.0275)
p mean_code_length(huf)  / ran_mean_length(15, 0.9725, 0.0275) * 2