Editing LZ77 and LZ78 (section)

==Theoretical efficiency==
In the second of the two papers that introduced these algorithms they are analyzed as encoders defined by finite-state machines. A measure analogous to [[information entropy]] is developed for individual sequences (as opposed to probabilistic ensembles). This measure gives a bound on the [[data compression ratio]] that can be achieved. It is then shown that there exists finite lossless encoders for every sequence that achieve this bound as the length of the sequence grows to infinity. In this sense an algorithm based on this scheme produces asymptotically optimal encodings. This result can be proven more directly, as for example in notes by [[Peter Shor]].<ref>{{cite web
| url=https://math.mit.edu/~shor/PAM/lempel_ziv_notes.pdf
| title=Lempel–Ziv notes
| author=Peter Shor
| author-link=Peter Shor
| date=2005-10-14
| access-date=2014-11-09
| archive-date=28 May 2021
| archive-url=https://web.archive.org/web/20210528171521/http://www-math.mit.edu/~shor/PAM/lempel_ziv_notes.pdf
}}</ref>

Formally, (Theorem 13.5.2 <ref>{{Cite book |last=Cover |first=Thomas M. |title=Elements of information theory |last2=Thomas |first2=Joy A. |date=2006 |publisher=Wiley-Interscience |isbn=978-0-471-24195-9 |edition=2nd |location=Hoboken, N.J}}</ref>).

{{Math theorem|name=LZ78 is universal and entropic|note=|math_statement=

If <math display="inline">X</math> is a binary source that is stationary and ergodic, then <math display="block">\limsup_n \frac 1n l_{LZ78}(X_{1:n}) \leq h(X)</math> with probability 1. Here <math display="inline">h(X)</math> is the entropy rate of the source.
}}Similar theorems apply to other versions of LZ algorithm.