Length-Restricted Coding Using Modified Probability Distributions
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
Proc. 24th Australasian Computer Science Conference, Gold Coast, Australia,
February 2001, 117-124.
Abstract
The use of data compression has long been a central part of text
databases and fast communication protocols.
In many contexts, effective compression techniques use a minimum
redundancy prefix code.
However, if the length of a codeword exceeds the machine word size,
the decoding routines must be altered and lose efficiency.
To avoid these complications it is desirable to produce a prefix code
with the constraint that no codeword should be longer than some
constant.
Larmore and Hirschberg's Package-Merge Algorithm is a well known
method for producing minimum-redundancy length-restricted prefix
codes, although other methods exist.
In this paper we present an alternative method for length-restricted
coding which calculates an approximate code, rather than an optimal
code, but which can be implemented to operate in linear time.
This approach also has applications to non length-limited coding.