Encode and decode the following sequence using L-77 and Lz-78 algorithm.

wabbabrarbarracbac

Give drawbacks of Lz-77 and Lz-78 assume window size 9 for Lz-77.

Mumbai university > Electronics and telecommunication Engineering > Sem 7 > Data compression and Encryption

Marks: 10

Years: Dec 2015

**Encoding the given sequence using L-77

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.

| w | a | b | b | a | b | r | a | r | b | a | r | r | |---|---|---|---|---|---|---|---|---|---|---|---|---|

Search buffer (7) Look ahead buffer (6)

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)>

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)>

| wabb | a | b | r | a | r | b | a | r | r | a | c | b | a | c | |------|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

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)>

| wabbabr | a | r | b | a | r | r | a | c | b | a | c | |---------|---|---|---|---|---|---|---|---|---|---|---|

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)>

| r | b | a | r | r | a | c | b | a | c | wabbabra | |---|---|---|---|---|---|---|---|---|---|----------|

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)>

| r | b | a | r | r | a | c | b | a | c | wabbabra | |---|---|---|---|---|---|---|---|---|---|----------|

Hence, look the ad 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

wabbabrarbarracbac**

Sequence: wabbabrarbarracbac

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.