A common complaint about adaptive prefix coding is that it is much slower than static prefix coding. Karpinski and Nekrich recently took an. important step towards resolving this: they gave an adaptive Shannon coding algorithm that encodes each character in O(1) amortized time and decodes it in O(logH+1) amortized time, where H is the empirical entropy of the input string s. For comparison, Gagie's adaptive Shannon coder and both Knuth's and Vitter's adaptive Huffman coders all use Θ(H+1) amortized time for each character. In this paper we give an adaptive Shannon coder that both encodes and decodes each character in O(1) worst-case time. As with both previous adaptive Shannon coders, we store s in at most (H+1)|s|+o(|s|) bits. We also show that this encoding length is worst-case optimal up to the lower order term. In short, we present the first algorithm for adaptive prefix coding that encodes and decodes each character in optimal worst-case time while producing an encoding whose length is also worst-case optimal.
展开▼
