Enhanced Variable-Length Codes: Improved Compression with Efficient Random Access
Citations Over TimeTop 10% of 2014 papers
Abstract
We investigate the usage of the wavelet tree and the rank/select-dictionary data structures on hybrid-structured variable-length codes, which represent an integer in the form of a unary code section followed by a binary section. We propose to handle unary and binary partitions as separate streams and create wavelet trees or R/S dictionaries over the unary streams, which grants us the opportunity to directly access any codeword. Particularly concentrating on Elias and Rice schemes, we introduce several solutions that (i) improve the compression significantly, and (ii) provide random access in constant or logarithmic time. Experiments are conducted to compare the performances of the proposed codes against Elias/Rice schemes and more recent state-of-the-art codings such as Simple9, PForDelta,DACs, and improved-AC techniques. We observed that the newly introduced methods outperform the original Elias/Rice codecs by approximately 30% and the others by approximately 10% in terms of compression ratios. The methods described in this study are generic and may further be extended to some other hybrid structure (unary/binary) variable-length codes as well.
Related Papers
- → Generalized Unary Coding(2015)21 cited
- → Odd weight symmetry in some binary codes (Corresp.)(1977)3 cited
- → Spread Unary Coding(2014)1 cited
- Pdf417 Two-dimension bar code Coding Technology Research(2012)
- → A Variable-to-Fixed Length Lossless Source Code Attaining Better Performance than Tunstall Code in Several Criterions(2017)