In this assignment, you will learn about the famous Lempel-Ziv-Welch (LZW)
compression algorithm. Most compression algorithms including UNIX
compress are based on the LZW algorithm. The LZW algorithm
compresses a given text by figuring out patterns which appear very
often in the text. The basic idea is replace (perhaps very long) patterns
which appear many times by a much shorter code. Read about this algorithm
here.
Your assignment is to implement the LZW algorithm. You can assume that the
input text contains english characters (capital and small), space, and
full stop. You need to write two programs - one for compressing an input
text, and the other to uncompress the compressed text to the original text.
To implement the dictionary of code and key, you will use a hash table. Use your own
hash function, but you must use quadratic probing to resolve collisions.