Sorry, you need to enable JavaScript to visit this website.

Simple Worst-Case Optimal Adaptive Prefix-Free Coding

Citation Author(s):
Travis Gagie
Submitted by:
Travis Gagie
Last updated:
7 March 2022 - 1:03am
Document Type:
Document Year:
Travis Gagie


Gagie and Nekrich (2009) gave an algorithm for adaptive prefix-free coding that, given a string $S [1..n]$ over an alphabet of size $\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.

0 users have voted: