| Abstract: | In this paper we study the adaptive prefix coding problem in cases when the size of the input alphabet is large, e.g., character-based compression of Chinese or word-based compression of English. We present an online prefix coding algorithm that uses O(σ1/λ+ϵ ) bits of space for any ε > 0 and encodes the string of symbols in O(log log σ) time per symbol in the worst case, where σ is the size of the alphabet.
The upper bound on the encoding length is λnH (s) + (λ ln 2 + 2 + ϵ)n + O(σ1/λ log2 σ) bits |
