Subject: Multimedia System

Topic: Compression Algorithms

Difficulty: Hard

The Lempel-Ziv-Welch (LZW) algorithm employs an adaptive, dictionary-based compression technique. Unlike variable-length coding, in which the lengths of the code words are different, LZW uses fixed-length code words to represent variable-length strings of symbols/ characters that can only occur together, such as words in English text.

Algorithm of LZW Compression:

BEGIN

s = next input character;

while not EOF

c = next input character;

if s + c exists in the dictionary

s= s + c;

else

{

output the code for Si

add string s + c to the dictionary with a new codej

S = Ci

}

output the code for Sj

END

LZW Compression for String ABABBABCABABBA

Let's start with a very simple dictionary (also referred to as a string table), initially containing only three characters, with codes as follows:

Algorithm of LZW Decompression:

BEGIN

s = NIL:

while not EOF

{

k = next input code:

entry = dictionary entry for k;

output entry;

if (s != NIL)

add string s + entry[OJ to dictionary

with a new code;

s = entry:

}

END