it.unimi.dsi.compression

Class HuffmanCodec

java.lang.Object

it.unimi.dsi.compression.HuffmanCodec

All Implemented Interfaces:

Codec, PrefixCodec, Serializable

public class HuffmanCodec
extends Object
implements PrefixCodec, Serializable

An implementation of Huffman optimal prefix-free coding.

A Huffman coder is built starting from an array of frequencies corresponding to each symbol. Frequency 0 symbols are allowed, but they will degrade the resulting code.

Instances of this class compute a canonical Huffman code (Eugene S. Schwartz and Bruce Kallick, “Generating a Canonical Prefix Encoding”, Commun. ACM 7(3), pages 166−169, 1964), which can by quickly decoded using table lookups. The construction uses the most efficient one-pass in-place codelength computation procedure described by Alistair Moffat and Jyrki Katajainen in “In-Place Calculation of Minimum-Redundancy Codes”, Algorithms and Data Structures, 4th International Workshop, number 955 in Lecture Notes in Computer Science, pages 393−402, Springer-Verlag, 1995.

We note by passing that this coded uses a CanonicalFast64CodeWordDecoder, which does not support codelengths above 64. However, since the worst case for codelengths is given by Fibonacci numbers, and frequencies are to be provided as integers, no codeword longer than the base-[(5^1/2 + 1)/2] logarithm of 5^1/2 · 2³¹ (less than 47) will ever be generated.

Modifications

1. This class has been modified to define an alternative ctor which exposes the symbol[] in correlated order with the codeWord bitLength[] and the shortest code word in the generated canonical.
2. A method has been added to recreate the PrefixCoder from the shortest code word, the code word length[], and the symbol[].

See Also:

Serialized Form

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	HuffmanCodec.DecoderInputs Class encapsulates the data necessary to reconstruct a CanonicalFast64CodeWordDecoder or recreate the code.

Field Summary

Fields

Modifier and Type	Field and Description
int	size The number of symbols of this coder.

Constructor Summary

Constructors

Constructor and Description
HuffmanCodec(int[] frequency) Creates a new Huffman codec using the given vector of frequencies.
HuffmanCodec(int[] frequency, HuffmanCodec.DecoderInputs decoderInputs) Creates a new Huffman codec using the given vector of frequencies.

Method Summary

Methods

Modifier and Type	Method and Description
CodeWordCoder	coder() Returns a coder for the compression technique represented by this coded.
BitVector[]	codeWords() Returns the vector of prefix-free codewords used by this prefix coder.
Decoder	decoder() Returns a decoder for the compression technique represented by this coded.
static PrefixCoder	newCoder(BitVector shortestCodeWord, int[] length, int[] symbol) (Re-)constructs the canonical huffman code from the shortest code word, the non-decreasing bit lengths of each code word, and the permutation of the symbols corresponding to those bit lengths.
static PrefixCoder	newCoder(HuffmanCodec.DecoderInputs decoderInputs) (Re-)constructs the canonical huffman code from the shortest code word, the non-decreasing bit lengths of each code word, and the permutation of the symbols corresponding to those bit lengths.
int	size() Returns the number of symbols handled by this codec.

Methods inherited from class java.lang.Object

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

Field Detail

size

public final int size

The number of symbols of this coder.

Constructor Detail

HuffmanCodec

public HuffmanCodec(int[] frequency)

Creates a new Huffman codec using the given vector of frequencies.

Parameters:

frequency - a vector of nonnnegative frequencies.

HuffmanCodec

public HuffmanCodec(int[] frequency,
            HuffmanCodec.DecoderInputs decoderInputs)

Creates a new Huffman codec using the given vector of frequencies.

Parameters:

frequency - a vector of non-negative frequencies.

decoderInputs - The inputs necessary to reconstruct a CanonicalFast64CodeWordDecoder will be set on this object.

Method Detail

coder

public CodeWordCoder coder()

Description copied from interface: Codec

Returns a coder for the compression technique represented by this coded.

Specified by:

coder in interface Codec

Specified by:

coder in interface PrefixCodec

Returns:

a coder for the compression technique represented by this codec.

decoder

public Decoder decoder()

Description copied from interface: Codec

Returns a decoder for the compression technique represented by this coded.

Specified by:

decoder in interface Codec

Returns:

a decoder for the compression technique represented by this codec.

size

public int size()

Description copied from interface: Codec

Returns the number of symbols handled by this codec.

Specified by:

size in interface Codec

Returns:

the number of symbols handled by this codec.

codeWords

public BitVector[] codeWords()

Description copied from interface: PrefixCodec

Returns the vector of prefix-free codewords used by this prefix coder.

Specified by:

codeWords in interface PrefixCodec

Returns:

the vector of prefix-free codewords used by this prefix coder.

newCoder

public static PrefixCoder newCoder(HuffmanCodec.DecoderInputs decoderInputs)

(Re-)constructs the canonical huffman code from the shortest code word, the non-decreasing bit lengths of each code word, and the permutation of the symbols corresponding to those bit lengths. This information is necessary and sufficient to reconstruct a canonical huffman code.

Parameters:

decoderInputs - This contains the necessary and sufficient information to recreate the PrefixCoder.

Returns:

A new PrefixCoder instance for the corresponding canonical huffman code.

newCoder

public static PrefixCoder newCoder(BitVector shortestCodeWord,
                   int[] length,
                   int[] symbol)

(Re-)constructs the canonical huffman code from the shortest code word, the non-decreasing bit lengths of each code word, and the permutation of the symbols corresponding to those bit lengths. This information is necessary and sufficient to reconstruct a canonical huffman code.

Parameters:

shortestCodeWord - The code word with the shortest bit length.

length - The bit length of each code word in the non-decreasing order assigned when the code was generated. The length of this array is the #of symbols in the code.

symbol - The permutation of the symbols in the assigned when the canonical huffman code was generated. The length of this array is the #of symbols in the code.

Returns:

A new PrefixCoder instance for the corresponding canonical huffman code.

See Also:

HuffmanCodec.DecoderInputs