Move-to-front, distance coding, and inversion frequencies revisited

DOI10.1016/j.tcs.2010.04.024zbMath1203.94084OpenAlexW2109122310MaRDI QIDQ982665

Travis Gagie, Giovanni Manzini

Publication date: 7 July 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.04.024

zbMATH Keywords

data compressionempirical entropyBurrows-Wheller transform

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Measures of information, entropy (94A17) Application of orthogonal and other special functions (94A11) Source coding (94A29)

Related Items

The myriad virtues of wavelet trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The myriad virtues of wavelet trees
• A simpler analysis of Burrows-Wheeler-based compression
• Second step algorithms in the Burrows-Wheeler compression algorithm
• When indexing equals compression
• Compressed representations of sequences and full-text indexes
• An analysis of the Burrows—Wheeler transform
• Most Burrows-Wheeler Based Compressors Are Not Optimal
• Boosting textual compression in optimal linear time
• A locally adaptive data compression scheme
• Universal codeword sets and representations of the integers
• Lexical Permutation Sorting Algorithm
• Universal lossless source coding with the Burrows Wheeler transform
• Burrows-Wheeler compression with variable length integer codes
• Inversion Coding
• Nearly Tight Bounds on the Encoding Length of the Burrows-Wheeler Transform
• The Engineering of a Compression Boosting Library: Theory vs Practice in BWT Compression