A Fast Algorithm for Adaptive Prefix Coding

In this paper we present a new algorithm for adaptive prefix coding. Our algorithm encodes a text S of m symbols in O(m) time, i.e., in O(1) time per symbol. The length of the encoded string is bounded above by (H + 1)m + O(nlog²m) bits where n is the alphabet size and H is the entropy. This is the first algorithm that works in O(m) time and achieves an almost optimal bound on the encoding length in the worst case. Besides that our algorithm does not depend on the explicit tree traversal