2008/11/21 by Travis Gagie, Marek Karpiński, Marek Karpinski +4
Computer Science · Engineering · #Advanced Wireless Communication Techniques #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #Error Correcting Code Techniques #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.0811.3602
10 pages
arxiv created 2008/11/21 · openalex publication_date 2008/11/21 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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 / λ log2 σ) bits.