###
Fast and Compact Prefix Codes

####
Travis Gagie, Gonzalo Navarro, and Yakov Nekrich

It is well known that, given a probability distribution over *n* characters,
in the worst case it takes *Theta(n log n)* bits to store a prefix code
with minimum expected codeword length. However, in this paper we first show
that, for any 0< *e* <1/2 with *1/e = O(polylog(n)*, it
takes *O(n log log (1/e))* bits to store a prefix code with
expected codeword length within *e* of the minimum. We then show that,
for any constant *c > 1*, it takes *O(n^(1/c) log n)* bits to store a
prefix code with expected codeword length at most *c* times the minimum. In
both cases, our data structures allow us to encode and decode any character in
*O(1)* time.