Efficient and Compact Representations of Some Non-Canonical Prefix-Free Codes
Antonio Fariña, Travis Gagie, 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 characters. In this paper
we first show how, given a probability distribution over an alphabet of
s characters, we can store a nearly optimal alphabetic
prefix-free code in o(s) bits such that we can encode and
decode any character in constant time. We then consider a kind of code
introduced recently to reduce the space usage of wavelet matrices (Claude,
Navarro, and Ordóñez, Information Systems, 2015). They
showed how to build an optimal prefix-free code such that the codewords'
lengths are non-decreasing when they are arranged such that their reverses are
in lexicographic order. We show how to store such a code in O(s log L +
2^(e L)) bits, where L is the maximum codeword
length and e is any positive constant, such that we can encode and decode any character in constant time under reasonable assumptions. Otherwise, we can always encode and decode a codeword
of l bits in time O(l) using O(s log L) bits of space.