utl::BWTencoder Class Reference
[Data Compression]

BWT-based coder. More...

#include <BWTencoder.h>

Inheritance diagram for utl::BWTencoder:

[legend]

List of all members.

Public Member Functions
	BWTencoder (uint_t mode, Stream *stream, bool owner=true, uint_t blockSize=K(256))
	Constructor.
virtual uint_t	decode (byte_t *block, uint_t num)
	Decode data from the associated stream.
virtual uint_t	encode (const byte_t *block, uint_t num)
	Encode data to the associated stream.
void	start (uint_t mode, Stream *stream, bool owner=true, uint_t blockSize=K(256))
	Initialize for encoding or decoding.
Protected Member Functions
virtual void	clear ()
	Revert to initial state.
virtual void	finishEncoding ()
	Perform any necessary clean-up when encoding is finished.

---

Detailed Description

BWT-based coder.

BWTencoder is a block-sorting, lossless data compressor based on the Burrows-Wheeler Transform (BWT). bzip2 by Julian Seward is currently the most popular compressor based on the BWT. I have stolen some ideas (and even code!) from bzip2, and I've made it clear (with code comments) where I've done so. In fact, I have to admit that this implementation contains no original ideas or insights of my own. My goal here isn't research - I leave that to those who are best-suited for it. I've tried to provide a solid implementation that is:

• fast enough for many purposes
• easy to read and maintain
• easy to use within the UTL++ framework

I think I've achieved these goals. I'll leave it to you to decide if this implementation is a good choice for your application. The best I can do is be honest about the strengths and weaknesses.

Attributes

• blockSize : Setting the block size is the sole method of compression tuning. Compression benefits from larger block size, but the law of diminishing returns applies here. 256 KB tends to be a nice balance between compression ratio and memory/CPU usage. I don't recommend a block size smaller than 64 KB or larger than 1 MB though. Space required is approx. (9 * blockSize) for compression and (5 * blockSize) for decompression.

Advantages

• provides excellent compression
• code is easy to read and maintain
• fast enough for many purposes
• easy to use within the UTL++ framework

Disadvantages

• it's a resource-hog, even compared to bzip2:
• -- requires more space than bzip2
• -- requires more time than bzip2 (a lot more in the worst case)
• possible patent issues due to the use of arith-coding
• not as thorougly tested as bzip2 (yet) -- use at your own risk!

Research Papers

   M. Burrows and D. J. Wheeler
   "A block-sorting lossless data compression algorithm"
   SRC Research Report 124

Links

• http://gatekeeper.dec.com/pub/DEC/SRC/research-reports/abstracts/src-rr-124.html
• http://www.bzip.org/

Author:

Adam McKee

Definition at line 76 of file BWTencoder.h.

---

Constructor & Destructor Documentation

utl::BWTencoder::BWTencoder	(	uint_t	mode,
		Stream *	stream,
		bool	owner = true,
		uint_t	blockSize = K(256)
	)			[inline]

Constructor.

Parameters:

	mode	io_rd to encode, io_wr to decode (see io_t)
	stream	(optional) associated stream
	owner	(optional : true) owner flag for stream
	blockSize	(optional : 256 KB) block size

Definition at line 87 of file BWTencoder.h.

References utl::init().

---

Member Function Documentation

virtual uint_t utl::BWTencoder::decode	(	byte_t *	block,
		uint_t	num
	)			[virtual]

Decode data from the associated stream.

Returns:

number of bytes decoded

Parameters:

	block	block to decode into
	num	size of block

Implements utl::Encoder.

virtual uint_t utl::BWTencoder::encode	(	const byte_t *	block,
		uint_t	num
	)			[virtual]

Encode data to the associated stream.

Returns:

number of bytes encoded

Parameters:

	block	block to encode
	num	size of block

Implements utl::Encoder.

void utl::BWTencoder::start	(	uint_t	mode,
		Stream *	stream,
		bool	owner = true,
		uint_t	blockSize = K(256)
	)

Initialize for encoding or decoding.

Parameters:

	mode	io_rd to encode, io_wr to decode (see io_t)
	stream	(optional) associated stream
	owner	(optional : true) owner flag for stream
	blockSize	(optional : 256 KB) block size

virtual void utl::BWTencoder::clear

(

)

[protected, virtual]

Revert to initial state.

Reimplemented from utl::Encoder.

virtual void utl::BWTencoder::finishEncoding

(

)

[protected, virtual]

Perform any necessary clean-up when encoding is finished.

Reimplemented from utl::Encoder.

---

The documentation for this class was generated from the following file:

• BWTencoder.h