Huffman Trees

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

</COMMENT>

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 JavaTM SE Runtime Environment (which can be downloaded from the Oracle® Software Downloads page) installed, there are two ways to do this:

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:

Source Files


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.