LZW
Implements the LZW compression algorithm.
You're viewing an older version of this page (#5690). View the current version.
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
- 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
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
Returns
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
Returns
STATIC CLASS METHOD
decodestr
Parameters
STATIC CLASS METHOD
lookup
Parameters
STATIC CLASS METHOD
putcode
Parameters
STATIC CLASS METHOD
getcode
Parameters
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.