| An Example A sample run of LZW for a sample input stream is shown below. (A
highly redundant string is used to highlight the compression features).
Input string: /WED/WE/WEE/WEB
Character input |
Code Output |
New Code Value and Associated
String |
/W |
/ |
256 = /W
|
E |
W |
257 = WE
|
D |
E |
258 = ED
|
/ |
D |
259 = D/
|
WE |
256 |
260 = /WE
|
/ |
E |
261 = E/
|
WEE |
260 |
262 = /WEE
|
/W |
261 |
263 = E/W
|
EB |
257 |
264 = WEB
|
<END> |
B |
|
Aggregate code output:
/WED<256>E<260><261><257>B
LZW decompression takes the stream of codes and uses it to exactly recreate the
original input data. Just like the compression algorithm, the decompressor adds a new
string to the dictionary each time it reads in a new code. All it needs to do in addition
is to translate each incoming code into a string and send it to the output. A sample run
of the LZW decompressor, for the identical string as above, is shown in below.
Input code: /WED<256>E<260><261><257>B
Code Input |
String Output |
New Code Value and Associated
String |
| / |
/ |
|
| W |
W |
256 = /W
|
| E |
E |
257 = WE
|
| D |
D |
258 = ED
|
| 256 |
/W |
259 = D/
|
| E |
E |
260 = /WE
|
| 260 |
/WE |
261 = E/
|
| 261 |
E/ |
262 = /WEE
|
| 257 |
WE |
263 = E/W
|
| B |
B |
264 = WEB
|
Output String: Input string: /WED/WE/WEE/WEB
Indeed, the most remarkable feature of this type of compression is that the
entire dictionary has been implicitly transmitted to the decoder. This is a marked
difference from algorithms such as Huffman and Shannon-Fano, where the coding scheme has
to be explicitly transported to the decoder, resulting in space-overhead and reduced
compression ratios. The LZW decompressor develops a dictionary identical to the one the
encoder used, created as it parses the strings.
|
