Fill out code in the given modules to do a Huffman encoding writing in RUBY prog
ID: 3920147 • Letter: F
Question
Fill out code in the given modules to do a Huffman encoding writing in RUBY programing language. Every linked structure must be started from scratch.
Modules
Module MyOrderedItem defines an abstract class called OrderedItem. Use the techniques discussed in the notes to define an 'abstract' class in ruby. This abstract class is used to ensure sub-classes define two functions: compareTo and to_s.
Module MyOccurrenceList defines a data structure called OccurrrenceList. As in the previous assignments, all your data structures are linked structures that you create on your own. The nodes contain an item and a count, as well as a link to the next node. Provide an increment method in the Node class so that the count in a node may be easily incremented by one.
The occurrence list itself should support the add method, which either adds a new item to the head of the list (with a count of 1), or increments the count of the existing item. You may want to write a find method to support this operation, but you don't have to. Also write the to_s method, which returns a string containing the contents of the list (items and counts), one item per line.
Module MyPriorityQueue defines a data structure called PriorityQueue. Since a priority queue must have some means of ordering item by priority, ensure that only OrderedItem objects are added to the data structure (use the kind_of? method to check that items added to the priority queue are OrderedItems). Your data structure must support an insert method, a get_first method and an empty? method.
Module MyBST defines a data structure called BST (a binary search tree). This structure also must be able to order items, but use Duck Typing this time to ensure that items can respond to the compareTo message (use respond_to?). Your BST will use the simple insertion technique of simply following a path from the root to an empty subtree, and inserting a new node at that point (we are not concerned about making a balanced tree). As you have probably done in Java, have a public insert method, which calls a private, recursive insert to actually perform the insertion. Provide a to_s method that performs an inorder traversal of the tree (again using a private, recursive method) and returns the string.
Since we are inserting BST objects into a PriorityQueue when performing Huffman encoding, the BST class must extend OrderedItem. Thus, you must also provide a compareTo method (compare the items in the roots of the trees). Main program The main program will read input from a file (this is included in the free code). It then produces a Huffman Tree, and uses that to produce an encoding of the original input. The encoding is actually a sequence of '0' and '1' characters, NOT a binary file. It then prints the original string and the 'encoded' version.
A3.rb
require_relative "MyOccurrenceList"
include MyOccurrenceList
require_relative "MyPriorityQueue"
include MyPriorityQueue
require_relative "MyBST"
include MyBST
#......................................................................buildOccurrenceList
def buildOccurrenceList(inFile)
result = OccurrenceList.new
File.open(inFile) do |fb|
while line = fb.gets # gets returns nil at end-of-file
line.chomp! # remove the newline character
for i in 0...line.size
result.add(line[i])
end
end# while
end# File.open
return result
end# buildOccurrenceList
#..................................................................................getText
def getText(inFile)
result = ''
File.open(inFile) do |fb|
while line = fb.gets # gets returns nil at end-of-file
line.chomp! # remove the newline character
result += line
end# while
end# File.open
return result
end# getText
#.....................................................................................main
def main
myList = buildOccurrenceList('smalldata.txt')
puts "The occurrence list " + myList.to_s
toEncode = getText('smalldata.txt')
puts 'End of processing'
end# main
main
MyOccurrenceList.rb
#.........................................................................MyOccurrenceList
module MyOccurrenceList
end# module MyOccurrenceList
# un-comment if your module is in a separate file
#require_relative "MyOccurrenceList"
include MyOccurrenceList
#.....................................................................................main
def testOL
inStr = 'AABBCDEFFG'
theList = OccurrenceList.new
for i in 0...inStr.size do
theList.add(inStr[i])
end# do
puts theList.to_s
puts 'End of processing'
end# testOL
MyPriorityQueue.rb
require_relative "MyOrderedItem"
MyBST.rb
require_relative "MyOrderedItem"
include MyOrderedItem
#....................................................................................MyBST
module MyBST
end# module MyBST
# un-comment if your module is in a separate file
#require_relative "MyBST"
include MyBST
#....................................................................................MyInt
class MyInt
attr_reader :item
def initialize(item); @item = item; end# initialize
def compareTo(other)
if !(other.instance_of?(MyInt))
raise "MyInt compareTo: #{other} is not a MyInt"
end
return self.item() - other.item()
end# compareTo
def to_s; "#{@item}"; end# to_s
end# class MyInt
#.....................................................................................main
def testBST
arr = [12, 7, 16, -2 ,0, 18, 1, 100]
bst = BST.new
arr.size.times do |i|
newInt = MyInt.new(arr[i])
puts "inserting #{newInt.to_s}"
bst.insert(newInt)
end
puts bst.to_s
puts 'End of processing'
end# testBST
MyOrderedItem.rb
module MyOrderedItem
end# module MyOrderedItem
# nothing to test here
smallText.txt
AAAAAAAAAAAAAAACCCCCCCEEEEEEEEEEEEEEEE EEEEEEEEEGGGGGGHIIIIIIIIIIIIIIIBBBBBBDDDDDDDD DDDDFFFF
Encoding (with '|' between each character):
output
111|111|111|111|111|111|111|111|111|111|111|111|111|111|1 11|1101|1101|1101|1101|1101|1101|1101|10|10|10|10|10|1 0|10|10|10|10|10|10|10|10|10|10|10|10|10|10|10|10|10|10| 10|1100|1100|1100|1100|1100|1100|01000|00|00|00|00|00| 00|00|00|00|00|00|00|00|00|00|0101|0101|0101|0101|010 1|0101|011|011|011|011|011|011|011|011|011|011|011|011| 01001|01001|01001|01001
Explanation / Answer
class HuffmanCoder
def self.encode(text = "")
return HuffmanString::from_plaintext(text)
end
def self.decode(text = "")
return HuffmanString::from_ciphertext(text)
end
end
class HuffmanString
attr_accessor :plaintext
attr_accessor :tree
attr_accessor :ciphertext
def self.from_plaintext(text = "")
s = HuffmanString.new
s.plaintext = text
return s
end
def self.from_ciphertext(ciphertext = "")
s = HuffmanString.new
s.ciphertext = ciphertext
return s
end
def plaintext=(text)
@plaintext = text
@tree = HuffmanTree::build(self.plaintext)
@ciphertext = self.tree.encode(self.plaintext)
end
def ciphertext=(text)
@tree, @ciphertext = HuffmanTree::parse(text)
@plaintext = self.tree.decode(self.ciphertext.clone)
end
# Overridden to return the completely encoded bit string
def to_s
return self.tree.to_binary_string + self.ciphertext
end
def inspect
str = "Huffman String "
str += " Plaintext: #{self.plaintext} "
str += " Binary plain: #{self.plaintext.encode("UTF-8").bytes.to_a.map{|c| c.to_s(2)}.join} "
str += " Tree: #{self.tree} "
str += " Binary tree: #{self.tree.to_binary_string} "
str += " Ciphertext: #{self.ciphertext} "
return str
end
end
class HuffmanTree
attr_accessor :root
def initialize(root = nil)
self.root = root
end
def self.build(str = "")
pq = PriorityQueue.new
str.split("").each do |c|
pq.put(c, pq.get(c) + 1)
end
while pq.length > 1
v1 = pq.pop_with_prio
v2 = pq.pop_with_prio
prio = v1[1] + v2[1]
node = HuffmanNode.new(nil)
if v1[0].is_a? HuffmanNode
node.left = v1[0]
node.left.parent = node
else
node.left = HuffmanNode.new(node, v1[0])
end
if v2[0].is_a? HuffmanNode
node.right = v2[0]
node.right.parent = node
else
node.right = HuffmanNode.new(node, v2[0])
end
pq.put(node, prio)
end
return HuffmanTree.new(pq.pop)
end
def self.parse(str)
input = str.clone
root = HuffmanNode.new(nil)
current = root
while true
code = input.slice!(0, 1)
if code == "0"
# node has two children
current.left = HuffmanNode.new(nil)
current.left.parent = current
current.right = HuffmanNode.new(nil)
current.right.parent = current
current = current.left
elsif code == "1"
# node has a value
val = input.slice!(0, 8)
current.value = Integer("0b" + val).chr
while current != nil and (current.right.nil? or current.right.full_subtree?)
current = current.parent
end
if current.nil? or (current == root and !current.right.value.nil?)
break
end
current = current.right
end
end
tree = HuffmanTree.new(root)
return [tree, input]
end
def to_s
return "#<HuffmanTree:root=#{self.root}>"
end
def encode(text = "")
return text.split("").map{|c|self.binary_path_to(c)}.join("")
end
def decode(ciphertext = "")
current = self.root
s = ""
while ciphertext.length > 0
val = ciphertext.slice!(0, 1)
current = current.left if val == "0"
current = current.right if val == "1"
if !current.value.nil?
s += current.value
current = self.root
end
end
return s
end
def binary_path_to(char = "")
return "" if char.length != 1
ans = []
visited = {}
current = self.root
return "" if current.nil?
while true
visited[current] = true
if current.value == char
break
end
if !current.left.nil? and current.left.is_a? HuffmanNode and !visited[current.left]
ans << 0
current = current.left
next
end
if !current.right.nil? and current.right.is_a? HuffmanNode and !visited[current.right]
ans << 1
current = current.right
next
end
if (current.right.nil? or visited[current.right]) and (current.left.nil? or visited[current.left])
ans.pop
current = current.parent
next
end
break
end
return ans.map{|x| x.to_s}.join("")
end
def to_binary_string
return self.root.to_binary_string
end
end
class HuffmanNode
attr_accessor :left
attr_accessor :right
attr_accessor :parent
attr_accessor :value
def initialize(parent, v = nil)
self.parent = parent
self.value = v
end
def to_s
if self.value.nil?
if self.left.nil? and self.right.nil?
return "nil"
else
return "#<HuffmanNode:value=#{self.value},left=#{self.left},right=#{self.right}>"
end
else
return self.value
end
end
def to_binary_string
if self.value.nil?
return "0" + self.left.to_binary_string + self.right.to_binary_string
else
bs = self.value.encode("UTF-8").bytes.to_a[0].to_s(2)
s = "1" + ("0" * (8 - bs.length) + bs)
raise Exception.new("Failed assertion: encoded value string is not nine bits long") if s.length != 9
return s
end
end
def full_subtree?
if self.left.nil? and self.right.nil?
return !self.value.nil?
end
return (self.left.full_subtree? and self.right.full_subtree?)
end
end
class PriorityQueue
attr_accessor :data
def initialize
self.data = {}
self.data.default = 0
end
# Insert the given key at the given priority. Replaces the matching key's priority, if it exists.
def put(k, v)
self.data[k] = v
end
# Read the priority for the given key without removing it
def get(k)
return self.data[k]
end
# Get the next key according to priority. Does not remove the key.
def peek
return nil if self.length == 0
frequencies = self.data.sort_by{|k,v| v}
val = frequencies.select{|x| x[1] == frequencies[0][1]}.map{|x| x[0]}.sort_by{|x| x.to_s}[0]
return val
end
# Get the next key according to priority. Does not remove the key.
# Returns an array of the form [value, priority].
def peek_with_prio
return nil if self.length == 0
val = self.peek
return [val, self.get(val)]
end
# Get the next key according to priority. Removes the key.
def pop
val = self.peek
self.delete(val) if !val.nil?
return val
end
# Get the next key according to priority. Removes the key.
# Returns an array of the form [value, priority].
def pop_with_prio
val = self.peek_with_prio
return nil if val.nil?
self.delete(val[0])
return val
end
# Remove the given key from the queue, regardless of its priority
def delete(k)
self.data.delete(k)
end
# Get the number of keys currently in the queue.
def length
return self.data.length
end
end
require 'optparse'
require './coder.rb'
options = {}
OptionParser.new do |opts|
opts.banner = "Usage: huffman.rb [options]"
opts.on("-m", "--mode MODE", [:encode, :decode], "Set the mode: encode/decode") do |m|
options['mode'] = m
end
end.parse!
if options['mode'].nil?
puts "You must specify a mode: encode/decode"
Kernel::exit(FALSE)
end
if ARGV.length == 0
puts "You must specify some text to #{options['mode']}"
Kernel::exit(FALSE)
end
case options['mode']
when :encode
encoded = HuffmanCoder::encode(ARGV.join(" "))
puts encoded.to_s # encoded binary string
when :decode
puts HuffmanCoder::decode(ARGV.join(" ")).plaintext
else
puts "Invalid mode"
Kernel::exit(FALSE)
end
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.