The Minimum-Redundancy (Huffman) Coding Page
Source code for the minimum-redundancy encoding and decoding
routines described by
Andrew Turpin and Alistair Moffat in
"On the Implementation of Minimum-Redundancy Prefix Codes",
IEEE Transactions on Communications, 45(10):1200-1207, October 1997, and
"Housekeeping for Prefix Coding",
IEEE Transactions on Communications, 48(4):622-628, April 2000.
Source code: shuff-1.1.tar.gz, February 2002,
written by Andrew Turpin, email@example.com.
A small bug was fixed in February 2002 to make the current version shuff-1.1.
Manual page PDF, 7 kB/Postscript, 12 kB/Source, 4 kB.
A suite of arithmetic coding routines is also available,
Another paper --
"In-Place Calculation of Minimum-Redundancy Codes",
Proc. 1995 Workshop on Algorithms and Data Structures,
Kingston, Ontario, August 1995 (LNCS volume 955), pages 393-402 --
describes how to efficiently calculate Huffman codeword lengths.
A further technique appears in the "Managing Gigabytes" book,
If compression programs are of interest to you, so too will be this
book: Compression and
Coding Algorithms by Alistair Moffat and Andrew Turpin,
Kluwer Academic Publishers, Boston,
It describes in detail the various mechanisms used in shuff.
An alternative book that includes coverage of compression methods at
a higher level, and also information retrieval techniques (read: web
search engines) is Managing
Gigabytes: Compressing and Indexing Documents and Images by
Ian H. Witten, Alistair Moffat, and Timothy C. Bell,
Morgan Kaufmann, San Francisco, 1999.
Students, you may well have arrived at this page because you searched
for "Huffman coding" at Google, and have a programming task to carry
out, quite possibly for class credit.
Rest assured that your instructor also knows about this page, and
will quickly be able to pick where your "borrowed" your software
And if your instructor doesn't know about this page they won't
understand your software either -- the techniques in this software
are innovative, original, and sufficently unique that they have our
fingerprints all over, through, and under them.
Really, if you can't do the assigned programming project without
resorting to the web to look for free code, then you shouldn't be
doing the subject.
alistair / csse.unimelb.edu.au
February 13, 2002; April 11, 2004;
January 13, 2013
This page, its content and style, are the responsibility of the
author and do not necessarily
represent the views, policies, or opinions of The University of Melbourne.