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