I have been experimenting with LZ77 (naively $O(n^2)$ runtime, infinite window). Applying it to the 7th Fibonacci word $abaababaabaab$ yields the correct LZ factorization:

$\qquad a,b,a,aba,baaba,ab$.

My question is about the behavior of LZ77 if we iterate it. My experiments suggest that reapplication of LZ77 to the input will yield no further patterns that were not found the first time.

By reapplication I mean, where in the first instance we treat the factors of the string as the sequence of unit symbols 'a' and 'b', in the second application the factors are the LZ factors. I was hoping to discover (over larger various texts, like the Complete Sonnets of Shakespeare) increasing gains, and possibly, "multilevel" patterns found by LZ over the sequence of factors of the previous iterate. But none of this occurred. The sequence of factors after the second iteration is exactly the same as the first.

So where is the bug in my thinking? Is there a simple proof of this given the definition of an LZ factor being the longest prefix from the current position occurring in the concatenation of the preceding LZ factors?

  • 1
    $\begingroup$ Perhaps this question is relevant? $\endgroup$
    – vonbrand
    Commented Jan 31, 2013 at 20:58
  • $\begingroup$ there are some compression algorithms which are "recursive" see eg grammar compression. also some "specially constructed/contrived" inputs could give additional "levels" of compression but generally it wont happen. $\endgroup$
    – vzn
    Commented Apr 15, 2013 at 2:28

2 Answers 2


Lempel and Ziv proved that under some reasonable assumptions, the limiting rate of their algorithm is equal to the entropy of the text. That means that in the limit, the output should be completely random. Random text cannot be compressed (on average), so you should expect that if you take a long text and apply Lempel-Ziv twice, then the second time wouldn't compress the text at all.

  • $\begingroup$ So it's that simple, huh? Wow, it is such an amazing algorithm they can get such clean, no-loose-ends results. But it's also a really simple algorithm. There's really nothing more to it? $\endgroup$ Commented Jan 30, 2013 at 16:44
  • 2
    $\begingroup$ Not quite. The algorithm is only guaranteed to work under some (reasonable) assumptions. The performance guarantee is only true in the limit. In any specific domain, you could use domain-specific knowledge to "speed up convergence". The complexity of the algorithm is not necessarily optimal. And many times lossy encryption is acceptable and has (much) superior performance, e.g. for images, music and videos. $\endgroup$ Commented Jan 30, 2013 at 18:31
  • $\begingroup$ thanks! So are there any more of the assumptions they refer to than you mention above? Or should I just read the paper again for those? $\endgroup$ Commented Feb 1, 2013 at 1:52
  • $\begingroup$ The assumption is that the process is Markovian and at its limiting distribution, i.e. ergodic. You can read Cover & Thomas to see what this means. $\endgroup$ Commented Feb 1, 2013 at 4:23
  • $\begingroup$ So the assumption reduces to bigram or transition frequencies between letters of the alphabet? Or does it assume the repeat patterns ( of any length ) are markovian ? In the former which I suspect is intended , this is very limiting. $\endgroup$ Commented Feb 1, 2013 at 4:53

You have to be careful about what you mean by iterative. Did you apply this to a sequence of concatenations of the source string? Because that will certainly increase the dictionary. There might also be some interesting optimal intersections (from the coding perspective of the optimal prefix-free size of the pattern encoding vs the individual optimal prefix symbol encodings) of pattern sizes discovered by applying it forwards and backwards instead of iteratively.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.