The Lempel-Ziv-Welch (LZW) Algorithm

The LZW compression is commonly used for encoding and decoding GIF images. This recursive algorithm was first developed in 1977 by Abraham Lempel and Jacob Ziv and later modified by Terry Welch. This algorithm received notoriety through patent claims from Unisys - an international IT company - targeted at the Open Source and free Software developers'Community. Not at last due to these claims the extremely popular GIF file format lost ground to the emerging PNG file format. Luckily enough, this patent is about to expire this year (2004) in most countries.

The algorithm is basically very simple. Colour values are converted to strings which are then referenced and stored. The aim is to produce longest possible strings by taking adjacent colours and looking for identical sequences throughout the entire image. Take for example the following simplified sequence:

1. RRGBGBGGBRGBBGBRRGBGBGBGBBBRRBGBG
2. When split up we discover a variety of identical strings: RRG BGB GG BR GB BGB RRG BGB G BGB B BR R BGB G $_1$_2GG$_3GB$_2$_1$_2G$_2B$_3R$_2G [$_1=RRG][$_2=BGB][$_3=BR]
3. or another possibility: RR GBGB G GBR GB B GBR R GBGB GBGB BB RR B GB G $_1$_2G$_3$_4B$_3R$_2$_2BB$_1B$_4G [$_1=RR][$_2=GBGB][$_3=GBR][$_4=GB]
4. ...and a last one: RRGBGBG GB R GB B GB RRGBGBG B GB BBRRB GB G $_1$_2R$_2B$_2$_1B$_2BBRRB$_2G [$_1=RRGBGBG][$_2=GB]

The best choice is the one which needs the least storage memory. From the above examples we see that many short strings as in example #3 will use lots of memory while the production of as long as possible identical strings as in example #4 needs the least memory.

How the LZW-Algorithm works for GIF encoding and decoding is illustrated in the following flow-charts.

The GIF Encoding algorithm

The GIF Decoding algorithm

The above charts are based on the original images GIFENCOD.GIF and GIFDECOD.GIF by Bob Montgomery