Data Compression Using an “Imaginary Sliding Window”

Methods of adaptive coding that use the scheme of a sliding window are well known in data compression. In such methods, the code of the next letter $x_t$ is determined by the analysis of the window's contents, i.e., of the word $x_{t-w}x_{t-w+1}\dots x_{t-1}$, where $w\geq 1$ is the window's size. After encoding $x_t$, it is written into the window from the right, and $x_{t-w}$ is removed. The advantages of these methods are the ability to estimate the source statistics accurately enough and a rapid adaptation to the varying statistics. In the paper, we propose a new scheme for organizing the sliding window, where a random element, instead of the left-most one, is removed from the window. This conserves all the properties of the sliding window, but enables one not to keep the window, which in turn allows the memory capacity of the encoder and decoder to be essentially decreased.