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)
““Never hug and kiss your children! Mother love may make your children’s infancy unhappy and prevent them from pursuing a career or getting married!” That’s total hogwash, of course. But it shows on extreme example of what state-of-the-art “scientific” parenting was supposed to be in early twentieth-century America. After all, that was the heyday of efficiency experts, time-and-motion studies, and the like.”
—Lawrence Kutner (20th century)