Efficient and Compact Representations of Some Non-Canonical Prefix-Free Codes
Antonio Fariña, Travis Gagie, Szymon Grabowski, Giovanni Manzini,
Gonzalo Navarro, and Alberto Ordóñez
For many kinds of prefix-free codes there are efficient and compact
alternatives to the traditional tree-based representation. Since these put
the codes into canonical form, however, they can only be used when we can
choose the order in which codewords are assigned to symbols. In this paper we
first show how, given a probability distribution over an alphabet of
s symbols, we can store an optimal alphabetic prefix-free code in
O(s log L) bits such that we can encode and decode any codeword
of length l in O(min (e, log L)) time, where
L is the
maximum codeword length. With O(2^(L^e)) further bits, for any
constant e > 0, we can encode and decode O(log l) time.
We then show how to store a nearly optimal alphabetic prefix-free code in
o(s) bits such that we can encode and decode in constant time. We also
consider a kind of optimal prefix-free code introduced recently where the
codewords' lengths are non-decreasing if arranged in lexicographic order of
their reverses. We reduce their storage space to O(s log L)
while maintaining encoding and decoding times in O(l). We also show
how, with O(2^(e L)) further bits, we can encode and decode in constant
time. All of our results hold in the word-RAM model.