On-Line Adaptive Canonical Prefix Coding with Bounded Compression Loss

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

IEEE Trans. Information Theory, 47(1):88-98, January 2001.

Abstract

Semi-static minimum-redundancy prefix (MRP) coding is fast compared with rival coding methods, but requires two passes during encoding. Its adaptive counterpart, Dynamic Huffman coding, requires only one pass over the input message for encoding and decoding, and is asymptotically efficient. Dynamic Huffman coding is, however, notoriously slow in practice. By removing the restriction that the code used for each message symbol must have minimum redundancy and thereby admitting some compression loss, it is possible to improve the speed of adaptive MRP coding. This paper presents a controlled method for trading compression loss for coding speed by approximating symbol frequencies with a geometric distribution. The result is an adaptive MRP coder that is asymptotically efficient and also fast in practice.