# Questions tagged [lempel-ziv]

The tag has no usage guidance.

8 questions
Filter by
Sorted by
Tagged with
213 views

### Behavior of iterative application of LZ77

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$....
325 views

### LZ-type compression with a limited recursion depth

I would like to begin by apologizing. I am not a computer scientist, so my use of terminology will be off. I came across an interesting problem, which I believe to be pretty hard and would love to get ...
8k views

### Huffman Coding vs LZW Algorithm

I'm trying to understand comparisons between the two. Is there ever a case where is it better to use Huffman Coding over LZW? Could the compression ratio for Huffman ever surpass that of LZW? Thanks!...
642 views

### 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 ...
985 views

### LZW decoding process

I'm trying to understand how LZW decodes a string. For example suppose that we have a dictionary where: a=0 b=1 and we have to encode the string "aabbabaabb", so the output of the encoding ...
92 views

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