Markov and Compression

The concept of Markov chains fits nicely into our existing models because we can view statistical encoders as single-context Markov chains. Given one table of probability for the symbols of a stream, we assign codewords accordingly.

A second-context Markov chain could be created by adding a symbol-to-codeword table for each preceding symbol, such as that illustrated in Figure 9-2. Let’s see how this works.

Figure 9-2. A second-order or 2-context Markov chain uses a tree of symbol tables, as could be built for our summer vacation example.

Given the graph in Figure 9-2, to encode “Monday, Spelunking; Tuesday, Pool” we’d produce 0 1 10 1110 for a total of 8 bits. In contrast, if we were to enumerate each of the 10 states, we’d end up with something along the lines of 12+ bits to encode the same data.

From a technical standpoint, creating Markov chains for compression follows many of the rules we covered in adaptive statistical encoding (see Chapter 2); that is, reading in a symbol, dynamically updating a frequency table, and so on.

Practical Implementations

It’s worth pointing out that no one really uses Markov chains for compression. At least not in the way just described.

Consider a worst-case—but not implausible—scenario, in which you have an 8-context chain.

This means that for each node, you’re going to end up with 256 other child nodes, 8 deep. This means that you will need 256⁸ (two-hundred-fifty-six-to-the-power-of-eight!) or 16 exabytes of memory⁶ to represent your tables. Which is crazy, even by modern computing standards.⁷ As such, various derivative algorithms have been created that are just a little more practical about memory and performance than a general Markov chain. The most notable ones are prediction by partial matching and Context Mixing, which we are going to take a look at next.

The Search Trie

The main problem with any practical implementation of PPM has to do with the creation of a data structure where all contexts (0 through N) of every symbol read from the input stream are stored and can be located quickly. In simplistic cases, this can be implemented with a special tree data structure called a trie,¹⁰ for which each branch represents a context.

For example, let’s build a PPM trie for the string “ABAC”, with a maximum¹¹ allowed context of 2, as depicted in Figure 9-3.

1. Reading in the first value, “A”, appends a new node [A,1] to the root of the tree. This represents that “A” has been seen 1 time so far at context 1. (Children of the root node are context 1, grandchildren are context 2, and so on).

2. Reading the second value, “B”, adds two nodes to the tree.

   1. First, it adds an order-1 context node, [B,1]. This is useful in the case where “B” is the start of its own context chain.

   2. Second, it adds an order-2 context node [B,1] under the [A,1] node. This is to represent the chain “AB” that we’ve read through the input stream so far.

3. Reading the next “A” value has a few tricks.

   1. First, it updates the count value of the order-1 context node, (because “A” has already been encountered at that context).

   2. Next, it adds an [A,1] node as a child of each [B,1] nodes. This represents both the order 1 and order 2 contexts of “BA” and “ABA”, respectively.

4. The final symbol, “C” follows a similar process, but with a small change.

   1. We add the order-1 context node [C,1].

   2. The next step would be to add 4-order [C,1] nodes to all 3-order [A,*] nodes. You can see that on the lefthand side, this is completed fine with the [B,1]->[A,1] chain. However, on the right side, adding the new node would violate our context height restriction. So, we append nothing.

   3. As a final step, we have a valid [A,1] node at order-1, and add a [C,1] node as a child there.

Figure 9-3. Building a PPM trie with an N-context of 2. Each level of the tree represents a context. The children of the root are the first-order context. The number next to the character denotes how many times that symbol has been encountered, at that context.

This trie is beneficial, in that we can quickly query the N-minus-X contexts, given a current state. For example, given a symbol “C”, our 2-order context is “BA”, our 1-order context is “A”. This fits perfectly because it represents a sliding window of the previous one and two symbols from “C” in the “ABAC” string we encoded.

We can use this trie to represent all of the following substrings of the input, given a 2-context limit (Figure 9-4): B, BA, BAC, C, A, AB, AC, and ABA.

Figure 9-4. Strings represented by this trie: B, BA, BAC, C, A, AB, AC, and ABA.

Compressing a Symbol

In addition to providing efficient storage and fetching of substrings, the trie structure also contains counts per level. A statistical encoder can use these to build probability tables and assign encodings for each symbol, as shown in Figure 9-5.

Figure 9-5. The PPM trie, and an example of the symbol-to-codeword tables you could use for encoding.

Effectively, given a level, we only need to consider the siblings at this level and normalize their values to arrive at probabilities. For example, the context-1 counts of [B,1], [C,1], and [A,2] would represent probabilities of 25%, 25%, and 50%, respectively.

Also, note that because we can use 1-bit encodings in context-2, for every symbol encountered in context, we save 1 bit, for potentially substantial savings.

You can implement this in a straightforward fashion as a modification to the data structures we covered in Chapter 3.

Choosing a Sensible N Value

So what is the value of N supposed to be? PPM selects a value N and tries to make matches based on that context length. If no match is found, a shorter context length is chosen. As such, it seems that a long context (large value of N) would result in the best prediction. However most PPM implementations skew toward an N value of 5 or 6, trading off memory, processing speed, and compression ratio.

There are variants of PPM, such as PPM*, which try to extend the value of N and make it exceptionally large. You can do this with a new type of trie data structure, and significantly more computational resources than PPM. This usually results in about 6% better savings than straight-up PPM.

Dealing with Unknown Symbols

