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.