data compression link collection

Adaptive Huffman Coding

Traditional Huffman Coding uses a static dictionary, which means each item in the file is encoded the same way. Typical implementations send the encoding table to the decoder as part of the encoded file. Adaptive Huffman coding modifies the table as characters are encoded, which allows the encoder to adapt to changing conditions in the input data. Adaptive decoders don’t need a copy of the table when decoding, they start with a fixed decoding table and update the table as characters are read in.

Adaptive Huffman Compression

C# implementation of adaptive Huffman coding. Implements both the FGK and Vitter algorithm variations. Compression provided through two public classes, AdaptiveHuffmanProvider and AdaptiveHuffmanStream. Good compression ratios for text-based data

* * * * *

Posted in April 25th, 2004

A Memory-Efficient Huffman Adaptive Coding Algorithm for Very Large Sets of Symbols

This paper describes an adaptive Huffman scheme that is designed to work with large numbers of symbols - at least that’s what the abstract says. The web page indicates that there are executables in the archive, but all I see is a Word document.


Posted in March 10th, 2003

David’ Scott’s Bijectified Vitter Adaptive Compression

David Scott presents an implementation of Vitter’s dynamic Huffman compressor, adapted so that it is bijective. Don’t know what bijective means? Check out David’s home page for more details.


Posted in December 9th, 2002

Design and Analysis of Dynamic Huffman Codes

J. S. Vitter. “Design and Analysis of Dynamic Huffman Codes,” Journal of the ACM, 34(4), October 1987, 825-845. Full paper in PDF and Postscript format.

* * *    

Posted in April 7th, 2002

ALGORITHM 673 Dynamic Huffman Coding

Jeff Vitter’s Pascal implementation of his Adaptive Huffman algorithm. Naturally, this ACM submission is documented in a somewhat academic fashion.

* * * *  

Posted in April 7th, 2002

Video and Audio Compression

Class notes on lossless compression algorithms. Quick info on Huffman, Adaptive Huffman, and LZW.

* * * *  

Posted in February 26th, 2002

David’s Compression Page

This page has a some Huffman compression code that has been adapted to implement a unique property that author refers to as one to one compression. In a nutshell, this property means that for any file X, F( F’( X ) ) == X. (F is either the compressor or decompressor, and F’ is its opposite number.)This is definitely not the case for most conventional compression algorithms.

* * * * *

Posted in December 17th, 1999

Adaptive Huffman Encoding

A library to perform adpative Huffman coding as described by Knuth in J. Alg. Nice clean looking C source code.

This link continues to be one of the most popular links at Reader Karl M. had this comment about the page: The program has a few problems converting from one-based to zero-based arrays. The code for incorporating the last symbol grabs an extra input bit, but since this is usually the EOT symbol, the bug doesn’t always cause problems..

* * * *  

Posted in December 16th, 1999

Charles Bloom’s Adaptive Huffman Program

This is a fairly small C program that was developed on the Amiga.

Note: I’m not sure why, but this page gets a very high number of ratings, nearly all very favorable, although Kate W. did claim: Parts missing from the source code, can’t build.

* * * *  

Posted in December 16th, 1999

Adaptive Huffman Coding

A nice description of Adaptive Huffman Coding, as seen through a couple of different algorithms. I believe this is part of a survey paper by Debra A. Lelewer and Daniel S. Hirschberg.

* * * * *

Posted in November 10th, 1999

Statistical Coders

A group of statistical coders from Charles Bloom. This includes several different entropy encoders, including Huffman, Adaptive Huffman, CACM Arithmetic coding, and a Skew Coder.

* * * *  

Posted in November 6th, 1999

The Lossless Compression (Squeeze) Page

This page is designed made to teach people about Lossless compression algorithms through the use of text graphics and Java Applets! Dominik Szopa has created pages that demonstrate Huffman, Adaptive Huffman, and LZW compression.

DCL reader SF has this to say: While the site itself is rather quick, it’s disorganized…the Java applets really don’t show what’s going on at all. They show only the external effects…This site has definate potential, and I do recommend people see it. However, it’s also got a ways to go yet. .

* * * *  

Posted in December 24th, 1998