Fast Autocorrelated Context Models for Data Compression
This work addresses the need for more efficient and general data compression techniques, reducing reliance on ad-hoc models for specific data types.
The paper tackles the problem of automatically generating efficient context models for data compression by using the autocorrelation function to identify highly correlated offsets, which improves predictive coding algorithms. The method achieves the highest performance to date on a lossless image compression benchmark.
A method is presented to automatically generate context models of data by calculating the data's autocorrelation function. The largest values of the autocorrelation function occur at the offsets or lags in the bitstream which tend to be the most highly correlated to any particular location. These offsets are ideal for use in predictive coding, such as predictive partial match (PPM) or context-mixing algorithms for data compression, making such algorithms more efficient and more general by reducing or eliminating the need for ad-hoc models based on particular types of data. Instead of using the definition of the autocorrelation function, which considers the pairwise correlations of data requiring O(n^2) time, the Weiner-Khinchin theorem is applied, quickly obtaining the autocorrelation as the inverse Fast Fourier transform of the data's power spectrum in O(n log n) time, making the technique practical for the compression of large data objects. The method is shown to produce the highest levels of performance obtained to date on a lossless image compression benchmark.