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 compression ratio that can be achieved. It is then shown that there exist 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 proved more directly, as for example in notes by Peter Shor.
Read more about this topic: LZ77 And LZ78
Famous quotes containing the words theoretical and/or efficiency:
“Post-structuralism is among other things a kind of theoretical hangover from the failed uprising of ‘68Ma way of keeping the revolution warm at the level of language, blending the euphoric libertarianism of that moment with the stoical melancholia of its aftermath.”
—Terry Eagleton (b. 1943)
“I’ll take fifty percent efficiency to get one hundred percent loyalty.”
—Samuel Goldwyn (1882–1974)