# LZW

Implements the LZW compression algorithm.

Controller: **CodeCogs**

**Contents**

## Interface

C++

## Overview

This module allows to compress or decompress an input array using the Lempel-Ziv-Welch (LZW) algorithm. The LZW algorithm is a lossless data compression algorithm created by Terry Welch in 1984. This algorithm represents an improved version of the LZ78 algorithm created by Abraham Lempel and Jacob Ziv in 1978. The idea of the compression algorithm is the following: as the input data is being processed, a dictionary keeps a correspondence between the longest encountered words and a list of code values. The words are replaced by their corresponding codes and so the input file is compressed. Therefore, the efficiency of the algorithm increases as the number of long, repetitive words in the input data increases.**Note:**Either when using the compression or the decompression methods, the elements of the input array must be of type

**unsigned**

**char**, which is also the type of the resulting array's elements. The following example generates a sample array of N random letters (from A to Z) and compresses it. The compressed array is then decompressed to see if the sample array is identical to the uncompressed array. The size of the compressed array is also displayed, to prove the efficiency of the LZW algorithm.

### Example 1

#include <codecogs/computing/io/compression/lzw.h> #include <iostream> // the number of characters to generate in the sample array #define N 10000 using namespace Computing::IO::Compression; int main() { // initialize random seed srand(time(0)); // generate an array of N random letters std::vector<unsigned char> sample; for (int i = 0; i < N; ++i) sample.push_back('A' + rand() % ('Z' - 'A' + 1)); // compress the sample array std::vector<unsigned char> compressed = LZW::compress(sample); // decompress the compressed array std::vector<unsigned char> uncompressed = LZW::decompress(compressed); // compare the sizes of the compressed and uncompressed arrays std::cout << " Size of the sample array: " << N << std::endl; std::cout << " Size of the compressed array: " << compressed.size() << std::endl; std::cout << "Size of the uncompressed array: " << uncompressed.size() << std::endl; std::cout << std::endl; // test if the sample and the uncompressed arrays are identical // this proves that the LZW compression algorithm does not affect the initial data bool identical = (N == uncompressed.size()); for (size_t i = 0; identical && i < uncompressed.size(); ++i) if (sample[i] != uncompressed[i]) identical = false; if (identical) std::cout << "The sample and uncompressed arrays are identical." << std::endl; else std::cout << "Error! The sample and uncompressed arrays are NOT identical." << std::endl; return 0; }

**Output**Size of the sample array: 10000 Size of the compressed array: 7621 Size of the uncompressed array: 10000 The sample and uncompressed arrays are identical.

### Authors

*Lucian Bentea (July 2009)*

### References

- The description of the LZW algorithm on Wikipedia, http://en.wikipedia.org/wiki/Lempel-Ziv-Welch
- Implementation of the original LZW algorithm using various programming languages, http://rosettacode.org/wiki/LZW_compression

## Class LZW

The LZW class implements routines for compressing and expanding arrays using the LZW algorithm. These routines are called**compress**and

**decompress**.

##### Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.

## Members of LZW

#### Compress

This method uses the LZW algorithm to compress the array given throughstaticstd::vector<...>compress( std::vector<...> *&*`in`) *in*. The result is returned as another array. A typical use of this method would be similar to:std::vector<unsigned char> compressedData = LZW::compress(rawData);

in the array to compress, as a vector of unsigned char elements

### Returns

- the compressed array, as a vector of unsigned char elements

#### Decompress

This method uses the LZW algorithm to decompress the array given throughstaticstd::vector<...>decompress( std::vector<...> *&*`in`) *in*. The result is returned as another array.**Note:**The input array is supposed to be the result of applying the LZW compression algorithm. A typical use of this method would be similar to:std::vector<unsigned char> decompressedData = LZW::decompress(compressedData);

in the array to decompress, as a vector of unsigned char elements

### Returns

- the decompressed array, as a vector of unsigned char elements