Bounding the inefficiency of length-restricted prefix codes (Q5953598)

Comparisons between the average length \(A\) of an optimal prefix code and the average length \(A_L\) of an optimal \(L\)-restricted prefix code are presented. It has been proved that: if \(L=\lceil \log n\rceil\) then \(A_L-A<\lceil \log n\rceil-1\); if \(L>\lceil\log n\rceil\) then \(A_L-A<1/\psi^{L-\lceil\log(n+\lceil\log n\rceil-L)\rceil-1}\), where \(\psi\) is the golden ratio and \(n\) is the number of elements of the alphabet \(\Sigma\). For \(\lceil\log n\rceil < L \leq n/2\) the bound is asymptotically tight. For \(L\geq \lceil\log n\rceil+11\) the bound guarantees that \(A_L-A<0.01\). Additionally, an \(O(n)\) time and space \(1/\psi^{L-\lceil\log(n+\lceil\log n\rceil-L)\rceil-1}\)-approximative algorithm to construct \(L\)-restricted prefix codes is presented.