Building a Huffman Tree

In summary, Huffman discovered that if he used a binary tree, he could use the probabilities from the symbol table alongside the branches of the binary tree to create an optimal binary code.

Here’s a tiny—and incomplete—example table:

So, let’s put these on sticky notes, sort them by probability, and call them the leaves of the binary Huffman tree that we are going to build from the bottom up (see Figure 5-1).

Figure 5-1. The starter nodes sorted by their frequency of occurrence.

First, take the two symbols with the smallest probabilities, move them one level deeper, and create a parent that is a combination of the two symbols and their probabilities, as depicted in Figure 5-2.

Figure 5-2. Creating a combined parent node for B and C.

Second, repeat this process for the remaining A and combine it with BC to create the new root ABC, which represents our complete set of symbols (see Figure 5-3).

Figure 5-3. Combining A and BC to create the ABC root tree.

Generating Codewords

To set up the tree for generating codewords, assign 0s to all left branches, and 1s to all right branches (Figure 5-4).

Figure 5-4. Assigning 0s and 1s to the branches.

Finally, to find a code for a given symbol/leaf node, “walk the tree” from the top down,² and line up the 1s and 0s from most significant bit (MSB) to least significant bit (LSB)—that is, left to right.

For example, to determine the code for B, start at the root, traverse to the right (1), then to the left (0), resulting in 10 as the encoded representation (Figure 5-5).

Figure 5-5. Walking the tree to find B’s code.

Finally, repeat this same process for all the remaining symbols/leaves of the tree (Figure 5-6).

Figure 5-6. Codes for all symbols (leaf nodes) in the tree.

Encoding and Decoding

Congratulations! You now have constructed a VLC assignment for your unique data set, which you can use to encode your data. Walk through the input stream, and for each symbol, write the appropriate codeword to the output.

As with other VLCs, for decoding purposes, you need to transfer the symbol-to-codeword table along with your compressed content and mirror the standard VLC decoding process

Because creating the tree takes more “effort” (uses compute resources) than passing the symbol-to-codeword table (increases data stream size), you should always prepend your data stream with the codeword table, not re-create it at the destination.³

Practical Implementations

Folks have done a crazy amount of amazing analysis on Huffman codes over the past 50 years or so, and have come up with variants to ensure that they operate within some performance or memory threshold, or produce various codes that are skewed toward a specific probability. Entire books have been written about this algorithm and its complexity and optimizations.

But that’s all we’re going to say about it—you’ve got enough of the mechanics to understand how your data is interacting with algorithms when you begin to try them.

Finding the Right Number

Arithmetic coding works by transforming a single string into a number that requires fewer bits to represent than the original string. For example, “TOBEORNOT” could be represented by 236712⁶, whose ceil(–log₂(236712)) = 18 bits. Compare this with the ASCII version of “TOBEORNOT,” which sits at 56 bits.

But this isn’t as easy as just picking a number at random, as we did earlier. Arithmetic coding goes through a complex process of calculating this number from an input stream. The trick is that choosing the number is actually a modification on the binary search algorithm that we introduced in Chapter 2 (you know, the chapter you were not supposed to skip).

If you recall from that chapter, you can use a binary search to output 0/1 bits to catalog the search’s no/yes decision process as we were checking whether a number fit into one of two spaces against a pivot value. But what if we had four spaces? Each decision would then output 2 bits (for one-fourth of the number range, respectively). Still makes pretty good sense, right?

Arithmetic coding kinda works along this path, but with some serious modifications.

Arithmetic coding creates a number space [0,1)⁷ and subdivides it based on the probability of symbols in the data stream. So, “A” would be given [0,0.25) if its probability were 25%, and B, with a probability of 10%, would then be given [0.25,0.35), and so on, as shown here:

When the encoder reads a symbol, it finds the range for that symbol. For example, if A were read, the range [0.0,0.25) would be used. After a symbol is read, the encoder will subdivide that symbol range and assign new range values for symbols proportionally.

For example, if our stream provided three A symbols in a row, the encoder would subdivide the A range three times, as illustrated here:

