This assignment will focus on an application of priority queues
called Huffman Encoding. This encoding allows a developer to
compress data stored in text files so that they use up less
space on disk.
Here is what we'd like you take out of this assignment.
Develop a priority queue using a binary heap
To work with Java's implementation of the priority queue ADT.
To illustrate a technique for compressing strings through a simple console program.
Similar to other data types, string characters are stored as binary numbers in computer systems. Characters are converted
to base-2 numbers using an encoding scheme, where we map each character to a numeric value. You have probably heard
of several of these schemes before: ASCII, Unicode, UTF-8, UTF-16, etc...
Each encoding scheme supports different types of characters. The number of supported characters depends upon the amount of bits (binary digits) used to store each character. If more bits are used to store a character, then you can typically store a larger range of characters. The opposite is true where, given fewer bits we can represent fewer types of characters. Encoding schemes have a difficult job to accomplish as there are many different languages in the world and with them plenty of characters to represent in our programs.
Here is an example encoding scheme. This table includes part of the ASCII encoding scheme which can be used to
represent 128 unique characters.