Performance of LZ algorithms on individual sequences
The performance of three versions of the Lempel-Ziv (LZ) algorithm on individual sequences is investigated. It is shown that as 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 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 Ziv entropy, which is the best compression attainable by finite-state block-to-block codes that have vanishing probability of error.
data compression lempel-ziv codes source coding