The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
29 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 ...
1
vote
1answer
113 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 ...
-1
votes
1answer
251 views

Decoding a binary message with LZW dictionary

I have the following exam question for a multimedia exam in college and I have absolutely no idea where to start. I know how the decoder algorithm should work but I have no idea how to do it on ...
1
vote
2answers
156 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 ...
5
votes
2answers
112 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 ...