Paper Info
Title
Bounding the Inefficiency of Length-Restricted Prefix Codes
Abstract
   Abstract. We consider an alphabet Σ= {a 1 ,\ldots,a n } with corresponding symbol probabilities p 1 ,\ldots,p n . For each prefix code associated to Σ , let l i be the length of the codeword associated to a i . The average code length c is defined by c=\sum i=1 n p i l i . An optimal prefix code for Σ is one that minimizes c . An optimal L -restricted prefix code is a prefix code that minimizes c constrained to l i ≤ L for i=1,\ldots,n . The value of the length restriction L is an integer no smaller than \lceil log n \rceil . Let A be the average length of an optimal prefix code for Σ . Also let A L be the average length of an optimal L -restricted prefix code for Σ . The average code length difference ɛ is defined by ɛ=A L -A . Let ψ be the golden ratio 1.618. In this paper we show that ɛ L-\lceil\log (n+\lceil\log n\rceil-L)\rceil-1 when L > \lceil log n \rceil . We also prove the sharp bound ɛ log n \rceil -1 , when L = \lceil log n \rceil . By showing the lower bound 1/(ψ L-\lceil\log n\rceil+2+\lceil\log (n/(n-L))\rceil -1) on the maximum value of ɛ , we guarantee that our bound is asymptotically tight in the range \lceil log n \rceil . When L\geq \lceil log n \rceil +11 , the bound guarantees that ɛ . From a practical point of view, this is a negligible loss of compression efficiency. Furthermore, we present an O(n) time and space 1/ψ L-\lceil\log (n+\lceil\log n\rceil-L)\rceil-1 -approximative algorithm to construct L -restricted prefix codes, assuming that the given probabilities are already sorted. The results presented in this paper suggest that one can efficiently implement length restricted prefix codes, obtaining also very effective codes.
Year
DOI
Venue
2001
10.1007/s00453-001-0060-4
Algorithmica
Keywords
Field
DocType
Key words. Prefix codes,Huffman trees,Approximative algorithm,Compression,Redundancy.
Integer,Approximation algorithm,Binary logarithm,Discrete mathematics,Combinatorics,Binary tree,Prefix,Code word,Prefix code,Mathematics,Bounding overwatch
Journal
Volume
Issue
ISSN
31
4
0178-4617
Citations 
PageRank 
References 
11
0.70
20
Authors
2
Name
Order
Citations
PageRank
Ruy Luiz Milidiú119220.18
Eduardo Sany Laber222927.12