com.mhhe.clrs2e
Class Huffman

java.lang.Object
  |
  +--com.mhhe.clrs2e.Huffman

public class Huffman

extends java.lang.Object

Implements Huffman's algorithm as described in Section 16.3 of Introduction to Algorithms, Second edition.

Nested Class Summary

private static class	Huffman.InternalNode Inner class for an internal node in a Huffman tree.
private static class	Huffman.Node Inner class for a node in a Huffman tree.
static class	Huffman.PrefixCodeItem Inner class for an item in a prefix code.

Field Summary

private Huffman.Node

root The root of the Huffman tree.

Constructor Summary

Huffman(Huffman.PrefixCodeItem[] items)
Creates a Huffman tree from an array of PrefixCodeItem.

Method Summary

private Huffman.Node	constructTree(Huffman.PrefixCodeItem[] items) Creates a Huffman tree from an array of PrefixCodeItem.
java.lang.String	decode(int[] encoding, int n) Decodes an encoded string, where the encoding is bits packed into an array of int.
java.lang.String	decode(java.lang.String encoding) Decodes an encoded string, where the encoding is a String consisting of 0s and 1s.
private void	encodeLeaves(Huffman.Node x, java.lang.String code) Labels all leaves in a subtree with their appropriate codewords.
private int	getBit(int[] array, int i) Returns a specific bit in an array of int.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

root

private Huffman.Node root

The root of the Huffman tree.

Constructor Detail

Huffman

public Huffman(Huffman.PrefixCodeItem[] items)

Creates a Huffman tree from an array of PrefixCodeItem. Sets the instance variable root to reference the root of this tree, and stores the codewords into all the PrefixCodeItems at the leaves of the tree.

Parameters:

items - The array of PrefixCodeItem.

Method Detail

constructTree

private Huffman.Node constructTree(Huffman.PrefixCodeItem[] items)

Creates a Huffman tree from an array of PrefixCodeItem. Implements the Huffman procedure from page 388.

Parameters:

items - The array of PrefixCodeItem.

Returns:

The root of the Huffman tree.

encodeLeaves

private void encodeLeaves(Huffman.Node x,
                          java.lang.String code)

Labels all leaves in a subtree with their appropriate codewords.

Parameters:

x - Root of the subtree.

code - x's codeword, which is a prefix of all codewords for leaves within the subtree rooted at x.

decode

public java.lang.String decode(java.lang.String encoding)

Decodes an encoded string, where the encoding is a String consisting of 0s and 1s.

Parameters:

encoding - The encoded string, assumed to consist only of 0s and 1s.

Returns:

The decoded string.

decode

public java.lang.String decode(int[] encoding,
                               int n)

Decodes an encoded string, where the encoding is bits packed into an array of int.

Parameters:

encoding - The encoded string, as bits packed into an array of int.

n - The total number of bits in the encoding.

Returns:

The decoded string.

getBit

private int getBit(int[] array,
                   int i)

Returns a specific bit in an array of int.

Parameters:

array - The array of int.

i - Which bit we want.

Returns:

The ith bit of the array.