Efficient and Compact Representations of Prefix Codes
Travis Gagie, Gonzalo Navarro, Yakov Nekrich, and Alberto Ordóñez
Most of the attention in statistical compression is given to the space used
by the compressed sequence, a problem completely solved with optimal prefix
codes. However, in many applications, the storage space used to represent the
prefix code itself can be an issue. In this paper we introduce
and compare several techniques to store prefix codes. Let N be the sequence
length and n be the alphabet size. Then a naive storage of an optimal prefix
code uses O(n log n) bits. Our first technique shows how to use
O(n log log (N/n)) bits to store the optimal prefix code. Then we introduce
an
approximate technique that, for any 0 < e < 1/2, takes
O(n log log (1/e)) bits to store a prefix code with average
codeword length within an additive e of the minimum. Finally, a
second approximation takes, for any constant c > 1,
O(n^(1/c) log n)
bits to store a prefix code with average codeword length at most c times
the minimum. In all cases, our data structures allow encoding and decoding of
any symbol in O(1) time. We experimentally compare our new techniques with
the state of the art, showing that we achieve 6-8-fold space reductions,
at the price of a slower encoding (2.5-8 times slower) and decoding (12-24
times slower). The approximations further reduce this space and improve the
time significantly, up to recovering the speed of classical implementations,
for a moderate penalty in the average code length.
As a byproduct, we compare various heuristic, approximate, and
optimal algorithms to generate length-restricted codes, showing that the
optimal ones are clearly superior and practical enough to be implemented.