Basically, each symbol recursively divides its range until we reach the end of the input stream. After that’s done, we have a final range of values, such as [0.253212, 0.25421). The number you output, is a value in this range. So for our example, for an input string of AAA, the output could be anything in the range [0,0.015625).

Encoding

Let’s encode a complete example with three symbols, R, G, and B, with respective probabilities of 0.4, 0.5, and 0.1. We assign them ranges in the interval [0,1) according to their probability, as shown in the following table (note that the entropy of this table is 1.36):

The following diagram shows the same information represented in number-line form of the ranges for three symbols, R, G, and B:

Using this probability setup, let’s encode the string “GGB.”

The first symbol we read from the input stream is “G.” Because the interval of G, according to our table, is [0,4,0.9), we subdivide the number space between the values of 0.4 and 0.9 according to probabilities, which gives us a new range of intervals, as shown in the updated figure and table that follow.

We now read the second symbol from the input stream. It’s another G, so we again subdivide the G range of numbers, which is between 0.6 and 0.85, and update the intervals as shown in the following figure and the table.

And finally, we read and subdivide again for the letter B, and update the figure and table once more.

Congratulations! You just arithmetically encoded a stream!

Picking the Right Output Value

So, we’ve subdivided the range intervals, but what number do we output as the final result?

Our final interval for B is [0.825,0.85), and any number from that range will serve the purpose of letting us reconstruct the original string, giving us some choices between 0.825 and 0.849999.... This being a book about compression, we want to use the number that we can represent with the fewest bits (and as close to our 1.36 bits entropy goal) as possible.

The number in this range that requires the fewest bit is 0.83.

Finally, because the decoder “knows” that this is a floating-point number, we can drop the leading 0 for additional savings and end up with 83, which with log₂(83) = 7 bits, gives us 1.42 bits per symbol, which is almost at entropy.

Decoding

Decoding from this final number is pretty straightforward—basically the encoding process in reverse. Just as with encoding, we begin by creating the segmented range between [0,1) based on the probabilities, as demonstrated here:

We then take our input value, 83, add the leading “0” to get 0.83, and find which interval it falls into. We output the symbol associated with that interval.

In our case, 0.83 falls in the range 0.4,0.9, giving us the value G to output.

We then subdivide the G space according to the probabilities (same as when we were encoding).

To get our second symbol, we repeat the process. Our input value is still 0.83, which falls (again) in G’s range, so we output another G, and subdivide again, as shown here:

Continuing one more time, 0.83 falls in the range 0.825,0.85, which is the range for the symbol B, so we output B.

This gives us our final decoded stream as GGB.

Pretty nifty, eh? Our decoding process basically works by drawing a line through each recursive space and outputting whatever symbol we land in at that time.

Practical Implementations

The adoption and dominance of arithmetic coding since its patent expiration in the 2000s has led to a plethora of topics that relate to practical implementations of this algorithm. More impressive is how many of them have been modified for specific codecs, such as the binary-only versions used by JPG and H.264 codecs. Those lossy compression methods are out of scope for this book, but there are plenty of resources out there if you’d like to investigate more.  

Encoding and Decoding Using a Transform Table

The tANS variant of ANS works by moving around a table of values.

As an example, let’s just assume that you’re given the table that follows. Ignore how we’ve created it, we’ll get to table creation in  a moment.

Given the preceding table, let’s walk through how to encode the input string BAA:

1. Given an input stream BAA, we begin with a pair of [row index, input symbol], which is [1,B].⁹

2. We use this pair to reference a location in the table from which to read our next value. We grab the value at cell [1,B] in the table, which is 3, and make that our new row index for [3,?].

3. To get the column index, we then read the next symbol, which is A, completing the new table index [3,A].

4. Again, we grab the value at that cell in the table, which is 7.

5. We read the next symbol, which is also A, we end up with [7,A].

6. And the value at that index is 16.

7. We can continue forward with this until we hit the end of the table (or the end of the string).

8. The transform of this table takes BAA and results in [3,7,16].

Decoding works in the exact opposite way.

1. We begin with the last value, 16.

2. We then search the entire table and find that 16 sits at row 7, column A.

