Compression

Files can often be compressedthat is, represented using fewer bytes than the standard representation. This technique is useful for saving disk space and for reducing network traffic. The total time required to compress a file, send the compressed file, and uncompress it at the other end is often less than the time required to send the uncompressed file. This explains why software made available for download over the Internet is usually compressed.

In this section, we discuss two algorithms for compressing data. The discussion is in terms of text, but these algorithms can be adapted to work for any kind of data.

Huffman Encoding

In an ASCII text file, each character is represented by the same number of bits. Such a fixed-length encoding is somewhat wasteful, because some characters are more common than others. If a character appears frequently, it should have a shorter representation. Huffman encoding produces such an efficient representation.

Consider the String "beekeepers_&_bees". Eight different characters appear in this String, so we could have a 3-bit code for each character (Figure 17-14). (ASCII works like this, using 7 bits to encode 128 different characters.) In a Huffman encoding, common characters such as 'e' have shorter codes than rare characters such as '&'.

Representing the String "beekeepers_&_bees" using the fixed-length encoding requires 51 bits:

000 001 001 010 001 001 011 001 100 101 110 111 110 000 001 001 101

Using the Huffman encoding, this takes only 45 bits:

110 0 0 11110 0 0 11111 0 1011 100 1110 1010 1110 110 0 0 100

The savings can be considerably greater on a long String, such as the entire text of a novel.

We included spaces above to make it clear where one code begins and another ends. In practice, there is only a sequence of bits. It is easy to detect the end of a code in a fixed-length encoding, because each code uses the same number of bits. We might worry that, in a Huffman encoding, we might incorrectly conclude that we've read the code 100 when we've really only read the first three characters of the code 10011. To avoid this danger, Huffman encodings are designed so that no code is a prefix of another code. For example, the code for 'b' is 110, and no other code starts with 110.

A Huffman encoding can be automatically generated from a table of character frequencies. These should be drawn from a string typical of those being compressed. For example, when compressing English text, character frequencies on the front page of the New York Times will do nicely. To keep our example small, however, we will use the frequencies in the message being compressed (Figure 17-15).

To generate a Huffman encoding, we first construct a binary tree. When we are done, leaves in this tree corresponds to characters. Deeper leaves have longer codes.

