Length-restricted coding using modified probability distributions
Mike Liddell, Alistair Moffat · 2001
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. L.L. Larmore and D.S. Hirschberg's (1990) 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-restricted coding.