next up previous contents index
Next: Adaptive Arithmetic Coder ( Up: Version 6.6 The LEDA Previous: Bounded Priority Queues (   Contents   Index


Lossless Compression

Before we go into the details of the classes belonging to this module we want to give an overview of the different components and how they interact. We start with an example. Suppose you want to write a string to a compressed file named ``foo'' and read it back from the file. Then you can use the following program:

#include <LEDA/basics/string.h>
#include <LEDA/coding/compress.h> // contains all compression classes

using namespace leda;

typedef HuffmanCoder Coder;

int main()
{
  string str = "Hello World";

  encoding_ofstream<Coder> out("foo");
  out << str << "\n";
  out.close();
  if (out.fail()) std::cout << "error writing foo" << "\n";

  decoding_ifstream<Coder> in("foo");
  str.read_line(in);
  in.close();
  if (in.fail()) std::cout << "error reading foo" << "\n";

  std::cout << "decoded string: " << str << "\n";

  return 0;
}

In the example above we used the classes encoding$\_ofstream$ and decoding$\_ifstream$ with LEDA datatypes only. We want to emphasize that they work together with user-defined types as well. All operations and operators (« and ») defined for C++ streams can be applied to them, too.

Assume that you want to send the file ``foo'' to a friend over the internet and you want to make sure that its contents do not get corrupted. Then you can easily add a checksum to your file. All you have to do is to replace the coder in the typedef-statement by CoderPipe2<MD5SumCoder, HuffmanCoder>. The class CoderPipe2 combines the two LEDA coders MD5SumCoder (the checksummer) and HuffmanCoder into a single coder. If the pipe is used for encoding, then the MD5SumCoder is used first and the HuffmanCoder is applied to its output. In decoding mode the situation is reversed.
The standard behaviour of a checksummer like MD5SumCoder is as follows: In encoding mode it reads the input stream and computes a checksum; the output data basically consists of the input data with the checksum appended. In decoding mode the checksum is stripped from the input data and verified. If the input is corrupted the failure flag of the coder is set to signal this.

Suppose further that your friend has received the encoded file ``foo'' and wants to decode it but he does not know which combination of coders you have used for encoding. This is not a problem because LEDA provides a class called AutoDecoder which can be used to decode any stream that has been encoded by LEDA. The complete code for this extended example is depicted below:

#include <LEDA/basics/string.h>
#include <LEDA/coding/compress.h>

using namespace leda;

typedef CoderPipe2<MD5SumCoder, HuffmanCoder> Coder;

int main()
{
  string str = "Hello World";

  // your code ...
  encoding_ofstream<Coder> out("foo");
  out << str << "\n";
  out.close();
  if (out.fail()) std::cout << "error writing foo" << "\n";

  // your friend's code ...
  autodecoding_ifstream in("foo"); 
            // autodecoding_ifstream = decoding_istream<AutoDecoder>
  str.read_line(in);
  in.finish(); // read till the end before closing (-> verify checksum)
  if (in.fail()) std::cout << "decoding error, foo corrupted" << "\n";
  std::cout << "decoded string: " << str << "\n";

  return 0;
}

This example shows how easy it is to add compression to existing applications: You include the header ``LEDA/coding/compress.h'', which makes all classes in the compression module available. Then you simply replace every occurrence of ofstream by encoding$\_ofstream$ <Coder > and every occurence of ifstream by autodecoding$\_ifstream$.

Of course, you can also use the LEDA coders in file mode. This means you can encode a file ``foo'' into a file ``bar'' and decode ``bar'' again. The example below shows how. We also demonstrate a nice feature of the AutoDecoder: If you query a description after the decoding the object tells you which combination has been used for encoding the input.

#include <LEDA/coding/compress.h>

using namespace leda;

typedef CoderPipe2<MD5SumCoder, HuffmanCoder> Coder;

int main()
{
  Coder coder("foo", "bar");
  coder.encode();
  if (coder.fail()) std::cout << "error encoding foo" << "\n";

  AutoDecoder auto("bar", "foo");
  auto.decode();
  if (auto.fail()) std::cout << "error decoding bar" << "\n";

  std::cout << "Decoding info: " << auto.get_description() << "\n";

  return 0;
}

More examples can be found in $LEDAROOT/test/compression. There we show in particular how the user can build a LEDA compliant coder which integrates seamlessly with the AutoDecoder.


Below we give a few suggestions about when to use which coder:



Subsections
next up previous contents index
Next: Adaptive Arithmetic Coder ( Up: Version 6.6 The LEDA Previous: Bounded Priority Queues (   Contents   Index