Efficient and Compact Representations of Prefix Codes

DOI10.1109/TIT.2015.2452252MaRDI QIDQ2977298zbMATH OpenOpenAlexFDO

Authors Travis Gagie, Yakov Nekrich, Alberto Ordóñez, Gonzalo Navarro

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.3438

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Information theory (general) (94A15)

Abstract: Most of the attention in statistical compression is given to the space used by the compressed sequence, a problem completely solved with optimal prefix codes. However, in many applications, the storage space used to represent the prefix code itself can be an issue. In this paper we introduce and compare several techniques to store prefix codes. Let $N$ be the sequence length and $n$ be the alphabet size. Then a naive storage of an optimal prefix code uses $O(nlogn)$ bits. Our first technique shows how to use $O(nloglog(N/n))$ bits to store the optimal prefix code. Then we introduce an approximate technique that, for any $0<epsilon<1/2$, takes $O(nloglog(1/epsilon))$ bits to store a prefix code with average codeword length within an additive $epsilon$ of the minimum. Finally, a second approximation takes, for any constant $c>1$, $O(n^{1/c}logn)$ bits to store a prefix code with average codeword length at most $c$ times the minimum. In all cases, our data structures allow encoding and decoding of any symbol in $O(1)$ time. We experimentally compare our new techniques with the state of the art, showing that we achieve 6--8-fold space reductions, at the price of a slower encoding (2.5--8 times slower) and decoding (12--24 times slower). The approximations further reduce this space and improve the time significantly, up to recovering the speed of classical implementations, for a moderate penalty in the average code length. As a byproduct, we compare various heuristic, approximate, and optimal algorithms to generate length-restricted codes, showing that the optimal ones are clearly superior and practical enough to be implemented.

Cited in

(14)

• Efficient prefix coding of uncertainty spaces
• Space-efficient Huffman codes revisited
• Robust prefix encoding using lower (2,3) number representation
• A fast algorithm for adaptive prefix coding
• On the size of transducers for bidirectional decoding of prefix codes
• Fast and Compact Prefix Codes
• scientific article; zbMATH DE number 6533775 (Why is no real title available?)
• Fixed-prefix encoding of the integers can be Huffman-optimal
• scientific article; zbMATH DE number 4045195 (Why is no real title available?)
• Three space-economical algorithms for calculating minimum-redundancy prefix codes
• Efficient and compact representations of some non-canonical prefix-free codes
• Efficient and compact representations of some non-canonical prefix-free codes
• Bounding the inefficiency of length-restricted prefix codes
• Efficiency of chain codes to represent binary objects

This page was built for publication: Efficient and Compact Representations of Prefix Codes

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