Implements the LZW compression algorithm.

View versions (2)

Interface

#include <codecogs/computing/io/compression/lzw.h>

using namespace Computing::Io::Compression;

class LZW

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>
#include <cstdlib>
#include <ctime>

// 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.

References

GPL Licence — free for non commercial use. See Licence details.

Members of LZW

STATIC CLASS METHOD

compress

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);

Parameters

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

Returns

the compressed array, as a vector of unsigned char elements

STATIC CLASS METHOD

decompress

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);

Parameters

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

Returns

the decompressed array, as a vector of unsigned char elements

STATIC CLASS METHOD

decodestr

Parameters

buf
buffer to write the decoded (reversed) string into
code
the dictionary code to expand
pfxcode
the prefix-code table built up during decoding
appchar
the appended-character table built up during decoding

STATIC CLASS METHOD

lookup

Parameters

strcode
the dictionary code for the string seen so far
c
the next input character to extend that string with
codeval
the hash table mapping (strcode, c) pairs to their assigned dictionary code
pfxcode
the hash table's prefix-code entries
appchar
the hash table's appended-character entries

STATIC CLASS METHOD

putcode

Parameters

out
the output byte stream to append packed bits to
code
the fixed-width code to pack into the output stream

STATIC CLASS METHOD

getcode

Parameters

in
the compressed byte stream to unpack bits from
pos
the current byte position within in, advanced as bits are consumed

DECLARATION

input_bit_count

Number of valid bits currently held in input_bit_buf, waiting to be consumed by getcode().

DECLARATION

output_bit_count

Number of bits currently held in output_bit_buf that have not yet been flushed to the output stream.

DECLARATION

input_bit_buf

32-bit bit-accumulator used by getcode() to unpack fixed-width codes from the compressed byte stream.

DECLARATION

output_bit_buf

32-bit bit-accumulator used by putcode() to pack fixed-width codes into the compressed byte stream.