Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2008 Copyright 2008 Universität Bonn, Institut für Informatik, Abt. V
85297

21.11.2008

Low-Memory Adaptive Prefix Coding
Travis Gagie, Marek Karpinski, Yakov Nekrich
[Download PostScript] [Download PDF]

In this paper we study the adaptive prefix coding problem in cases where the size of the input alphabet is large. We present an online prefix coding algorithm that uses O(σ1 / λ + ε) bits of space for any constants ε>0, λ>1, 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 λ n H (s) +(λ ln 2 + 2 + ε) n + O (σ1 / λ log 2 σ) bits.

Last Change: 11/21/08 at 13:35:06
 English
Universität Bonn -> Institut für Informatik -> Abteilung V