Dealing with Short Runs

However, not all data is as uniform as our first example. Following the simplistic algorithm, AAAABCCCC would be encoded as [A,4][B,1][C,4]. Because the single B in the middle of the run was expanded from one symbol to a symbol-and-length pair, we have just created bloat in the data stream, as illustrated in Figure 8-2.

Figure 8-2. Small runs represent large problems for RLE as an algorithm. The overhead of storing short runs impacts the compression size significantly. Take this example, where the many nonduplicated symbols bloat the output.

Now if you’re lucky, across your entire stream the amount of overhead from these single symbols will easily be covered by the savings from long runs.

For all other situations, you need a way of identifying runs of characters that are worse off being encoded with RLE, and perhaps should be left alone in the stream, instead. For example, you could encode only runs with two or more symbols.

With that premise, AAAABCCCC would be encoded as [A,4] B [C,4]. Thus, if many characters are not repeated, you will rarely use an unnecessary counter. The problem with this method is that decoding is properly ambiguous. If we translate the transformed stream into binary, we could end up with 100000110010000101000011100,² and no real way of distinguishing where the B run ends and the C run begins. Basically, the literal values being interwoven into the data stream is problematic.³

As such, we need a way to denote what runs have pairs and what runs don’t. A common solution to this is to add to the data set a second bit stream that denotes whether a given stream is long or repeated (Figure 8-3). Thus, the stream of 100000110010000101000011100 would be prepended by a bit stream of 101, denoting that the first symbol is a run, the second is not, and the third is. This helps save you the overhead of small-run streams by instead deferring a single bit-per-run.

Figure 8-3. By combining a bit stream denoting which literals are runs, we can properly decode the stream. In this example, the second literal has a 0 for run control, so we don’t attempt to read the 3 bit code afterward, which would denote how long the run is.

Compressing

Compressing an RLE’d stream is a bit of a trick. First, split your data set into two sets: a literal stream, and a run-length stream. (Remember the bit stream you prepended? It will tell you from which stream to read during decoding.) You can encode the literal stream by using an encoder of your choice.⁴ The run-length stream is really where the compression problems lie. So, using the very real-world method of trial and error, let’s find a suitable encoding for it.⁵

Given the lengths [4,3,1,1,1,3,1,2,1,2,1], we could encode them with binary 2 bits per value, giving us 22 bits total. However, this falls over if we get one run of long length, such as [256,3,1,1,1,3,1,2,1,2,1]. In this case, we’d need to encode all the values with the same number of bits as the largest value in the set. So in this case, we’d need to encode every value with 8 bits, making the set 88 bits total. Not ideal.

So, let’s move from that to static VLCs. In a naive model, we could assign a run-length integer with the number of bits from the representing VLC. So, if we had the lengths [4,3,1,1,1,3,1,2,1,2,1], we could end up with a unary encoding of [11110,1110,10,10,10,1110,10,110,10,110,10], or 31 bits. As you can see, this method fails directly. It assigns the smallest value to the smallest codeword (assuming that it appears most often in the data). RLE lengths are opposite, however, and we want to assign the largest values (representing the longest runs) with the smallest codewords.

Applying a statistical encoder (such as Huffman or arithmetic compression) might be better. We can get a sense of the impact of those values on our data set by calculating the set’s entropy, which is 1.69, giving us an encoded size of ~19 bits (about 13% savings). We could find a lower entropy by applying an adaptive version of a statistical encoder, which might take into account locality, if there is any.

RLE is considered a single-context model, in that any given symbol considers the previous symbol during encoding. If it’s the same, you continue on with the run, and if it’s different, you terminate the current run. Even though it’s not used often for modern compressors, more efficient RLE methods continue to be researched. For example, a new RLE compressor, TurboRLE, has been published recently, and it claims to be the fastest, most efficient RLE encoder of all time.

XOR Delta Coding

The issue with subtractive delta coding is that you can end up with negative values, which causes all sorts of problems. Negative values require you to store an extra lead bit, and they also increase the dynamic range of your data, like so:

We can improve this result by replacing subtractions  with bitwise exclusive OR (XOR) operations.

    0101 (decimal 5)
XOR 0011 (decimal 3)
  = 0110 (decimal 6)

     0101 (decimal 5)
XOR 1111 (decimal 15)
  = 1010 (decimal 10)

XORing bypasses the issue of negatives entirely, because XORing integers never generates negative values.

