Bounding the Inefficiency of Length-Restricted Prefix Codes

Abstract. We consider an alphabet Σ= {a ₁ ,\ldots,a _n } with corresponding symbol probabilities p ₁ ,\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 ⁿ 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 ɛ < 1/ψ ^{L-\lceil\log (n+\lceil\log n\rceil-L)\rceil-1} when L > \lceil log n \rceil . We also prove the sharp bound ɛ < \lceil 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 < L ≤ n/2 . When L\geq \lceil log n \rceil +11 , the bound guarantees that ɛ < 0.01 . 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.