Can I have an example of a greedy input, for both the huffman and ZL algorithms? I think i grasp the concept but find it hard to come up with an actual example.
Date: 05 Feb 2015 13:32
Number of posts: 6
RSS: New posts
This is a quote from the LZ lecture:
"Our compression algorithm as described is greedy: Any repeat of length 3 or more is reported and employed right away. Sometimes this is not optimal: We could have an [m1, k1] repeat in position p, and an [m2, k2] repeat in position p+1 or p+2, with k1«k2. Thus a non-greedy algorithm may result in improved compression."
I must say I don't understand this explanation, so if someone who gets it can give an example that could be a great help.
A greedy algorithm makes the best choice it can at each point, so it may not always be the optimal one, just locally optimal. There are problems for which the greedy algorithm is the best, but in the case of LZ, it is possible that by choosing the longest repeated sequence at the current position, I lose a possibility to find a longer one just one step ahead.
Is the greed of the algorithm k-dependant? (k being the minimal repeated sequence for compression).
Actually I just saw that question 7.a in the last HW assignment was to give exactly that kind of example… So I got it :-)