The goal for this project is to develop a file compression utility to
compete with applications like 7-Zip, gzip, WinZip etc. You must
develop two Java executables:
JMZip will take two command line arguments. The first is the the
file to compress, and the second is the name of a file to create. A
sample execution might look like the following:
$ java JMZip MyPaper.doc MyPaper.jmz
This command would perform Huffman encoding on the data in
MyPaper.doc and save a compressed version of the file to
JMUnzip application must undo the compression process to
recreate a copy of the original file. The first argument will be the
compressed file, the second argument will be the desired file name of
the uncompressed file. We could decompress
MyPaper.jmz as follows:
$ java JMUnzip MyPaper.jmz MyPaperRestored.doc
- Both applications must print appropriate error messages in the case of missing or incorrect arguments. In particular, the user must be informed if he or she attempts to open a file that cannot be opened or save to a location where they do not have permission.
- Both applications should overwrite the file specified in the second argument if that file already exists.
- Neither application may modify the file provided as the first argument.
You should already have experience reading and writing text files in Java. You may not have experience handling file I/O with binary data. For this application it will be necessary to both read and write binary data. We will need to read binary files because our compression tool should be able to compress any file whether or not it contains plain-text. We will need to create binary files because the Huffman coding process results in a binary encoding. Saving a series of 0’s and 1’s as ASCII characters would not reduce the overall file size since we would end up using eight bits to store each individual bit of encoded data.
We are providing two Java files to help with efficiently manipulating and storing binary data.
BitSequence.java- This class represents an arbitrarily long sequence of bits. You will use this class to represent the Huffman-encoded version of the input file.
HuffmanSave.java- This is a simple container class that stores a
BitSequencealong with a
HashMapof frequency data. Recall that decoding the bit sequence created during the Huffman coding process requires us to have access to the Huffman tree that was used to create the code. A
HuffmanSaveobject stores all of the information necessary to reconstruct a compressed file. The frequency data can be used to rebuild the Huffman tree and the
BitSequencestores the encoded data.
For this application the
.jmz files must be serialized versions of
HuffmanSave objects. Object serialization is the process of
converting a complete Java object into a binary form so that it can be
saved to a file or communicated over a network. This
provides some background on serialization and shows examples of saving
and loading Java objects.*
HuffmanSave.java must not be
Tips, Advice and Additional Information
Our textbook provides a partial implementation of a Huffman tree. You are welcome to use that code as a starting point, but you should be aware that it is incomplete and will require some modifications. For example, the leaves in the textbook implementation store
charvalues. Your code will need to store
There are undoubtedly many other Java Huffman tree implementations floating around on the internet. Obviously, submitting any of that code as your own would violate the JMU honor code. As always, if you obtain any information from outside sources you must provide a link to your source in the acknowledgment statement in your submission. (Copying external code with a citation wouldn’t violate the honor code, but it also wouldn’t result in any credit for the project.)
One issue that needs to be addressed when developing a Huffman tree is how to handle ties: which trees should be selected when more than two options are tied for the lowest frequency? In one sense, it doesn’t matter. In the case of a tie any valid choice will result in the same encoding length as long as the frequencies actually match the frequencies in the data being encoded.
On the other hand different choices in tie-breaking will result in different trees and thus different encodings. This is an issue for decoding because the resulting bits can only be decoded by a tree that exactly matches the tree that was used for the encoding process.
This must be addressed by providing a deterministic mechanism for breaking ties. For example, ties go to the tree that contains the lowest byte value. You can implement this by modifying the existing
compareTomethod so that it performs some additional logic in the case of ties based on frequency. Failing to address this issue can lead to symptoms that are difficult to diagnose. The encoding/decoding process may seem to work well in most cases because the tree happens to be built the same way for decoding as it was for decoding.
You probably have the most experience reading files using the
Scannerclass. Recall that every file is really just a long sequence of bytes. The
Scannerclass is useful because it allows us to interpret those bytes as
Strings etc. For this project, we don’t care what the bytes actually represent. This means there is no reason to use the
Scannerclass. Instead you can just use the
FileInputStreamto process the bytes in the file directly.
|Web-CAT Style Checks||20%|
|Web-CAT Instructor Style Points||20%|
* Note that object serialization is not a good strategy for long-term data storage. If the implementation of the serialized class changes, it becomes impossible to deserialize using a Java program that uses a later version of the class. We are using serialization for this project because it saves us the trouble of specifying and implementing a new binary data format. If you were to continue developing this tool the next step would be to design a file format that is independent of the details of the implementation.