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.

template<class INPUT_ITERATOR, class OUTPUT_ITERATOR>
void bcopy( INPUT_ITERATOR input, INPUT_ITERATOR eof, OUTPUT_ITERATOR output )
{
    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::istream_iterator(),
	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) )
        out.put(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

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<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

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Comments:

sutambe
2012-01-05T04:40:04

I think you could use the stream buffer iterators (e.g., istreambuf_iterator and ostreambuf_iterator) in place of regular stream iterators.

#include <iterator>
#include <fstream>
#include <algorithm>

int main(void)
{
std::ifstream in("binary", std::ios_base::binary);
std::ofstream out("binary_copy", std::ios_base::binary);

std::copy(std::istreambuf_iterator<char>(in.rdbuf()),
std::istreambuf_iterator<char>(),
std::ostreambuf_iterator<char>(out));

return 0;
}


Permalink
ubm_techweb_disqus_sso_-6750fe5cda9485b8fe72d368596f9830
2012-01-03T20:41:42

You can still use iterators, even if you are reading raw data.

I would do something like this (assuming that we are 100% sure that the size of the input file is a multiple of 512B):

struct Block {
static const size_t size = 512;
char data[size];
};

ostream& operator<<(ostream& s, const Block& x) {
s.write(x.data, Block::size);
}

istream& operator>>(istream& s, Block& x) {
s.read(x.data, Block::size);
assert(s.gcount() == Block::size);
}

template <typename inputitr,="" typename="" outputitr="">
void bcopy(InputItr i, InputItr i_end, OutputItr out) {
while (i != i_end) {
*out = *i;
++i;
++out;
}
}

...

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


Permalink


Video