Questions tagged [lempel-ziv]
The lempel-ziv tag has no usage guidance.
7
questions
0
votes
1answer
32 views
Lempel-Zilv-Welch Algorithm Decoding Question
Hello i am studying about LZW algorithm by watching this video:
https://www.youtube.com/watch?v=j2HSd3HCpDs&t=481s
I couldnt fully understand decoding process.
At current 258,how does 116 come at ...
1
vote
2answers
6k 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!...
5
votes
0answers
318 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 ...
1
vote
1answer
91 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 $\...
2
votes
1answer
931 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 process (...
2
votes
2answers
585 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 ...
6
votes
2answers
201 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$....
