Encode and decode the following sequence using L-77wabbabrarbarracbac Give drawbacks of Lz-77 and Lz-78

14views

written 6.2 years ago by

teamques10 ★ 68k

Encoding the given sequence using L-77

Given Sequence: wabbabrarbarracbac

Consider the length of the window is 13 in which the size of search buffer is 7.

Size of look ahead buffer is 6. It is assumed that contents of search buffer are already encoded.

enter image description here

Search buffer (First 7 bits)

Look ahead buffer (last 6 bits)

For ‘a’ in look ahead buffer, a match at maximum offset of 6 is obtained.

Offset (o) = 6

Length (l) = 1

Code = c(r)

Therefore, the triple is <6, 1, c(r)>

enter image description here

For ‘b’ in look ahead buffer, a match at maximum offset of 7 is obtained.

Offset (o) = 7

Length (l) = 1

Code = c(a)

Therefore, the triple is <7, 1, c(a)>

enter image description here

For ‘r’ in look ahead buffer, a match at maximum offset of 5 is obtained.

Offset (o) = 5

Length (l) = 1 + 1 =2

Now, in this case the actual length l = 2 because ‘r’ is following after the match ‘r’ in search buffer. As ‘r’ is already encoded in the sequence the modified length becomes 1 + 1 = 2 where additional length of 1 is for ‘r’ sequence in look ahead buffer.

Code = c(a)

Therefore, the triple is <5, 2, c(a)>

enter image description here

For ‘c’ in look ahead buffer, there is no match found in search buffer.

Offset (o) = 0

Length (l) = 0

Code = c(c)

Therefore, the triple is <0, 0, c(c)>

enter image description here

For ‘b’ in look ahead buffer, a match at maximum offset of 6 is obtained.

Offset (o) = 6

Length (l) = 2

Code = c(c)

Therefore, the triple is <7, 1, c(c)>

enter image description here

Hence, look ahead buffer is now empty and encoding is stopped.

The encoding triples are

<6, 1, c(r); 7, 1, c(a); 5, 2, c(a); 0, 0, c(c); 7, 1, c(c)>

Encoding the given sequence using L-78

Given Sequence: wabbabrarbarracbac

Output	Index	Entry
<0, c(w)>	1	w
<0, c(a)>	2	a
<0, c(b)>	3	b
<3, c(a)>	4	ba
<3, c(r)>	5	br
<2, c(r)>	6	ar
<4, c(r)>	7	bar
<0, c(r)>	8	r
<2, c(c)>	9	ac
<3, c(c)>	10	bac

Sequence: w a b ba bra r bar r ac bac

Drawbacks of L-77 compression technique:

This method assumes that a match is found around the window which is not the case in practical applications.

Compression ratio can be improved only by increasing the size of search window which increases the latency.

This method is not practically applicable as there is no definite data structure.

Drawbacks of L-78 compression technique:

The drawback of the L-78 algorithm is the memory size as the frequently encountered symbols as well as the longer matches have to be stored as entries in the dictionary.

If the dictionary is full then either the dictionary has to be restarted or some of the entries have to be deleted.

ADD COMMENT EDIT