class Huffman

Public Class Methods

decode(encoded_text, code_table) click to toggle source

# File lib/huffman.rb, line 53
def self.decode(encoded_text, code_table)
  text = []
  code_table = code_table.invert
  previous = ''
  encoded_text.each_char do |char|
    if code_table[previous + char]
      text << code_table[previous + char]
      previous = ''
    else
      previous += char
    end
  end
  text.join
end

encode(text, frequencies=nil) click to toggle source

frequencies should be a hash containing the occuring letters of the text and their corresponding frequency i.e. {‘a’ => 5, ‘b’ => 3}

# File lib/huffman.rb, line 45
def self.encode(text, frequencies=nil)
  frequencies = get_frequencies(text) unless frequencies
  tree = build_tree(frequencies)
  code_table = {}
  frequencies.size > 1 ? tree.traverse('', code_table) : code_table = {frequencies.keys[0] => '0'}
  {encoded_text: text.chars.map{|char| code_table[char]}.join, code_table: code_table}
end

Private Class Methods

build_tree(frequencies) click to toggle source

# File lib/huffman.rb, line 77
def self.build_tree(frequencies)
  nodes = []
  frequencies.each_pair do |letter, frequency|
    nodes << Node.new(letter, frequency)
  end

  order = 1
  while nodes.length > 1 do
    nodes.sort!
    left = nodes.shift
    right = nodes.shift
    combined = Node.new('', left.weight + right.weight, order, left, right)
    nodes << combined
    order += 1
  end
  nodes.shift
end

get_frequencies(text) click to toggle source

# File lib/huffman.rb, line 69
def self.get_frequencies(text)
  frequencies = Hash.new(0)
  text.each_char do |char|
    frequencies[char] += 1
  end
  frequencies
end