Efficient Approximate Adaptive Coding


Andrew Turpin
Department of Computer Science, The University of Melbourne, Parkville 3052, Australia.

Alistair Moffat
Department of Computer Science, The University of Melbourne, Parkville 3052, Australia.


Status

Proc. 1997 IEEE Data Compression Conference, Snowbird, Utah, March 1997, pages 357-366.

Summary

The notion of approximate minimum-redundancy coding is introduced, in which a minimum-redundancy code is calculated for an approximate probability distribution. The characteristics of one particular class of approximate probability distribution allow extremely fast calculation of the minimum-redundancy code, and we describe a mechanism that uses this fast recalculation method in a pseudo-adaptive coder. Analysis is given that bounds both the compression loss due to the use of approximate probabilities and the time taken by the recalculations. Experimental results are given that show the new method to be substantially faster than traditional fully-adaptive minimum-redundancy coding, with negligible compression deterioration.

Keywords

Huffman code, prefix-free code, minimum-redundancy code, adaptive coding, dynamic coding.