Low-Memory Adaptive Prefix Coding
| dc.creator | Gagie, Travis | |
| dc.creator | Karpinski, Marek | |
| dc.creator | Nekrich, Yakov | |
| dc.date | 2008-11-21 | |
| dc.date.accessioned | 2026-07-07T10:20:10Z | |
| dc.date.available | 2026-07-07T10:20:10Z | |
| dc.description | 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 $\eps>0$, $λ>1$, and encodes the string of symbols in $O(\log \log σ)$ time per symbol \emph{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. | |
| dc.description | 10 pages | |
| dc.identifier | https://arxiv.org/abs/0811.3602 | |
| dc.identifier | http://arxiv.org/abs/0811.3602 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/174763 | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | Low-Memory Adaptive Prefix Coding | |
| dc.type | text |