×

Bounding the inefficiency of length-restricted prefix codes. (English) Zbl 1012.94008

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.

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
PDFBibTeX XMLCite
Full Text: DOI