Bounding the inefficiency of length-restricted prefix codes

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms in computer science (68W99) Prefix, length-variable, comma-free codes (94A45)

Review text

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.

Recommendations

Cited in

(22)

This page was built for publication: Bounding the inefficiency of length-restricted prefix codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5953598)