Starting with: [1,3,10,8,6]

So, this didn’t quite reduce the dynamic range, because we still need 4 bits per value, but it did keep all our values positive, regardless of the relative ordering of the data.

Frame of Reference Delta Coding

Consider the following sequence:

We could store these 10 numbers as 8-bit integers using 80 bits in total. But that seems a waste because all those numbers below 107 are just padding space. We’re including bits to potentially represent them, but our data set does not include any of those values.

The frame-of-reference approach addresses this problem by subtracting the smallest value from the rest of the numbers. In the example, the numbers range from 107 to 135. Thus, instead of coding the original sequence, we can subtract 107 from each value and delta encode this difference:

As a result, we can code each offset value using no more than 5 bits.

Of course, we still need to store the minimum value 107 using 8 bits, and we need at least 3 bits to record the fact that only 5 bits per value are used. Nevertheless, the total 8 + 3 + 9 * 5 = 45 is much less than the original 80 bits.

The “frame” part of “frame of reference” (also called “FOR”) has to do with the fact that to apply this transform to your data set properly, you need to subdivide it into smaller blocks (or frames) of numbers. 

For instance, we could split our previous set of numbers into these two sets:

We’d end up with the following:

And framing our data has helped produce smaller dynamic ranges, and thus it requires fewer bits per value to represent.⁷

Sadly, outliers can still cause problems.

Patched Frame of Reference Delta Coding

Consider the following number set:⁸

That outlier is basically breaking compression for the rest of the data.

To alleviate this problem, Zukowski et al.⁹ proposed a method of patching that they called PFOR.¹⁰

It works like this:

1. Choose a bit width b.

2. Walk through the data and encode numbers with b bits.

3. When you come to a number that requires more than b bits to encode, store this exception in a separate location.

The exceptions part of PFOR is where the magic comes in.

1. Consider our delta encoded example [1,1,8,246].

2. In a simplistic form, we could split the data into two sets, those values that require b bits and those that don’t. With b = 4 bits, we’d then get [1,1,8][246].

3. We can now encode the first set with 4 bits, and then the exception in 8 bits.

4. To know where the exceptions get merged back into the source list, we also need a position value, giving us [1,1,8][246][3].

During the decoding phase, we take the exception values and insert them back into the source stream before undoing the delta decoding.

Of course, there are two main questions at this point:

• How do we find the value b?

• What do we do with the exceptions?

Compressing Delta-Encoded Data

Note that at this point, we haven’t actually compressed anything; we’ve merely transformed the data in such a way that things can potentially be more compressible.¹¹

Delta coding produces a more compressible data set when it can do the following:

• Reduce the maximum value in the stream, reducing the dynamic range.

• Produce lots of duplicate values, which allows for more effective statistical compression.

The second is most likely more important because it fits in better with common statistical compression systems. However, if the results of delta coding don’t produce statistically variant data, you end up needing to take advantage of the first, which basically moves toward trying to reduce the overall LOG2 for the entire data set.

In general, taking the produced data and then throwing it at any statistical encoder should produce good compression.

Does It Work on Text?

Not really. I mean, it can work, but given that English text oscillates between early sections of the alphabet and later sections of the alphabet, you end up with a lot of positive-negative switches in the data. Plus, other systems like LZ are going to do a ton better.  

Avoiding Rogue Symbols

One of the issues with MTF is that a few rogue symbols can interrupt a nice stream of symbols that exist at the front. This is one of the more detrimental issues because it can seriously mess up your encoding, and in truth, it’s quite common in real-life data.

One solution to this is to not let symbols go to the very front of the list as soon as they are matched; instead, you need to employ some heuristic that slowly moves them to the front. The following example demonstrates how heuristics work quite well in practice.

Compressing MTF

MTF creates a stream of symbols that is expected to have a lower entropy than the source stream. This makes its output a prime candidate to pass off to a statistical compressor for further compression. Because MTF should produce a stream with more 0s and 1s, a simple statistical encoder would work fine.

MTF is unique in that it reassigns a shorter value to symbols as they recur within a short time. RLE, on the other hand, assigns the shortest codes to symbols that occur in clusters. In practice, MTF is one of the simplest forms of dynamic statistical transforms.

Ordering Is Important!

One of the issues with entropy as a unit of measure is that it fails to take into account the order of the symbols. Regardless of how we shuffle [1234567890], it always has an entropy of 4.

