Worst-case optimal adaptive alphabetic prefix-free coding

Abstract

We give the first algorithm for adaptive alphabetic prefix-free coding that is worst-case optimal in terms of time and compression when $\ddot{I}ƒ\in o\left(\frac{n^{1/2}}{\log n}\right)$, where $\ddot{I}ƒ$ is the size of the alphabet and $n$ is the length of the input.