Channels ▼

Mark Nelson

Dr. Dobb's Bloggers

What's the Best Paradigm for Data Compression Routines?

January 03, 2012

When I updated my LZW reference code to use the latest C++ features, I abstracted my input and output functions using templates. Data was read and written using the iostreams paradigm, which requires simple classes that implement just a few functions. Would I have been better off using the iterator paradigm instead? The C++ algorithms library favors that method of processing data, and it can be both elegant and powerful. Which of the two paradigms is the right one for data compression?

The Conflict

General purpose data compression routines tend to be used on binary streams of data, either from files or in-memory objects. So what is the best general paradigm for input and output when compressing data?

You might analyze this problem by imagining that you need to write a binary copy routine.

    while ( input != eof )
        *output++ = *input++;

This routine is particularly nice when you are performing a simple copy using pointers to memory — the generated code should be really efficient.

However, the iterator paradigm doesn't work quite as well when you want to perform a binary copy of data in a file. I can make use of iterators that almost do the job:

 std::ifstream in( "input.txt", std::ios_base::binary );
 std::ofstream out("output.txt", std::ios_base::binary );
 bcopy( std::istream_iterator(in),
	std::ostream_iterator(out) );

But the bad news is that both istream_iterator and ostream_iterator use the insertion and extraction operators, which are really meant for whitespace-delimited textual data, not binary data. The copy routine shown here will not make a binary byte-for-byte copy of the input file.

So when using files, the stream approach seems to be the way to go:

template<class INPUT_STREAM, class OUTPUT_STREAM>
void bcopy( INPUT_STREAM in, OUTPUT_STREAM out )
    char c;
    while ( in.get(c) )

If my files have been opened using the iostream classes, I can use this binary copy function without having to write any glue code — they already support the get and put methods, so this works right out of the box.

My Choice

If I've made up my mind that my data compression routine is going to use one of these two paradigms, it means I am going to have to write some glue code. If I choose the iterator-based approach, I need the equivalent of istream_iterator and ostream_iterator for binary files — and these aren't in the standard library. If I choose the stream-based approach, I need efficient put() and get() members for blocks of memory. In some cases, basic_stringstream might do the job, but not in all cases.

After dithering around with various solutions, I tentatively opted for the stream paradigm. I found the implementation for various sources of data to be fairly simple, and the interface is easy to understand. I don't know if it's the perfect choice, and I'll keep experimenting, but for now it works for me. My abstraction of the LZW code still needs a lot of work, so it's always possible I could rethink this at a later date.

I'd like to hear your thoughts — is there an obvious right answer to this question?

Related Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags


<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags


<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

