The Minimum-Redundancy (Huffman) Coding Page


Software

Source code for the minimum-redundancy encoding and decoding routines described by Andrew Turpin and Alistair Moffat in the papers "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.

Note also a recent survey paper about Huffman Coding, Computing Surveys, 2019, to appear.

Source code: shuff-1.1.tar.gz, February 2002, written by Andrew Turpin, aht@csse.unimelb.edu.au. 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, see http://people.eng.unimelb.edu.au/ammoffat/arith_coder/.

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, described below.


Books

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, February 2002. 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

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 from. 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 Moffat
alistair / csse.unimelb.edu.au
February 13, 2002; April 11, 2004; January 13, 2013

Mandatory disclaimer: 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.