Of Lempel-Ziv-Welch Parses with Refillable Gaps.

We consider gapped variants of classical data compression paradigms (Ziv, J. and Lempel, A.,1977, 1978; Welch, T.A., 1984). In the original algorithm, phrases are identified and stored in a dictionary on-the-fly as the text-file is scanned. The entries in the dictionary are then matched against the incoming string, thereby determining the next codeword, and this gives the method an inherently linear-time implementation. In our variants, the phrases used in compression are selected among suitably chosen strings of intermittently solid and wild characters produced by the autocorrelation of the source-string, in a way that still preserves linearity of time. At the receiver, gaps can be filled back exactly, interpolated, or left blank, so that lossless, as well as lossy, implementations are possible. However, the focus of the paper is on lossy variants.