3. We output A as our symbol and 7 becomes the new current value.

4. We search the table again and find that 7 is at row 3, column A.

5. We output A, again, and set 3 as our new value.

6. When we search for our last 3, we see that it’s at row 1, column B. Because we’re in row 1, we know we can’t move further, so we’re done decoding.

7. The decoded stream is [A,A,B] because we were decoding the list from back to front.

8. Our last step is to reverse to get to the original BAA.

You can see that this table lets us encode an input string and decode it properly, given a nifty way to move around it.

Creating the Reference Table

The core of this algorithm is the magical reference table, which makes it possible for these types of transforms to occur. The table itself is created by first assigning each symbol a column in the table, such that the symbols are sorted by probability, left to right from highest to lowest.

In the previous table, the symbols A, B, C have the probabilities P([A,B,C]) = [0.45,0.35,0.2], and are each assigned a column of the table.

From here, we must fill in values into the table, adhering to a few specific properties:

• Every value in the table is unique (no repeats)

• Numbers in each column are sorted from lowest to highest

• Numbers in every row are larger than the number (index) of that row

If you can adhere to these principles, the encoding/decoding transform that we’ve shown should work just fine. But for tANS to become a true entropy encoder, there are two more properties that we must consider:

Determining the number of values in a column

The number of values in a column is equal to the probability of the column-symbol, multiplied by maxVal.¹⁰

Determining the numbers in each row

Numbers in a row are selected to align with the probability of occurrence for a symbol, such that if we divide the row-number by a value in a column, the resulting value is (roughly) equal to the probability of that column’s symbol.

Let’s take a closer look at these properties for our example.

The first property is somewhat straightforward. The largest value in the table is maxVal = 31. In accordance with the property, we subdivide the space of maxVal = 31, assigning P(s) * maxVal numbers to each symbol-column. For our example:

• B has P(B) = 0.35, which results in a column that is floor(0.35 * 31) = 10 elements high.
• The same goes for C (0.2 * 31 = 6).
• However,  the most-probable symbol, in the leftmost column A, has P(A) * maxVal + 1 = 0.45 * 31 + 1 = 14 rows. That’s because the most probable symbol adds an extra row for the maxVal.

This has the effect of subdividing the maxVal space, giving slots for each symbol, equal to its probability.¹¹

The second property defines that values in a row can be calculated by multiplying the row number by the probability of each symbol.

For our example table, the probabilities for the symbols S = [A,B,C] are P(S) = [0.45,0.35,0.2], and picking a row, say row 5, the values are 12, 14, 25.

When we divide those values by the row index, we get a result that’s pretty close to the symbol probabilities: [ 5 / 12, 5 / 14 , 5 / 25] = [0.41666.,0.357,0.2 ] ~= P(S).

This second property must remain true for all rows. You can see that for column A, each row has a value that’s about right with regard to P(A) = 0.45.

So, why is there sometimes a discrepancy between the assigned table value and the numerically calculated table value? It’s to avoid collisions.

Each value in the table must be unique. However, because we are rounding numbers up and down, we can end up with collisions at a few spots. For example, 1 / P(C) = 5, whereas 2 / P(B) = 5.714.

We resolve collisions by iterating forward to find the next highest value that is not yet used in the table. For example, in the case of assigning a symbol to column B, for row 2 we can’t use the value 5 (because it’s already used in row 1), so we try the next greater value, 6, which hasn’t been used in the table yet, and assign¹² that value.

By adhering to these two properties, you can create the entire preceding table that will properly encode/decode values and compress your data.

Using ANS for Compression

We previously identified how to move around our reference table; however, the output didn’t result in statistical compression. To achieve compression, we need to tweak our algorithm just a tad:

• First, instead of starting with row 1, our starting state/row is going to be maxVal.

• Second, for each symbol we read from the stream:

  • Set targetRow to the column height for that symbol.

  • Bitshift the state value right until it is smaller than the targetRow.

  • Each bit that is dropped from state during the shift, should be output to our encoded bitstream.

Let’s walk through an example encoding of the string “ABAC”, given the above modifications and the table we previously presented:

