LZW

Interface

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

1. The description of the LZW algorithm on Wikipedia, http://en.wikipedia.org/wiki/Lempel-Ziv-Welch
2. 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

 

staticstd::vector<...>compress(

std::vector<...>&

in

)

This method uses the LZW algorithm to compress the array given through 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

 

staticstd::vector<...>decompress(

std::vector<...>&

in

)

This method uses the LZW algorithm to decompress the array given through 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