# Tag Info

8

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 ...

5

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 ...

5

In a gist LZW is about frequency of repetitions and Huffman is about frequency of single byte occurrence. Take the string 123123123. (The following is an oversimplification but will make the point) LZW will identify that 123 is repeated three times and essentially create a dictionary of codes for sequences. It will esentially say when I say A I mean 123 ...

4

LZW is dictionary-based - as it encodes the input data, it achieves compression by replacing sub-strings that have occurred previously with references into the dictionary. If phrases do not repeat (the data is a stream of symbols in more or less random order), LZW isn't going to be able to compress the data very well. By contrast, Huffman Coding could ...

3

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-\...

2

Short answer: the decoding algorithm follows the same steps as the coder: it actually builds the tree. E.g., in your example the first two 0's mean two a's have been read, This then implies the code for aa was added to the tree as number 2. This continues, but necessarily the decoder always is one step behind the coder. In most cases all information is ...

1

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).

1

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 ...

Only top voted, non community-wiki answers of a minimum length are eligible