Description
Finish the implementation of Huffman compression and decompression using provided template. Several methods are already provided and ideally should be used. You need to provide implementations for the compress, decompress, makeTrie, makeCodingTable, and determineFrequencies methods (currently empty). You are also responsible for providing the documentation for these methods. You only need to modify the methods in the Huffman.java file. The main method takes two parameters, <+ | -> . If you want to compress a file, use – , to decompress use + . Compress creates a new file with name of original appended with “zip”, e.g. “input.txt.zip”. The decompress prints to standard out to avoid overwriting the original file. Notes on using the BitStreamOutput/Input in the compress/decompress methods: In compress, to write the number of symbols use the writeBits(…) method, for example: out.writeBits(text.length, 31); To write out a code (stored in the coding table as a String, e.g. “0101”), go through each char and use writeBit(boolean): if( code.charAt(j) == ‘0’ ) out.writeBit(false); else if( code.charAt(j) == ‘1’ ) out.writeBit(true); In decompress, the input should be performed similarly, to read in the number of symbols: int n = in.readBits(31); The codes were written out a bit at a time, so you need to read in a single bit at a time. You use the boolean returned to traverse the trie to a leaf which has the corresponding symbol. This is best accomplished with an iterative while loop. if( in.readBit() ) // go right else // go left Grading Notes You must: • Use the template provided for you • Have a style (indentation, good variable names, etc.) • Comment your code well (no need to over do it, just do it well) You may not: • Make your program part of a package. • Use code from anywhere except your own brain. Submission Instructions: • Name a folder with your gmu username • Put your java files in the folder (but not your .class) • Zip the folder (not just the files) and name the zip “username-pa8.zip” • Submit to blackboard Grading Rubric No Credit: • Non-submitted assignments • Late assignments • Non-compiling assignments • Non-independent work 1pt Submission Format 1pt Style and Comments 2pt compress 2pt decompress 2pt makeTrie 1pt makeCodingTable 1pt determineFrequencies Example Compress > java Huffman – algorhyme.txt > ls -la total 80 drwxr-xr-x. 2 user user 4096 Nov 3 14:35 . drwxrwxr-x. 4 user user 67 Nov 3 14:10 .. -rw-r–r–. 1 user user 386 Nov 3 14:31 algorhyme.txt -rw-rw-r–. 1 user user 262 Nov 3 14:35 algorhyme.txt.zip -rw-rw-r–. 1 user user 1972 Nov 3 14:34 BitStreamInput.class -rw-rw-r–. 1 user user 2642 Sep 6 20:40 BitStreamInput.java -rw-rw-r–. 1 user user 4268 Nov 3 14:34 BitStreamOutput.class -rw-r–r–. 1 user user 5817 Sep 6 20:41 BitStreamOutput.java -rw-rw-r–. 1 user user 4759 Nov 3 14:34 Huffman.class -rw-rw-r–. 1 user user 9756 Nov 3 14:07 Huffman.java -rw-rw-r–. 1 user user 1842 Nov 3 14:34 Huffman$Node.class -rw-rw-r–. 1 user user 2426 Nov 3 14:34 MinHeap.class -rw-rw-r–. 1 user user 3528 Sep 5 22:32 MinHeap.java -rw-rw-r–. 1 user user 4065 Nov 3 14:34 Stdio.class -rw-rw-r–. 1 user user 6950 Sep 13 16:53 Stdio.java Example Decompress > java Huffman + algorhyme.txt.zip Decompressed: I think that I shall never see A graph more lovely than a tree. A tree whose crucial property Is loop-free connectivity. A tree that must be sure to span So packets can reach every LAN. First, the root must be selected. By ID, it is elected. Least-cost paths from root are traced. In the tree, these paths are placed. A mesh is made by folks like me, Then bridges find a spanning tree. >