One node is created for each character, holding both that character and its count (Figure 17-16). This is a forest of trees, each containing one node. On each pass through the main loop, we choose the two lowest-count roots and merge them. (It doesn't matter how we handle ties.) The count for the new parent is the sum of its children's counts.

Figure 17-16. Building a Huffman tree. Initially, each node is in a separate tree (top). On each pass through the main loop, we combine the two roots with the lowest counts.

(This item is displayed on page 480 in the print version)

This continues until there is only one tree (Figure 17-17). The code for each character is determined by the path from the root to the corresponding leaf. Each right descent is represented by a 1, each left descent by a 0. For example, the path to 'b' is right-right-left, so its code is 110.

Figure 17-17. Final Huffman tree. The code for each character is determined by the path from the root to the corresponding leaf.

(This item is displayed on page 480 in the print version)

To translate these ideas into Java, we first need a class HuffmanNode (Figure 17-18). This is almost identical to a BinaryNode, but it has an additional field count. It also implements Comparable, so that we can find the lowest-count root. Inheritance pays off handsomely here.

Figure 17-18. The HuffmanNode class extends BinaryNode.

An instance of the Huffman class contains a tree of such nodes and a direct addressing table mapping characters to their codes (Figure 17-19). The codes are given as Strings of ones and zeroes for readability. In practice, the program would really read and write bits from a file; this is left as Project 17.20.

Figure 17-19. The constructor for the Huffman class first generates a tree, then uses the tree to generate a table of codes.

In generating the tree, we need to keep track of a set of roots. In each pass through the main loop, we need to grab the two roots with the smallest counts. This is a job for a priority queue (Figure 17-20).

Figure 17-20. A priority queue is used in building a Huffman tree.

This tree will be useful in decoding, but to encode a String we'll need a way to quickly get from a character to its code. This is accomplished using a direct-addressing table, which is populated by the elegant recursive method generateCodes() (Figure 17-21).

Once we have this table, encoding a String is just a matter of concatenating the codes for the characters making up the String (Figure 17-22).

Now, for example, if we

encode("beekeepers_&_bees")

Figure 17-21. As generateCodes() recurs more deeply into the tree, code gets longer.

Figure 17-22. The code for each character can be looked up in the table.

the result is:

"110 0 0 11110 0 0 11111 0 1011 100 1110 1010 1110 110 0 0 100"

To decode a message, we start at the root of the tree and use the incoming bits to steer left and right (Figure 17-23). When we hit a leaf, we add a character to the result and go back to the root.

Figure 17-23. The Huffman tree is used in decoding a String.

Now, for example,

decode(encode("beekeepers_&_bees"))

returns "beekeepers_&_bees".

LempelZiv Encoding

It is possible to prove that Huffman encoding is the best possible character-by-character encoding. We can do even better by creating codes for frequently occurring substrings. For example, when compressing Java programs, it could be useful to have special codes for substrings such as "public" and "for (int i = 0; i <". LempelZiv encoding uses this idea.

The set of codes used in LempelZiv encoding is not created in advance, but generated during encoding or decoding. Each code is an int corresponding to a String of one or more characters. Originally, there is a code for each single character.

As an example, consider encoding the String "beekeepers_&_bees" (Figure 17-24). We begin by reading the character 'b' and outputting the code for 'b'. On each subsequent step, we output a code and create a new code. As we work through the text, we eventually encounter substrings for which we have already created codes.

We output the code corresponding to the longest prefix of the remaining text for which there is a code. For example, when the remaining text is "eepers_&_bees", there is a code for "ee" but not for "eep", so the code for "ee" is output.

When a new code is created, it represents a String constructed from the Strings represented by the last two codes emitted. Specifically, it is the concatenation of the older string and the first character of the newer string. For example, when the last two codes emitted represented "k" and "ee", the new code represents "ke".

To implement this algorithm, we need two data structures to keep track of the codes. The first structure is a direct-addressing table mapping ints to Strings. The second structure is a digital search tree (Section 14.3) with codes stored at the nodes.

These data structures are declared in Figure 17-25. The constructor initializes them by creating one child of root for each of the 128 ASCII characters.

Our encode() method (Figure 17-26) reads from a Scanner and writes ints to an ObjectOutputStream. In the main loop on lines 820, we work down the digital search tree, using characters from the input to choose a child. When we can't go any further, we've found the longest prefix, so we emit a code and create a new one (lines 1115).

Figure 17-25. Data structures and constructor for the LempelZiv class.

Figure 17-26. LempelZiv encoding.

The protected method addNewCode() adds a node to the tree and an entry to the direct-addressing table (Figure 17-27).

Figure 17-27. Adding a new code to both data structures.

Now, for example, to compress the file words into the file words.lz, we could do this:

Scanner in = new Scanner(new File("words")); ObjectOutputStream out = new ObjectOutputStream(new FileOutputStream("words.lz")); new LempelZiv().encode(in, out);

Surprisingly, we don't need to keep the data structures around to decode a string. They can be generated on the fly during the decoding process, just as during the encoding process (Figure 17-28).

Figure 17-28. LempelZiv decoding.

To uncompress the previously compressed file, we could do this:

ObjectInputStream in = new ObjectInputStream(new FileInputStream("words.lz")); PrintWriter out = new PrintWriter("words"); new LempelZiv().decode(in, out);

Since each int takes up four bytes, LempelZiv encoding provides no compression until the encoder starts emitting codes representing strings longer than four characters. On long files, however, it can provide significant compression.

Java provides several classes that perform a variation on LempelZiv encoding, including java.util.zip.ZipInputStream, java.util.zip.GZIPInputStream, and java.util.jar.JarInputStream. We won't discuss these in detail.

Exercises