Assignment 9 – Hash Compression
Objective
Learn basic uses of Hash Algorithms to implement compression in a simplified case
Supports learning outcome 3
3. Implement data structures and algorithms in computer code.
Introduction
The topic of hashing is quite easy Topic – Hashing Techniques – if you have done anything as simple as putting socks in one drawer and underwear in another, well you’ve exercised the principle of hashing. Put similar items in bins so they can be found more easily.
Assignment
If you look at some compression techniques (such as LZW Compression https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch ) they make use of the concept of hashing techniques to compress files. We are going to do something similar. Consider the phrase
To be or not to be, that is the question.
Even though it does not make much sense to do this as the phrase is short. We will create bins for each word and record the position of the instances of the words in the proper bins. So write a program that first has a series of bins
to
be
or
not
Because the word to occurs in positions 1 and 5, the bin for the word to will contain 1 and 5
to: 1, 5
be: 2, 6
or: 3
not: 4
Write a program that will take the phrase, create bins for each word, and then record the instance position of each word in the bin. It will then output each bin (word) and the locations of the word in the phrase. So if the input was;
I want what I want and I know what I want.
The output would be;
I: 1, 4, 7, 10
what: 3, 9
want: 2, 5, 11
and: 6
know: 8
I have created a JSFiddle Shell to get you started that is here – http://jsfiddle.net/reaglin/rm96Luws/ to create your own JSFiddle from this one – use the Fork Option.
You can research algorithms for this type of hash compression, but you should be able to develop an algorithm to do this efficiently. You can use the String split function to separate the input into the initial array, and I will only use spaces to separate words when testing your code.
You are free to discuss what data structures you will use to hold the results and input on the discussion boards. In this assignment, you are free to select any structure you wish to complete the assignment.
Assignment Grading – I will look at your code to see if you constructed a decent Hash with bins to perform this. You can use an array, Lists, Queues, or combinations of these to hold the information. For example, you could keep the bins in an array, and each bin could be a list. A working system is worth 5 points, and a design that uses the structures you have used to date makes it worth another 5.
