Move-to-front, distance coding, and inversion frequencies revisited
type: Item
instance of: scholarly article
title: Move-to-front, distance coding, and inversion frequencies revisited
zbMATH Open document ID: 1203.94084
author: Travis Gagie
author: Giovanni Manzini
published in: Theoretical Computer Science
publication date: 2010-07-07T00:00:00Z
review text: The authors provide a first-time analysis of the move-to-front, distance coding and inversion frequencies by establishing upper and lower bounds on their compression ratios. These bounds are entropy-only since they do not involve non-constant overheads. Furthermore, the techniques establish new facets of their practical behaviour and provide mechanisms for their improved performance.
reviewed by: Richard A. Mollin
Mathematics Subject Classification ID: 94A29
Mathematics Subject Classification ID: 68P30
Mathematics Subject Classification ID: 94A11
Mathematics Subject Classification ID: 94A17
zbMATH DE Number: 5731739
zbMATH Keywords: data compression
zbMATH Keywords: Burrows-Wheller transform
zbMATH Keywords: empirical entropy
MaRDI profile type: Publication
full work available at URL: j.tcs.2010.04.024
OpenAlex ID: W2109122310
cites work: Inversion Coding
cites work: Lexical Permutation Sorting Algorithm
cites work: A locally adaptive data compression scheme
cites work: Q4023085
cites work: Second step algorithms in the Burrows-Wheeler compression algorithm
cites work: Universal lossless source coding with the Burrows Wheeler transform
cites work: Universal codeword sets and representations of the integers
cites work: Burrows-Wheeler compression with variable length integer codes
cites work: The Engineering of a Compression Boosting Library: Theory vs Practice in BWT Compression
cites work: The myriad virtues of wavelet trees
cites work: Boosting textual compression in optimal linear time
cites work: When indexing equals compression
cites work: Q4471381
cites work: Nearly Tight Bounds on the Encoding Length of the Burrows-Wheeler Transform
cites work: A simpler analysis of Burrows-Wheeler-based compression
cites work: Most Burrows-Wheeler Based Compressors Are Not Optimal
cites work: Q5708460
cites work: An analysis of the Burrows—Wheeler transform
cites work: Compressed representations of sequences and full-text indexes
cites work: Q3893804
cites work: Q4945084
DOI: 10.1016/J.TCS.2010.04.024
Recommended article: Move-to-Front, Distance Coding, and Inversion Frequencies Revisited
Recommended article: Q4531565
Recommended article: Decoding Frequency Permutation Arrays Under Chebyshev Distance
Recommended article: Coding Theory: A General Framework and Two Inverse Problems
Recommended article: Distance spectra of convolutional codes over partial-response channels
Recommended article: A Revisit to Ordered Statistics Decoding: Distance Distribution and Decoding Rules
Recommended article: Q5749238
Recommended article: On the spectrum of distances of a multilevel code, decoded by a multistage decoder
Recommended article: Inversion Coding
Recommended article: Invertible Low-Divergence Coding
description: scientific article; zbMATH DE number 5731739