Suppose that the LZ77 algorithm is used on the binary string x10 000 1 = 050001400001000. This notation means 5000 repetitions of 0, followed by 4000 repetitions of 1, followed by 1000 repetitions of 0. Assume a window size w = 1024.
(a) Describe how the above string would be encoded. Give the encoded string and describe its substrings.
(b) How long is the encoded string?
(c) Suppose that the window size is reduced to w = 8. How long would the encoded string be in this case? (Note that such a small window size would only work well for really simple examples like this one.) (d) Create a Markov source model with two states that is a reasonably good model for this source output. You are not expected to do anything very elaborate here; just use common sense.
(e) Find the entropy in bits per source symbol for your source m