Redundancy of the Lempel-Ziv codes
Serap A. Savari · 2002
For unifilar, Markov sources, we demonstrate that the redundancy of encoding the first n letters of the source output with the Lempel-Ziv (1977) string matching code (LZ '77) is O((ln ln n)/(ln n)) and the redundancy with the Lempel-Ziv incremental parsing rule (LZ '78) is O(1/(ln n)); in both cases, we upper bound the exact form of convergence.