Italiano (Italian) English (Inglese)
venerdì, 29 marzo 2024

Rapporti Tecnici

Dettagli rapporto tecnico
Autori:Travis Gagie
Yakov Nekrich
Titolo:Low-Memory Adaptive Prefix Coding
Apparso su:TR-INF-2008-07-06-UNIPMN
Editore:Computer Science Department, UPO
Anno:2008
URL:http://www.di.unipmn.it...R-INF-2008-07-06-UNIPMN.pdf
Sommario: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