Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
1  
Perhaps this question is relevant? –  vonbrand Jan 31 '13 at 20:58
    
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. –  vzn Apr 15 '13 at 2:28
    
@vzn Excellent ideas, thanks! –  Cris Stringfellow Apr 15 '13 at 4:20
add comment

migrated from cstheory.stackexchange.com Jan 30 '13 at 15:55

This question came from our site for theoretical computer scientists and researchers in related fields.

2 Answers

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.

share|improve this answer
    
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? –  Cris Stringfellow Jan 30 '13 at 16:44
2  
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. –  Yuval Filmus Jan 30 '13 at 18:31
    
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? –  Cris Stringfellow Feb 1 '13 at 1:52
    
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. –  Yuval Filmus Feb 1 '13 at 4:23
    
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. –  Cris Stringfellow Feb 1 '13 at 4:53
show 3 more comments

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.

share|improve this answer
    
Great, ideas. Thanks @Rob! –  Cris Stringfellow Apr 15 '13 at 4:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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