# Number of phrases of LZ compression

It is known that for the number $c(n)$ of phrases / tupel of the LZ compression for binary words of length $n$ the following relation holds: $$c(n)\leq\frac{n}{(1-\epsilon_n)\log_2 n}$$ With $\epsilon_n\to 0$ for $n\to\infty$.

The proof is made in Thomas & Cover: Elements of Information Theory (Lemma 12.10.1, page 320 in the linked chapter).

I tried to generalize it to an alphabet of size $k$ by adjust the proof step by step, but I failed. So, my question:

How can I prove that the number $c(n)$ of phrases / tupel of the LZ compression is bounded by $$c(n)\leq\frac{n}{(1-\epsilon_n)\log_k n}$$ for all words of length $n$ over an alphabet of size $k$ with $\epsilon_n\to0$ for $n\to\infty\;?$

• Sounds like an exercise. I suggest you keep trying. – Yuval Filmus Jun 19 '14 at 16:01
• If you mean an axercise for a course or something like that, it is not. But even if it were, your comment do not help me at all. – Danny Jun 19 '14 at 16:08
• Perhaps if you showed us the partial proof you have constructed so far, and where you think it broke down, we could give you better help. As it is, we can't tell what concepts you are having trouble with, so there's not anything useful that we can say. – Wandering Logic Jun 19 '14 at 19:36
• @WanderingLogic my question was more about some other way to prove this theorem.. like the answer i accept or maybe induction. Therefore i omit my try since it contains a lot of big expressions (see $n_k$ in the proof for $k=2$) – Danny Jun 20 '14 at 6:39
• Really? A down vote for that question? A lot of stupid questions pass that site and this question was down voted.. thanks. – Danny Jun 20 '14 at 6:41

You don't need to redo the proof for this, simply note that $n$ symbols of an alphabet of size $k$ can be represented with $n \log_2(k)$ bits. The Lempel-Ziv bound is then:
$\mbox{# phrases} \leq \frac{n log_2 k}{(1-\epsilon_{n \lg k})log_2(n \log_2 k)}$
Dividing numerator and denominator by $\log_2 k$ then gives:
$\mbox{# phrases} \leq \frac{n}{(1-\epsilon_{n \lg k})\left(log_k(n) + \log_2(\log_2(k))/log_2(k)\right)}$
Since $\epsilon_n \longrightarrow 0$ as $n \longrightarrow \infty$, the result follows.