Milidiú, R. L.; Laber, E. S. Bounding the inefficiency of length-restricted prefix codes. (English) Zbl 1012.94008 Algorithmica 31, No. 4, 513-529 (2001). 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. Reviewer: Jerzy Żurawiecki (Lublin) Cited in 6 Documents MSC: 94A45 Prefix, length-variable, comma-free codes 68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) 68W99 Algorithms in computer science Keywords:prefix codes; Huffman trees; approximative algorithm; compression; redundancy PDFBibTeX XMLCite \textit{R. L. Milidiú} and \textit{E. S. Laber}, Algorithmica 31, No. 4, 513--529 (2001; Zbl 1012.94008) Full Text: DOI