Woland (guest) 09 Jul 2014 00:22
On the mentioned exam, question number 2 is about an image matrix (1000*1000).
The question says you can represent the matrix as R - which is chaining the values of the rows one after the other…
meaning M[0,0], M[0,1] …. M[0,999], M[1,0]….
or as C - which is chaining the columns.
Then it says that NR and NC are the Lempel-Ziv compression of these strings (where each char is represented by 8 bits since 2^8 = 256 ? Am i right?).
The answer to this question claims that (NC+NR)/2 < 8 * 1000**2 (which is the naive representation)…
my question is - how can we be sure that Lempel-Ziv actually decreases the size of the string.
As i believe was mentioned in class, we saw that the text lempel-ziv compression for 'abcdef', for example, only makes it longer (because it now represents each ascii 7-byte-represented-char with 8 bytes).
I understand that since there are 10**6 "chars" to compress i cannot use the example, but how can i prove that now the equation (NC + NR)/2 < 8*1000^2 actually holds?
Thanks alot!
