  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 $\sigma$
symbols, we can store an optimal alphabetic prefix-free code in $\Oh{\sigma
\log L}$ bits such that we can encode and decode any codeword of length $\ell$
in $\Oh{\min (\ell, \log L)}$ time, where $L$ is the maximum codeword length.
With $\Oh{2^{L^\epsilon}}$ further bits, for any constant $\epsilon>0$, we can
encode and decode $\Oh{\log \ell}$ time. We then show how to store a nearly
optimal alphabetic prefix-free code in \(o (\sigma)\) 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 $\Oh{\sigma \log L}$ while maintaining encoding and
decoding times in $\Oh{\ell}$. We also show how, with $\Oh{2^{\epsilon L}}$
further bits, we can encode and decode in constant time. All of our results
hold in the word-RAM model.
