Data Compression Lec#14

Sparse Strings
Regardless of what the input data represents—text, binary, images, or anything else—we can think of the input stream as a string of bits. If most of the bits are zeros, the string is sparse. Sparse strings can be compressed very efficiently, and this section describes methods developed specifically for this task. Before getting to the individual methods it may be useful to convince the reader that sparse strings are not a theoretical concept but do occur commonly in practice. Here are some examples.
1. A drawing. Imagine a drawing, technical or artistic, done with a black pen on white paper. If the drawing is not very complex, most of it remains white. When such a drawing is scanned and digitized, most of the resulting pixels are white, and the percentage of black ones is small. The resulting bitmap is an example of a sparse string.
2. A bitmap index for a large data base. Imagine a large data base of text documents. A bitmap for such a data base is a set of bit-strings (or bitvectors) that makes it easy to identify all the documents where a given word w appears. To implement a bitmap, we first have to prepare a list of all the distinct words wj in all the documents. Suppose that there are W such words. The next step is to go over each document di and prepare a bit-string Di that is W bits long, containing a 1 in position j if word wj appears in document di. The bitmap is the set of all those bit-strings. Depending on the database, such bit-strings may be sparse.