Much of the work in optimizing a PPM model is handling inputs that have not already occurred in the input stream. The obvious way to handle them is to create a “never-seen” symbol which triggers the escape sequence. But what probability should be assigned to a symbol that has never been seen? This is called the zero-frequency problem. 

One variant of PPM uses the Laplace estimator, which assigns the “never-seen” symbol a fixed pseudo-count of one. A variant called PPMD increments the pseudo-count of the “never-seen” symbol every time the “never-seen” symbol is used. (In other words, PPMD estimates the probability of a new symbol as the ratio of the number of unique symbols to the total number of symbols observed.)

PPMZ presents one of the more interesting variants. It starts in the same way as PPM* does, by trying to match a N-context probability for the current symbol. However, if a probability isn’t found, it switches to a separate algorithm called a Local-Order-Estimator and uses the basic PPM model, with a completely separate predictor.

Types of Models

As we discussed earlier, adjacency is a very important topic to data compression. Algorithms such as LZ, RLE, delta, and BWT all work from the assumption that the adjacency of our data has something to do with the optimal way to encode it.

When introducing Markov, it’s easy to present it in this same light. Creating an adjacency-based context is easy to do (“if A follows B”, etc.). But in reality, this is just one way to create a contextual correlation between symbols. For instance, you might create a context as all values in an even index, or context might be derived from values which are clustered around a certain numerical range. Basically, adjacency and locality are the simplest forms of contextuality, but by no means are they the only ones.

With this mentality, it makes logical sense that there might be other signals in the data stream that could help us identify the right way to encode the current symbol, signals that have nothing to do with context or adjacency. Identifying and describing the relationships between symbols is what we call models. By modeling the data, we understand more about the various attributes it contains, and can we better describe the current symbol.

In reality, models can be anything and can change depending on the type of data you have.

For example, images care a lot about two-dimensional locality; that is, a pixel color generally has something to do with the adjacent colors above, below, and on each side of it, and we can take advantage of that for compression. This model doesn’t work for text though. There’s generally no observance that a character has any proper relation to one below or above it.¹²

In programming, after compiling your high-level instructions into bytecode, there’s a completely separate model. A single byte can describe an instruction, followed by a set of variable-length bytes that describe the input to that function. Because code tends to have common patterns, you could model that if you see a “Jump to this instruction” command, there’s most likely going to be a “push the variables onto the call stack” command around here somewhere, as well. So in this case, it’s not important to note the adjacent bytes, but the commands themselves.

Music is a completely different beast. You could create models to represent the bass line, or guitar riffs, and take into account the lengths of courses or bridges that are involved.

The point here is that there’s thousands of different ways to model your data if you just know enough about it to ask the right questions. So the problem becomes more difficult in some cases, because now, we’re not talking about generic algorithms, but more asking the question, “Do you understand enough about your data to model it properly?”

One of the pioneering compressors in the context mixing space, PAQ, includes the following models:

• N-grams. The context is the last N bytes before the predicted symbol (as in PPM).

• Whole-word n-grams, ignoring case and nonalphabetic characters (useful in text files).

• “Sparse” contexts. For example, the second and fourth bytes preceding the predicted symbol (useful in some binary formats).

• “Analog” contexts, consisting of the high-order bits of previous 8- or 16-bit words (useful for multimedia files).

• Two-dimensional contexts (useful for images, tables, and spreadsheets). The row length is determined by finding the stride length of repeating byte patterns.

• Specialized models that are only active when a particular file type is detected, such as x86 executables, or BMP, TIFF, or JPEG images.

And PAQ is no joke. It’s constantly at the top of the Large Text Compression benchmark, and one of the newer versions, ZPAQ, attained second place in a contest compressing human DNA.

Types of Mixing

Just off the cuff, how would you mix two given values? Average them? Add them together? Maybe weigh them differently based upon user preference or prior input? And these questions become more complex as you start using multiple models. After you have a set of 50 inputs, how do you combine models to pick the best compression?

Thankfully, statistics have mostly solved this problem for us. There are two types of approaches to mixing the outputs from different models together.

Linear mixing is a process of using the weighted average of the predictions, where the value comes from the weight of the evidence.

In our previous example, we were trying to figure out the probability of you going to the gym given how often you go to the gym, and how often you eat pasta. Now, these two values have a different evidence weight, in that one might be proving a more reliable value due to more tests/samples taken. For example, if you’re considering how pasta influences your gym attendance at a lifetime level, it would have more sample data and thus be a more reliable form of predictor than, say, your frequency of going to the gym in the last week.¹³ As such, we give one more weight in the mixed model due to it having more evidence.

Logistic mixing, on the other hand, is crazy.

You see, with linear mixing, there’s really no feedback loop to indicate to you whether the weight you assigned to a model was correct toward predicting how to compress this data. So, if your input stream changes, and the weighting of your models stays the same, you can end up bloating your output stream.

To address this, logistic mixing uses a neural network (artificial intelligence!) to update weights and reassign them based upon what models have given the most accurate predictions in the past. The trick here is with correcting the current weightings. Suppose that the current weight selects model A to encode this symbol in 12 bits. But model B would have been the correct choice, with an 8-bit encoding. The encoder outputs the 12 bits and then updates its weights so that when all of these models produce these same values next time, model B has a higher chance of being chosen.

The only downside to this is the massive amount of memory and running time it takes to compress the data.  If you look at ZPAQ on the LTCB, it took 14 GB of memory to compress a 1 GB file. All that modeling data has to go somewhere, right?