Italiano (Italian) English (Inglese)
Friday, 29 March 2024

Technical Reports

Technical Report Details
Authors:Travis Gagie
Yakov Nekrich
Title:Low-Memory Adaptive Prefix Coding
Published on:TR-INF-2008-07-06-UNIPMN
Publisher:Computer Science Department, UPO
Year:2008
URL:http://www.di.unipmn.it...R-INF-2008-07-06-UNIPMN.pdf
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