Fast and Compact Prefix Codes

Details Fast and Compact Prefix Codes Fast and Compact Prefix Codes

2009-05-19

arxiv.org/abs/0905.3107v1

Computer Science

Data Structures and Algorithms

Scientific paper

It is well-known that, given a probability distribution over $n$ characters, in the worst case it takes (\Theta (n \log n)) bits to store a prefix code with minimum expected codeword length. However, in this paper we first show that, for any $0<\epsilon<1/2$ with (1 / \epsilon = \Oh{\polylog{n}}), it takes $\Oh{n \log \log (1 / \epsilon)}$ bits to store a prefix code with expected codeword length within $\epsilon$ of the minimum. We then show that, for any constant (c > 1), it takes $\Oh{n^{1 / c} \log n}$ bits to store a prefix code with expected codeword length at most $c$ times the minimum. In both cases, our data structures allow us to encode and decode any character in $\Oh{1}$ time.

Affiliated with

Also associated with

No associations

Rating

Fast and Compact Prefix Codes 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 Fast and Compact Prefix Codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast and Compact Prefix Codes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-699951