Huffman encoding

huffman_encoding.rb

# Huffman encoding. Just for fun, I didn't verify that it is actually correct
# Glanced at the trees in this document to get the idea, then just rolled with what made sense
# https://www.siggraph.org/education/materials/HyperGraph/video/mpeg/mpegfaq/huffman_tutorial.html

class Huffman
  def self.for_string(string)
    freqs = string.chars.group_by(&:itself).map { |c, cs| Tree::Leaf.new cs.length, c }
    until freqs.one?
      freqs.sort!
      freqs.unshift Tree::Node.new(freqs.shift, freqs.shift)
    end
    new freqs.first
  end

  attr_reader :tree
  def initialize(tree)
    @tree = tree
  end
  
  def paths
    @paths ||= tree.paths("")
  end

  def encode(string)
    string.chars.inject 0 do |bits, char|
      paths.fetch(char)
           .reverse.each_char
           .inject(bits) { |bits, bit| bits<<1|bit.to_i }
    end    
  end

  def decode(encoded)
    decoded = ""
    until encoded.zero?
      path = tree
      until path.leaf?
        path = path.child_for_bit encoded[0]
        encoded >>= 1
      end
      decoded.insert 0, path.string
    end
    decoded
  end
end

class Huffman
  Tree = Module.new

  module Tree::Compare
    include ::Comparable
    def <=>(other)
      [frequency<=>other.frequency, num_children<=>other.num_children].find { |n| n!=0 } || 0
    end
  end

  Tree::Leaf = Struct.new :frequency, :string do
    include Tree::Compare
    def num_children()  0                    end
    def paths(previous) {string => previous} end
    def leaf?()         true                 end
  end

  Tree::Node = Struct.new :frequency, :num_children, :left, :right do
    include Tree::Compare
    def initialize(left, right)
      super left.frequency+right.frequency,
            2+left.num_children+right.num_children,
            left,
            right
    end
    def paths(previous)    left.paths(previous+"0").merge right.paths(previous+"1") end
    def leaf?()            false                                                    end
    def child_for_bit(bit) [left, right].fetch(bit)                                 end
  end
end

# =====  Example  =====
original = 'require"io/console";extend(self.class.const_get("\115ath"));puts"\e[?25l\e[?1000h";at_exit{puts"\e[?25h\e[?1000l"};x=y=ax=ay=0;dy=dx=0.5;h,w,e,fg=*$>.winsize,nil,7;r=->n,v{i=(3*tanh(v)).to_i+2;"\e[38;5;16m#{[196,208,184,38,21].map{|n|"\e[48;5;#{n}m"}.map.with_index{|c,j|c+(j==i&&n||?-)}*""}\e[40;37m\x20%6.2f"%v};self.class.const_get("\x54hread").new{$stdin.raw{(case$stdin.readpartial(20);when"\e[\x41";ay-=0.1;when"\e[\x42";ay+=0.1;when"\e[\x43";ax+=0.1;when"\e[\x44";ax-=0.1;when"\3";e=1;when/\e\[\115\x20(.)(.)/;dx,dy,x,y=0,0,*[$1,$2].map{|n|n.force_encoding(128.chr.encoding).ord-32};when/^\d/;fg=$&;end)until(e)}};(sleep(0.05);dx+=ax*0.1;dy+=ay*0.1;x+=dx/2;y+=dy/2;y,dy=y<1?[1,-dy*0.8]:(y>h)?[h,-dy*0.8]:[y,dy];x,dx=x<1?[1,-dx*0.8]:(x+1>w)?[w-2,-dx*0.8]:[x,dx];$><<"\e[40m\e[\x48\e[2\112#{r[?x,dx]}\x20x-velocity\r\n#{r[?y,dy]}\x20y-velocity\r\n#{r[?x,ax]}\x20x-accel\r\n#{r[?y,ay]}\x20y-accel\e[#{y.to_i};#{x.to_i}\x48\e[4#{fg}m\x20\x20")until(e)'
huff     = Huffman.for_string original.freeze
encoded  = huff.encode original   # => 37814598481318934198971053555134893719965913466478288462853056587140232332238408224670865004826633061907787689906537971634391724014402682155087173710753185999169658245919842651385833890498474895365172438386428968104678006898504114697300090712588080363269056636511047687554805890303544426194193253245364290874327443948247692810631643255440034789958978995865408776766243264266452145910923086173...

# About 30% smaller, saves 295 bytes, is decoded correctly
original.size                      # => 954
encoded.size                       # => 659
original.size - encoded.size       # => 295
encoded.size / original.size.to_f  # => 0.6907756813417191
huff.decode(encoded) == original   # => true