But we know that order does, in fact, matter greatly. For example, the LZ family of dictionary compressors takes ordering very seriously, as do the other contextual transforms we’ve shown in this section.

So if order matters, it stands to reason that if we transform the order of a data stream, we can make it more compressible.

The simplest reordering here is to simply sort our data. For example, converting [9,2,1,3,4,8,0,6,7,5] to [0,1,2,3,4,5,6,7,8,9] makes it possible for us to delta encode it as [0,1,1,1,1,1,1,1,1,1], which has a lower entropy than the source.

Sadly though, pure sorts are one-directional. That is, after you sort the data, you can’t get it back into its unsorted form without a ton of extra information to specify where it goes.

So we can’t purely sort our data, but we can get close.

BWT shuffles the data stream and attempts to cluster groups of the same symbol near one another, which is what we call a lexicographical permutation. Or rather, with BWT you can find a permutation of the original data set that might be more compressible based on its ordering.

And here’s the best part: we can encode to and decode from BWT without having to add significant additional data to our stream. Let’s take a look.

How BWT Works

The “transform” part of Burrows–Wheeler transform begins by creating a table with all the shifted permutations of the input stream.

For example, we have the word BANANA, again, and write that in the first row of our table. Then, on each following line we perform a rotational shift to the right by one character of that word. That is, shift all the letters over to the right, and prepend the rightmost character at the front. We continue with this shifting, until we’ve touched each letter in our input string, as shown here:

Next, the BWT algorithm sorts this table lexicographically by the bolded letters as shown in the example that follows. Feels good to have things back in order, doesn’t it?

Now, we want to draw your attention to the last column of characters in the preceding example (highlighted in italics). From top to bottom, they form the string NNBAAA, which interestingly enough, is a permutation of BANANA, and has a much better clustering of letters.

And this is exactly the permutation that we’re looking for. You see, by generating our rotated permutations and then lexicographically sorting them, the final column generally produces a permutation with a better symbol clustering than the original source string.

As such, NNBAAA is what BWT should return as its output.

But before you run off, there’s one other piece of data we need to grab as well. Notice in the sorted table that follows, that the input string sits at index 3.

We’ll need that row index during the decode phase of the BWT transform because it will allow us to bridge from our more-compressible permutation back to the source string.

Inverse BWT

The remarkable thing about the BWT is not that it generates a more compressible output—an ordinary sort could do that—but that this particular transform is reversible, with minimal data overhead. 

Let’s illustrate this to confirm that it’s true. So, we want to decode a BWT, and we’re given the string NNBAAA and the row-index 3.

The first thing we need to do is regenerate the permutation table. To do this, we iterate on a combination of sorting and string appending.

We begin by writing our output string, which represents the last column, into a table.

Oddly enough, if we sort this column, it is the same as the first column in our original, sorted table.¹⁴

So, let’s merge these two columns to get a pair of letters for each row:

Let’s sort that:

Next, we prepend the original output string (NNBAAA) to it again:

Then, we sort again and continue prepending and sorting columns, until the width of the matrix equals the length of the output string.

You should immediately notice two amazing properties of this final matrix:

• This final matrix is identical to the post-sorted permutation matrix that we generated in the encoder. This means that if we’re given the final column of our sorted matrix, NNBAAA, we can recover the entire post-sorted matrix that was used to generate it.

• Remember that row index 3 that we output during the encoding phase? Because this matrix is identical to the post-sorted one from the encoder, we simply need to look at the row at that index the fourth row to recover our source input string BANANA.

Practical Implementations

Be warned!

Even with all this wonderfulness, sadly you can’t just execute BWT on your entire 50 GB file. The way this permutation transform works, you’d have to store that same 50 GB, shifted left one symbol, for each row. That’s an awful lot of extra gigabytes.

As such, BWT is what we call a block sorting transform. It breaks the file into 1 MB chunks and applies the algorithm to each of them independently. The result is an algorithm that can practically fit in the memory of most modern devices and is somewhat performant.

Compressing BWT

So, it’s apparent that BWT doesn’t actually compress the data, it just transforms it. To practically use BWT, you need to apply another transform that is going to yield a stream with lower entropy, and then compress that.

The most common algorithm is to take the output of BWT and pass it to MTF, which is then followed by a statistical encoder. That’s basically the inner workings of BZIP2, folks.