sam.io
Class Huffman

java.lang.Object
  |
  +--sam.io.Node
        |
        +--sam.io.Huffman

Direct Known Subclasses:

Huffman16, Huffman8

public abstract class Huffman

extends sam.io.Node

Implementation of the auto-adaptive Huffman-tree coding input/output-streams with variable pattern length. This allows for transparent Huffman input/output filtering, like in

 InputStream source = new FileInputStream("foo.dat");
 OutputStream target = new Huffman8().output( new FileOutpuStream("bar.dat") );
 

for compression and similarly

 InputStream source = new Huffman8().input( new FileInputStream("bar.dat") );
 OutputStream target = new FileOutpuStream("foo.dat");
 

See Also:

input(java.io.InputStream), output(java.io.OutputStream), Huffman.Leaf

Nested Class Summary

protected class	Huffman.Leaf Special Node representing a leaf.
protected class	Huffman.LeafInputStream Class for reading leaves from an Huffman-compressed InputStream
protected class	Huffman.LeafOutputStream Class for writing Huffman-compressed leaves to an OutputStream

Constructor Summary

protected	Huffman(int patternWidth) Builds a new generic Huffman tree of specified pattern width.
protected	Huffman(int patternWidth, int granularity) Creates a new well-balanced Huffman tree.

Method Summary

protected Huffman.Leaf	get(int value) Gets the leaf coding for specified value.
abstract java.io.InputStream	input(java.io.InputStream encodedStream) Stream for decoding huffman-encoded data
boolean	isLeaf() Wether this node is a pure leaf, i.e.
int	longestPath()
static void	main(java.lang.String[] args) Main executable code.
int	numberOfLeaves()
int	numberOfNodes()
java.util.Enumeration	ordered() Gets the enumeration of all nodes that are lighter than this node in decreasing order.
abstract java.io.OutputStream	output(java.io.OutputStream encodedStream) Stream for encoding 8 bits huffman-encoded data
float	ratio()
void	reset() Resets the Huffman tree into a fully well-balanced one.
int	shortestPath()
java.lang.String	toString() Gets a formatted representation of this huffman tree.

Methods inherited from class java.lang.Object

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

Constructor Detail

Huffman

protected Huffman(int patternWidth)

Builds a new generic Huffman tree of specified pattern width.

Parameters:

patternWidth - the pattern width. This can be any positive integer up to 32, but for obvious reasons multiples of 8 shall be of wider use.

Huffman

protected Huffman(int patternWidth,
                  int granularity)

Creates a new well-balanced Huffman tree.

Each of the numberOfPatterns patterns is initially weighted by 1. This is an implementation requirement: a node is required to be strictly heavier than any of its sons, which would not be granted in case of zero-weighted leaves.

Parameters:

granularity - the granularity of the frequency updates. Higher means faster but less accurate (and thus lower compression ratios). In particular, a sequence of at most granularity consecutive bytes will not be compressed.

patternWidth - the pattern width. This can be any positive integer up to 32, but for obvious reasons multiples of 8 shall be of wider use.

Method Detail

main

public static void main(java.lang.String[] args)

Main executable code. This program (de)compresses a file with either 8-bits or 16-bits patterns. Syntax is java sam.Huffman {+|-}{8|16} input output Warning: 16-bits [en|de]coding is extremly slow !

input

public abstract java.io.InputStream input(java.io.InputStream encodedStream)

Stream for decoding huffman-encoded data

output

public abstract java.io.OutputStream output(java.io.OutputStream encodedStream)

Stream for encoding 8 bits huffman-encoded data

numberOfLeaves

public int numberOfLeaves()

Returns:

the total number of leaves of this Huffman tree

numberOfNodes

public int numberOfNodes()

Returns:

the total number of nodes of this Huffman tree

shortestPath

public int shortestPath()

Returns:

the size in bits of the smallest encoded pattern

longestPath

public int longestPath()

Returns:

the size in bits of the largest encoded pattern

ratio

public float ratio()

Returns:

the expected compression ratio associated to this Huffman tree

reset

public void reset()

Resets the Huffman tree into a fully well-balanced one.

get

protected Huffman.Leaf get(int value)

Gets the leaf coding for specified value. Does not update the Huffman tree.

Returns:

the leaf associated to byte value value.

See Also:

Huffman.Leaf.oneMore()

toString

public java.lang.String toString()

Gets a formatted representation of this huffman tree. This is well-suited for debugging but is rather unreadable. This only prints nodes and node the whole tree structure.

Overrides:

toString in class sam.io.Node

ordered

public java.util.Enumeration ordered()

Gets the enumeration of all nodes that are lighter than this node in decreasing order. This is mostly usefull when called from the root node which is the heaviest, i.e. from an Huffman instance.

isLeaf

public boolean isLeaf()

Wether this node is a pure leaf, i.e. if it has no son.