Decoding Prefix Codes
Mike Liddell
Department of Computer Science and Software Engineering,
The University of Melbourne,
Victoria 3010, Australia.
Alistair Moffat
Department of Computer Science and Software Engineering,
The University of Melbourne,
Victoria 3010, Australia.
Status
Software Practice and Experience, 36(15):1687-1710, December 2006.
Parts of this paper appeared in preliminary form in the Proceedings
of the 2003 IEEE Data Compression Conference, Snowbird Utah, April
2002, pages 392-401.
Abstract
Minimum-redundancy prefix codes have been a mainstay of research and
commercial compression systems since their discovery by David Huffman
more than 50 years ago.
In this experimental evaluation we compare techniques for decoding
minimum-redundancy codes, and quantify the relative benefits of
recently-developed restricted codes that are designed to accelerate
the decoding process.
We find that table-based decoding techniques offer fast operation,
provided that the size of the table is kept relatively small; and
that approximate coding techniques can offer higher decoding rates
than Huffman codes, with varying degrees of loss of compression
effectiveness.
Full text
http://dx.doi.org/10.1002/spe.741.