Home // International Journal On Advances in Software, volume 4, numbers 3 and 4, 2011 // View article

A Proposal of a New Compression Scheme of Medium-Sparse Bitmaps

Authors:
Andreas Schmidt
Daniel Kimmig
Mirko Beine

Keywords: Compressed bitmaps; WAH algorithm; RLE; CPU memory gap

Abstract:
In this paper, we present an extension of the WAH algorithm which is currently considered to be one of the fastest and most CPU-efficient bitmap compression algorithms available. The algorithm is based on run-length encoding (RLE) and its encoding/decoding units are chunks of the processor’s word size. The fact that the algorithm works on a blocking factor which is a multiple of the CPU word size makes the algorithm extremely fast, but also leads to a bad compression ratio in the case of medium-sparse bitmaps (1% - 10%), which is what we are mainly interested in. A recent extension of the WAH algorithm is the PLWAH algorithm that has a better compression ratio due to piggybacking trailing words, looking “similar” to the previous fill-block. The interesting point here is that the algorithm is also described to be faster than the original WAH version under most circumstances, even though the compression algorithm is more complex. Based on this observation, we extended the concept of the PLWAH algorithm to allow so-called “polluted blocks” to appear not only at the end of a fill-block, but also multiple times inside. This leads to much longer fills and, as a consequence, to a smaller memory footprint, which again is expected to reduce the overall processing time of the algorithm when performing operations on compressed bitmaps.

Pages: 401 to 411

Copyright: Copyright (c) to authors, 2011. Used with permission.

Publication date: April 30, 2012

Published in: journal

ISSN: 1942-2628