  Gagie and Nekrich (2009) gave an algorithm for adaptive prefix-free coding
that, given a string $S [1..n]$ over the alphabet $\{1, \ldots, \sigma\}$ with
$\sigma = o (n / \log^{5 / 2} n)$, encodes $S$ in at most $n (H + 1) + o (n)$
bits, where $H$ is the empirical entropy of $S$, such that encoding and
decoding $S$ take $O (n)$ time. They also proved their bound on the encoding
length is optimal, even when the empirical entropy is high. Their algorithm is
impractical, however, because it uses complicated data structures. In this
paper we give an algorithm with the same bounds, except that we require $\sigma
= o (n^{1 / 2} / \log n)$, that uses no data structures more complicated than a
lookup table. Moreover, when Gagie and Nekrich's algorithm is used for optimal
adaptive alphabetic coding it takes $O (n \log \log n)$ time for decoding, but
ours still takes $O (n)$ time.
