Microsoft Word - comp2150-w2022-A4.docx COMP 2150 – Winter 2022 – Assignment 4 Due April 25 at 11:59 PM In this assignment, you will implement javascript classes to support Huffman data compression....

Do the code for the folling program


Microsoft Word - comp2150-w2022-A4.docx COMP 2150 – Winter 2022 – Assignment 4 Due April 25 at 11:59 PM In this assignment, you will implement javascript classes to support Huffman data compression. Data compression (as used in zip and rar, for instance) is the process of taking large files and making them smaller by analyzing their contents. In this assignment the algorithm we will use is called Huffman encoding, and it works by building a binary tree that encodes each character as a sequence of 0s and 1s. The encoding is variable-length: some characters will be encoded as a short sequence of 0s and 1s, while other (more rare) characters will be encoded with longer sequences. Part 1: Hash Table Dictionary Create a javascript class called Dictionary that is implemented as a hash table. In the Dictionary, each entry is a Key-Value pair, and there can't be two Key-Value pairs in a dictionary with the same Key (that is, keys are unique in a dictionary). The Key will be an object that has a hashVal method (see below for the Hashable class and hashVal information). A Value can be anything (except undefined). When initialized, the Dictionary should be given a size as a parameter1. The Dictionary will create an array of that size as a field. When adding or searching for a Key-Value pair in the Dictionary, the position of the pair in the hash table will be the key’s hashVal modulo the length of the array. The hash table should use separate chaining. If there is a collision between two elements based on their hashVal, the hash table should place both elements in a linked list of elements at the array position. The order of elements in the linked list at a position is not important. The Dictionary should implement the following methods: 1. put(k,v): takes a Hashable key k and a value v and adds it to the dictionary, if it does not exist. If a key-value pair with k as the key already exists, the current value is replaced with v. The method does not have a return value. 2. get(k): takes a Hashable key k and returns the value v associated with it, if it appears in the dictionary. The method should return undefined if the key does not appear in the dictionary. 3. contains(k): takes a Hashable key k and determines if it is a key in the dictionary. Returns a boolean value. 4. isEmpty(): returns a boolean depending on whether the dictionary is empty or not. For each of the first three methods, the method should ensure that the key parameter has type Hashable (or has a hashVal() method, and an equals() method, as appropriate), and it should throw an error if the condition does not hold. 1 When using Dictionaries in this assignment, you should set the size to a large value of your choice. Hashable You should also implement a hierarchy of Hashable classes that can be stored as Keys in the hash table. The Hashable class should be abstract (using the techniques shown in class) with an abstract hashVal() and an abstract equals(x) method. You should implement at least the following two Hashable subclasses: • IntHash, whose hashVal function is the value of the integer. Two IntHash objects are equal if they contain the same integer value. • StringHash, whose hashVal function is the following expression: s[0]*pn-1 + s[1]*pn-2 + ...+ s[n-3]*p2 + s[n-2]*p + s[n-1] where s[i] is the ASCII value of the i-th character of the string, n is the length of the string, and p is a prime.2 You can assume that all characters in the strings are ASCII characters. Two StringHash objects are equal if they contain the same strings. Note: to get the ASCII value of a character from a string, you can use .charCodeAt(): x.charCodeAt(i) gives the ASCII value of the character at position i of the string x. The subclasses can have additional methods if you need them, including getters. You may implement further Hashable subclasses, but you are not required to do so. 2 In your code you should use a prime number of your choice that is less than 1000. Part 2: Huffman Trees To allow us to complete Part 3, you will create a class to represent a Huffman Tree, which is a type of binary tree used in Huffman Encoding (in Part 3). A Huffman Tree has the following properties: 1. Each tree is a binary tree. The children are not ordered in the same way as a binary search tree – we only talk about “left” and “right” subtrees. The tree is also not structured in a balanced way: left and right subtrees of a node, for instance, may have different heights. 2. Every internal node has two children. 3. Leaf nodes in a Huffman tree are labelled with a single character. Internal nodes in the tree are not labelled with any data. 4. Each Huffman Tree has a weight, which is a floating point value between zero and one. Create a class that represents Huffman Trees. You will need the following operations: 1. Creating a new tree: you should be able to create a tree that has one node, based on two parameters: a single character and a weight. This will create a tree with one node (a leaf node) and the weight given. 2. Combine two trees to create a new tree: you should be able to create a tree from two other trees (the left and right subtrees). The new tree should have a new root node, whose children are the two subtrees given, and the weight of the new tree is the sum of the weights of the two subtrees given. 3. You should implement a compareTo method for Huffman Trees. This method should take a parameter (another Huffman Tree) and return +1,0 or -1 to represent whether the parameter tree comes before (+1) or after (-1) the tree whose method is being called. For any two trees, the tree with the lowest weight should come first. If the two trees have the same weight, the tree that contains (in any leaf) the smallest character (in order) should come first.3 For example, if two trees had the same weight and if one tree contained the characters “C”,”O”,”M”,”P” and the other contained “E”,”N”,”G”,”L”, then the first tree would come first (it contains “C”). Because of how Huffman Trees are built, you do not have to worry about two trees containing the same smallest character (but if they did, you could return 0). 4. You will additionally need a search or traversal method in your Huffman Trees. This should be able to determine, for each character in the tree, the path (left/right moves) from the root to the leaf labelled with that character. This is described more in step 4 of the algorithm in Part 3. 3 To compare characters, use the less than operator < in javascript. part 3: huffman encoding after creating your dictionary and huffman tree classes, use them to implement huffman encoding. huffman encoding is used to compress text files by replacing characters in the text with sequences of bits (0-1).4 the algorithm works as follows: 1. the input to the algorithm is a text file. 2. before encoding anything, the entire file should be read, and character frequencies are calculated for each character that appears in the file. you then calculate, for each character x in the file “what is the percentage of the file that is the character x?” (as a number between 0 and 1). store this information in a dictionary from part 1. this calculation should be done for all characters, including spaces, newlines, etc. 3. next, the huffman encoding is constructed. the huffman encoding is built by constructing a set of huffman trees, and then joining these trees until one final huffman tree remains. a. initially, we construct a tree for each character in the file. the weight used for these initial trees are the percentages (0-1) calculated in step 2. b. at each step, we choose the two huffman trees in the set that are smallest, according to the order given by the compareto algorithm in part 2. we join these two trees, using the joining algorithm in part 2. (the left tree should be the smaller tree using compareto). remove the two trees that were joined from the set of huffman trees and add the new tree (thus, the set will have one fewer tree at each step). c. repeat this until all of the huffman trees are combined into one tree, which we call t. to support this step, you may need to construct additional javascript classes. 4. then, the huffman code is calculated. for each different character x that appears in the file, calculate the path from the root of t to the leaf that is labelled with the character x. build a string that represents this path to x: each time the path moves from a node to the left child, add a zero to the string and each time it moves to the right child, add a 1 to the string. 5. read the characters from the input file again. for each character in="" javascript.="" part="" 3:="" huffman="" encoding="" after="" creating="" your="" dictionary="" and="" huffman="" tree="" classes,="" use="" them="" to="" implement="" huffman="" encoding.="" huffman="" encoding="" is="" used="" to="" compress="" text="" files="" by="" replacing="" characters="" in="" the="" text="" with="" sequences="" of="" bits="" (0-1).4="" the="" algorithm="" works="" as="" follows:="" 1.="" the="" input="" to="" the="" algorithm="" is="" a="" text="" file.="" 2.="" before="" encoding="" anything,="" the="" entire="" file="" should="" be="" read,="" and="" character="" frequencies="" are="" calculated="" for="" each="" character="" that="" appears="" in="" the="" file.="" you="" then="" calculate,="" for="" each="" character="" x="" in="" the="" file="" “what="" is="" the="" percentage="" of="" the="" file="" that="" is="" the="" character="" x?”="" (as="" a="" number="" between="" 0="" and="" 1).="" store="" this="" information="" in="" a="" dictionary="" from="" part="" 1.="" this="" calculation="" should="" be="" done="" for="" all="" characters,="" including="" spaces,="" newlines,="" etc.="" 3.="" next,="" the="" huffman="" encoding="" is="" constructed.="" the="" huffman="" encoding="" is="" built="" by="" constructing="" a="" set="" of="" huffman="" trees,="" and="" then="" joining="" these="" trees="" until="" one="" final="" huffman="" tree="" remains.="" a.="" initially,="" we="" construct="" a="" tree="" for="" each="" character="" in="" the="" file.="" the="" weight="" used="" for="" these="" initial="" trees="" are="" the="" percentages="" (0-1)="" calculated="" in="" step="" 2.="" b.="" at="" each="" step,="" we="" choose="" the="" two="" huffman="" trees="" in="" the="" set="" that="" are="" smallest,="" according="" to="" the="" order="" given="" by="" the="" compareto="" algorithm="" in="" part="" 2.="" we="" join="" these="" two="" trees,="" using="" the="" joining="" algorithm="" in="" part="" 2.="" (the="" left="" tree="" should="" be="" the="" smaller="" tree="" using="" compareto).="" remove="" the="" two="" trees="" that="" were="" joined="" from="" the="" set="" of="" huffman="" trees="" and="" add="" the="" new="" tree="" (thus,="" the="" set="" will="" have="" one="" fewer="" tree="" at="" each="" step).="" c.="" repeat="" this="" until="" all="" of="" the="" huffman="" trees="" are="" combined="" into="" one="" tree,="" which="" we="" call="" t.="" to="" support="" this="" step,="" you="" may="" need="" to="" construct="" additional="" javascript="" classes.="" 4.="" then,="" the="" huffman="" code="" is="" calculated.="" for="" each="" different="" character="" x="" that="" appears="" in="" the="" file,="" calculate="" the="" path="" from="" the="" root="" of="" t="" to="" the="" leaf="" that="" is="" labelled="" with="" the="" character="" x.="" build="" a="" string="" that="" represents="" this="" path="" to="" x:="" each="" time="" the="" path="" moves="" from="" a="" node="" to="" the="" left="" child,="" add="" a="" zero="" to="" the="" string="" and="" each="" time="" it="" moves="" to="" the="" right="" child,="" add="" a="" 1="" to="" the="" string.="" 5.="" read="" the="" characters="" from="" the="" input="" file="" again.="" for="" each="">
Apr 13, 2022
SOLUTION.PDF

Get Answer To This Question

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here