Lempel, Ziv, Welsh (LZW)

The LZW algorithm is a widely used lossless compression for photos and graphics developed by Jacob Ziv, Abraham Lempel and Welsh in 1984. It is a one-dimensional compression algorithm based on the assumption that certain data sequences repeat in a data sequence.

As far as the repetition of data sequences is concerned, it may be, for example, repeating color patterns in a graphic or recurring character strings in a text. A repetition of a data sequence is present if, for example, a larger number of consecutive pixels have completely identical colors. In such a compression, the same byte is not assigned to each pixel, but only the first pixel is stored with a recognition code and the byte for the color value. Since the following pixels have the same color value, the next color value stored is the one that differs from the previous color values. This means that all pixels in between are not stored, which leads to a considerable reduction in data.

In the LZW method, the data is broken down into sections that are entered into a code table. For this purpose, a data block of fixed length is sampled, from which pointers are obtained and a dictionary is derived. The characters to be transmitted are assigned LZW codes via an assignment table, which are also transmitted. The LZW method achieves a much higher data reduction for detailed graphics than Run Length Encoding( RLE). The LZW algorithm is used in Graphics Interchange Format( GIF), in a variant also in PNG file format and optionally in Tagged Image File Format( TIFF).