Low-Memory Adaptive Prefix Coding

Details Low-Memory Adaptive Prefix Coding Low-Memory Adaptive Prefix Coding

2008-11-21

arxiv.org/abs/0811.3602v1

Computer Science

Data Structures and Algorithms

10 pages

Scientific paper

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(\sigma^{1 / \lambda + \epsilon}) $ bits of space for any constants $\eps>0$, $\lambda>1$, and encodes the string of symbols in $O(\log \log \sigma)$ time per symbol \emph{in the worst case}, where $\sigma$ is the size of the alphabet. The upper bound on the encoding length is $\lambda n H (s) +(\lambda \ln 2 + 2 + \epsilon) n + O (\sigma^{1 / \lambda} \log^2 \sigma)$ bits.

Affiliated with

Also associated with

No associations

Rating

Low-Memory Adaptive Prefix Coding does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Low-Memory Adaptive Prefix Coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Low-Memory Adaptive Prefix Coding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-163805