Description
In this project you will implement the LZW algorithm so that
• the code length is always between 9 bits (initially) and 16 bits, and the codes are packed at the output so as to occupy the minimum possible number of bytes for the whole compressed sequence (this is the same way that Huffman codes were mapped to bytes in the previous assignment).
• the LZW string dictionary will be implemented as a hash table of maximum capacity 216 entries using cuckoo hashing, with the search key for get() and put() being a character sequence, and the value associated to key (passed as an argument to put() and returned by get() when the key is found) being the number of elements already in the table when a key is first added (that is, the k-th string added to the table has value k for all k≥0) – notice that there is no need to implement a remove() method since it will never be used.
• whenever the number of strings in the cuckoo hashing mechanism is unable to add a new entry to the table (i.e. the cuckoo cycle gets longer than MaxLoop), it is reset to its initial contents of all 256 one-character strings plus the control code (which always gets
itself the value 256 and is associated to the empty string) by means of a reset() method,
and the code length gets back to 9 bits. You are responsible for implementing the LZW class that must function according to the following interface:
• LZW()
o a dummy constructor (no real work to do yet)
• static final int RESTART = 256
o the LZW control code to signal the resetting of the cuckootable
• byte[] compress(String fullText)
o a method that takes the text of an English message to be compressed and
returns a byte[] containing the packed sequence of LZW codes for the whole text (this method is responsible for initializing the dictionary to all 1-byte strings plus the RESET code (associated to the empty string), monitoring when it becomes full and resetting it to this initial state, then converting the sequence of codes into a byte array the same way as was done for Huffman coding.
• String decompress(byte[] compressed)
o a method that takes the binary compressed file (that is, the packed LZW codes
generated by the method above) and produces from it the exact contents of the original file.
I have already completed the cuckoo table.
I need help with the lzw class implementation.
You must compress “War and Peace” to within 1 kibibyte of 1309 kibibytes (in either direction) in less than 3 seconds and decompress the compressed file in less than 1 second. I ALREADY FINISHED THE PROJECT BUT IT HAS BUGS AND ITS NOT RUNNING AS IT SHOULD I NEED HELP WITH THIS AND I WILL PROVIDE THE CODE AND TEXT FILES NEEDED
