THE SLIDING-WINDOW LEMPEL-ZIV ALGORITHM IS ASYMPTOTICALLY OPTIMAL

The sliding-window version of the Lempel-Ziv data-compression algorith m (sometimes called LZ '77) has been thrust into prominence recently. A version of this algorithm is used in the highly successful ''Stacker '' program for personal computers. It is also incorporated into Micros oft's new MS-DOS-6. Although other versions of the Lempel-Ziv algorith m are known to be optimal in the sense that they compress a data sourc e to its entropy, optimality in this sense has never been demonstrated for this version. In this self-contained paper, we will describe the algorithm, and show that as the ''window'' size,'' a quantity which is related to the memory and complexity of the procedure, goes to infini ty, the compression rate approaches the source entropy. The proof is s urprisingly general, applying to all finite-alphabet stationary ergodi c sources.