Italiano (Italian) English (Inglese)
Thursday, 22 March 2018

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
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