Huffman generator example for Ruby and Crystal.

huffman.rb.cr

# Huffman Tree generator for Ruby and Crystal
# @faustinoaq
# Jan, 2017

class Element

  def initialize(sym = '\0', fr = 1.0)
    @ch = nil
    if sym != '\0'
    @ch = [Element.new]
    if ch = @ch
      ch.clear
      @ch = ch
    end
    end
    @sym = sym
    @fr = fr
  end

  def +(e)
    fr = @fr + e.fr
    Element.new('*', fr)
  end

  def fr
    @fr
  end

  def ch
    @ch
  end

  def ch=(other)
    @ch = other
  end

  def sym
    @sym
  end
end

def huffman(elements)
  while elements.size > 2
    elements = elements.sort_by do |e|
      e.fr
    end
    aux = elements[0] + elements[1]
    if ch = aux.ch
      ch << elements[0]
      ch << elements[1]
      aux.ch = ch
    end
    elements.delete_at(0)
    elements.delete_at(0)
    elements = [aux] + elements
  end
  elements
end

BIN  = [1]
BIN.clear
CODE = {'a' => "a"}
CODE.clear

def encode(niltree)
  if tree = niltree
  tree.each_with_index do |e, i|
    BIN << i
    if ch = e.ch
    if ch.empty?
      CODE[e.sym] = BIN.join
      BIN.pop
    else
      encode(e.ch)
    end
    end
  end
  end
  BIN.pop unless BIN.empty?
end

text = %(Premature optimization is the root of all evil.)
chars = { 'a' => 1.0 }
chars.clear
text.each_char do |c|
  begin
    chars[c] += 1.0
  rescue
    chars[c] = 1.0
  end
end

total = chars.values.sum
chars.each do |k, v|
  chars[k] = v/total
end

class Par
  def initialize(k = 'a', v = 1.0)
    @k = k
    @v = v
  end

  def k
    @k
  end

  def v
    @v
  end
end
chars.map do |k, v|
  Par.new(k, v)
end.sort_by do |e|
  e.v
end.each do |e|
  p [e.k, e.v]
end

elements = [Element.new('a', 1.0)]
elements.clear
chars.each do |k, v|
  elements << Element.new(k, v)
end
p elements
tree = huffman(elements)
# p tree
encode(tree)
p CODE

encoded = ""
text.each_char do |c|
  encoded += CODE[c]
end
p encoded

bincode = CODE.invert
limit = bincode.keys.map do |k|
  k.size
end.max
part = decoded = ""
encoded.each_char do |c|
  part += c
  begin
    decoded += bincode[part]
    part = ""
  rescue
    if part.size > limit
      raise "Invalid part of CODE"
    end
  end
end
p decoded