Performance of LZ algorithms on individual sequences
Paul C. Shields · IEEE Transactions on Information Theory · 1999
The performance of three versions of the Lempel-Ziv (1976) algorithm on individual sequences is investigated. It is shown that as the restart length goes to infinity, each compresses an individual sequence as well as any block-to-variable finite-state information lossless algorithm, and that the same conclusion holds for sliding-window LZ as the window width goes to infinity. Examples are given showing that an infinite-memory version outperforms such finite-memory forms and that such finite-memory forms can compress more than the Ziv (1978) entropy, which is the best compression attainable by finite-state block-to-block codes that have vanishing probability of error.