Huffman Coding

Posted on November 8, 2004. Filed under: Computer Science |

In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol (such as a character in a file) where the variable-length code table has been derived in a particular way based on the estimated probability of occurrence for each possible value of the source symbol. It was developed by David A. Huffman while he was a Ph.D. student at MIT, and published in the 1952 paper “A Method for the Construction of Minimum-Redundancy Codes”.

References:
Lossless Compression Algorithms (Entropy Encoding)
http://www.cs.cf.ac.uk/Dave/Multimedia/node207.html

Huffman Coding: A CS2 Assignment

http://www.cs.duke.edu/csed/poop/huff/info/

The Huffman Compression Algorithm
http://www.howtodothings.com/showarticle.asp?article=313

Dynamic Huffman Coder
http://www.geocities.com/malbrain/vitter_c.html
Canonical Huffman Coder Construction
http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&oe=UTF-8&threadm=370afe3d.0303041329.23
f0affe%40posting.google.com
C Library to search over compressed texts
http://butirro.di.unipi.it/~ferrax/CompressedSearch/
Michael Dipperstein’s Huffman Code Page
http://michael.dipperstein.com/huffman/index.html
libhuffman – Huffman encoder/decoder library
http://huffman.sourceforge.net/
Compression and Encryption Sources
http://www.larkin.lanit.ru/compress/compr.htm
Huffman Coding Class
http://codeproject.com/cpp/HandyHuffmanCoding.asp

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.

References:
Design and Analysis of Dynamic Huffman Codes
http://www.cs.duke.edu/~jsv/Papers/catalog/node60.html
Adaptive Huffman Encoding
http://www.xcf.berkeley.edu/~ali/K0D/Algorithms/huff/
http://www.ics.uci.edu/~dan/pubs/DC-Sec4.html

Advertisements

Make a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Liked it here?
Why not try sites on the blogroll...

%d bloggers like this: