Huffman Trees

Below is an applet for drawing a Huffman tree for a given string.

It is possible, for a variety of reasons, that the above applet might not run on your browser. For this reason (or others), you might wish to download the applet and run it as an application. As long as you have the Java^TM SE Runtime Environment (which can be downloaded from the Oracle® Software Downloads page) installed, there are two ways to do this:

The simplest way to install the program on your machine is to click here to launch the program as a stand-alone application.
If you want to install the program manually, you will first need to download viewer.jar (39K - more information on viewer.jar). Then you will need to download huffman.jar (21K) to the same directory. From that directory, you may run the program by issuing the command:
```
java -jar huffman.jar
```
On some operating systems, you may also be able to run the program by double-clicking the icon for huffman.jar.

Usage

The input consists of a string provided either as text entered in the text field or as the contents of a specified file (the latter option is probably prohibited by the browser if the program is being run as an applet). Based upon this input, a Huffman tree is generated. This tree describes a varying-length binary encoding for each character in the input string such that the length of the encoded string is minimized. The Huffman tree is displayed, along with a table giving, for each character in the string, its original encoding in hexadecimal (this helps to identify non-printing characters), its binary Huffman code, and its number of occurrences in the string. The Huffman code actually describes the path from the root of the tree to the node containing the encoded character: a 0 represents an edge to a left child, and a 1 represents an edge to a right child.

The table is initially sorted, first in nonincreasing order of number of occurrences, then in nondecreasing order of length of Huffman code, then in nondecreasing order of Huffman code. Using the Sort menu, the user can choose how the table is sorted. A stable sorting algorithm is used, so that if the table is first sorted by one key then another, the result will have the second key as primary key, and the first key as secondary key.

Font characteristics may be changed using the Font menu.

Error Messages

The following error messages may be displayed by the program:

Security Error Access to the file system is prohibited.
This message occurs when the runtime environment does not allow the program access to the local file system. The most common cause is pressing the "Choose File" button when the program is run as an applet. Most browsers do not allow applets access to the local file system.
Load Error Package edu.ksu.cis.viewer not found.
This message occurs when an attempt is made to draw the tree, but the runtime system cannot find the package edu.ksu.cis.viewer. The most probable cause is that the program is run as a stand-alone application without Web Start (see "Manual download" above), but the file viewer.jar has not been downloaded to the same directory as huffman.jar.
I/O Error
This message occurs when any error occurs while the program is interacting with the local file system; for example, the name of a nonexistent file is given. The cause of the error is briefly described in the message.

Source Files

viewer-src.zip - source for viewer.jar (35K)
huffman-src.zip - source for huffman.jar (10K)

Last updated November 25, 2010.

Rod Howell (rhowell@ksu.edu)

Oracle and Java are registered trademarks of Oracle and/or its affiliates. Other names may be trademarks of their respective owners.