1. Because the state = maxVal = 31 (binary 11111), that is what we start with.

2. Read the first symbol, which is A, giving us [31,A], and setting targetRow to 14.

3. Because 31 > 14, we start shifting and outputting bits.

   1. We shift state right once, to 1111, truncating the rightmost 1 to our output stream→1.

   2. State is now 15, which is still larger than 14; thus, we shift right again, making state 111 and outputting another 1 bit to the output stream. →1

   3. State is now 7, and we’ve truncated and written out two bits (11).

4. We now assign state to the table value at [7,A], which is 16 (binary 10000).

5. Read the next symbol, which is B, resulting in [16,B], and setting targetRow to 10.

6. Because 16 > 10, we start shifting and outputting bits.

   1. We shift 16 right once to set state = 8 (binary 1000), emitting a 0 to the output. →0

   2. Because 8 <10, we can move to the next symbol.

7. We set state to the table value at [8,B], which is 22 (binary 10110).

8. Read the next symbol, which is A, resulting in [22,A], and setting targetRow to 14.

9. Because 22 > 14, we shift and output bits. We shift right to get state = 1011, emitting 0. →0

10. We set state to the table value at [11,A], which is 24 (binary 11000).

11. Read the next symbol, which is C, resulting in [24,C], and targetRow to 6.

12. Because 24 > 6, we start shifting and outputting bits. We shift twice to get state = 110, emitting 00. →0 0

13. We set state to the table value at [6,C], which is 30 (11110).

14. Because our stream is now empty, we output our state value (11110) to the stream. →11110

15. Our final stream is thus: 11000011110 and 11 bits long. Plus the bits taken up by the symbol probabilities table.

Decoding Example

Decoding works in the opposite order:

1. Read in our frequency data from the compressed stream.

2. Create the table from the symbol frequency information.

3. Read a value from the stream.

4. Find its location in the table.

5. Output the column as the symbol.

6. Make value = row.

7. Read in some new bits.

It’s worth noting that in this example our maxVal = 31, or 5 bits of precision.

After creating the table, we work through our encoded 11000011110 stream backward as follows:

1. Working with 5 bits for our state targeted, read the last 5 bits 11110(30) of the stream.

2. We find the only number 30 in the table at location [C,6].

3. Output the symbol C.

4. 6 or 110 is only 3 bits, so we need to read 2 more from the stream (always try to make 5 bits).

5. Read the last 2 bits, 00, and append them to 110, resulting in 11000 24

6. Find the only location of 24 in the table at [A,11].

7. Output the symbol A.

8. 11 (binary 1011) is only 4 bits, so read 1 more bit from the stream, giving you 10110 (22).

9. Find 22 in the table at [B,8].

10. Output the symbol B.

11. 8 (binary 1000) is only 4 bits, so read 1 more, giving you 10000 (16).

12. Find 16 in the table at [A,7].

13. Output the symbol A.

14. 7 (binary 111) is only 3 bits, so read 2 more, giving you 11111(31).

15. Because this value now equals our maxValue (11111), we know this to be the end-of-message marker, so we quit decoding.

16. We reverse the string and have returned to ABAC.

So Where Does the Compression Come From?

Compression comes from the bit-wise output.

Because the least probable symbols have shorter columns, the valid row values are farther removed (in bit distance) from the max-symbol. Therefore, more right-shifts are required to get to the lower row indexes, which means more bits are pushed to the stream for each iteration. So, less probable symbols result in more bits being output to the final stream.

As we mentioned previously, giving more bits produces a higher precision for your space (and thus, a larger maxVal). This causes the values in the reference table to have fewer precision collisions, because the larger space allows for integers to more closely match the value given by P(s) * maxVal. Recall that collisions in the table result in linearly searching for a larger value that hasn’t been used yet. When encoding, this difference between the computed value and the actual value can result in more bit-shifts to get the state value below the target row value. When precision is high, there are fewer collisions, producing less bloat per value and fewer bits being shifted to the output stream.

The downside, though, is that larger precision produces a larger reference table, which takes significant time to create and significant amounts of memory to hold. So ensure that you find the right trade-off between performance and memory for your particular implementation.