# How optimal is Lempel-Ziv at reaching the Shannon limit?

I find this a bit difficult to describe, but I am interested in the following idea :

The LZ algorithm factors (verb) an input stream into adjacent factors, these are by definition the maximal prefixes of the piece of text that occur in the previous text (or equivalently the previous concatenation of LZ factors).

I know and believe that in the long term (given infinite input and infinite window) this coding scheme can achieve the Shannon limit, that it will find all repeat patterns that exist.

However in any given finite text (but with an unbounded window) how optimal is this?

Do the choice of factors earlier in the input have potential detrimental effects later on? For instance, could LZ converge to a choice of factors that omits certain larger factors, or factor-choices that would result in a better cover of the input (i.e. a choice of factors that cover more of the text?).

Or is the optimality of LZ only constrained by the window limit, and the finite nature of a text? Please provide some kind of hand waving or intuitive proof.

-
Achieving the Shannon limit isn't the same as finding all the repeat patterns that exist. I think you can show that there isn't any decomposition into fewer factors. But whether that means that it's optimal then depends on how you encode the factors. – Peter Shor Jan 30 '13 at 16:03
Yes, thank you, @PeterShor! I was thinking the same thing : Achieving the Shannon limit (and even LZ coding) is not the same thing as finding all repeat patterns that exist. Are there any (better than trivial) algorithms / work about finding all repeat patterns? I've been thinking about all repeat patterns that exist a lot lately. – Cris Stringfellow Jan 30 '13 at 16:47
The DEFLATE algorithm follows LZ77 with Huffman coding, and does better for finite strings than LZ77 alone. So LZ77 can be improved upon for short strings fairly easily, just not by another iteration of LZ77. – Peter Shor Jan 31 '13 at 14:06

If you apply the LZ77 algorithm twice, it doesn't find any new repeat patterns the second time. You can show that if there were any repeat pattern present after the LZ77 algorithm has been applied. this would have arisen from a repeat pattern in the original data which LZ77 would have found.

The DEFLATE algorithm follows LZ77 with Huffman coding, and does better for finite strings than LZ77 alone. So LZ77 can be improved upon for finite strings fairly easily, just not by using another iteration of LZ77.

However, the Huffman algorithm doesn't use repeat patterns. If you're asking the question of whether, for finite strings, the LZ77 algorithm does as well as any other algorithm based solely on finding repeat patters, I don't know if anybody has looked at this. The problem isn't quite well-defined as stated, but somebody might be able to prove some interesting theorems about this.

-
'Ask and you shall receive.' Great, thanks. – Cris Stringfellow Jan 31 '13 at 14:10
I think that is the gist of my question, yes. Are there any other better methods based on finding repeat patterns alone. If no body has looked at this that is interesting. – Cris Stringfellow Jan 31 '13 at 14:12
Yes re the proof, I believe you! This makes sense. Which is also equivalent to LZ being optimal. So while LZ is optimal in the limit -- for finite strings and based solely on repeat patterns there may be better factorizations findable by algorithms that do better than LZ. Or maybe LZ is the best. – Cris Stringfellow Jan 31 '13 at 14:35

The book Elements of information theory by Cover and Thomas contains some information on the Lempel-Ziv algorithm, including a proof of its asymptotic optimality (see Chapter 13).

-
This isn't an answer ... the OP already knows that LZ77 is optimal. – Peter Shor Jan 31 '13 at 4:36
Well, the proof can be mined to get results on the speed of convergence, and may be the issues the OP is interested in are discussed there. – Yuval Filmus Jan 31 '13 at 4:51
@PeterShor That is true actually. It did not really add anything. But I was kind of hoping to get an answer. – Cris Stringfellow Jan 31 '13 at 14:10