Fixed data base version of the Lempel-Ziv data compression algorithm

It is demonstrated that a variant of the Lempel-Ziv data compression algorithm where the database is held fixed and is reused to encode successive strings of incoming input symbols is optimal, provided that the source is stationary and satisfies certain conditions (e.g., a finite-order Markov source). A finite memory version of the Lempel-Ziv algorithm compresses (on the average) to about the entropy rate. The necessary memory size depends on the nature of the source.