![[fadden-logo]](../../images/faddenlogo.gif)
Hacking Data Compression Lesson 5 Adaptive Encoding
By Andy McFadden
GEnie A2Pro Apple II University - Copyright (C) 1992 GEnie
Today's lesson is on adaptive coding techniques. We begin with a
justification of why it's a Good Thing, and drop into a discussion of
adaptive Huffman. A description of the elusive splay tree compression
is also presented.
-=O=- Greetings and Adaptations
If you followed the discussion in last week's lesson on Huffman
encoding, you should be familiar with some of the issues involving
adaptive, semi-adaptive, and static models and encoders. To summarize
briefly:
- static schemes use a rigid set of probabilites, determined before
examining the data to be compressed.
- semi-adaptive schemes choose a set of probabilities, and use them
throughout the entire file. The choice can be made by scanning the
file in advance or using some sort of file type mechanism to determine
what the contents should be. The probability set or dictionary is
either stored in the program or transmitted before the data.
- adaptive schemes start out in a particular state (could start with
no knowledge at all or from a basic set of probabilities), and then
change the probabilities as the input as processed.
We've seen examples of all of these. Differential encoding, the
static-dictionary digram compressor, and the MacWrite encoder are all
static; last week's Huffman encoder is driven by a semi-adaptive model
based on character frequencies; and the MTF scheme described in
lesson 3 is adaptive.
-=*=-
We have already seen that adaptive schemes can lead to cleaner
implementations (no tables to shuffle around, no extra scanning
passes, etc). However, there are some other advantages.
In section 3.2 of _Text Compression_, Bell/Witten/Cleary state:
Given a set of conditioning classes with K members, an
alphabet with q symbols, and a message of length n, there
are adpative models that will take at most Kq log n bits
more than the best possible nonadaptive model.
This is probably not very meaningful, especially since we never really
went into what "conditioning classes" are. I've presented it because
there are two interesting conclusions which can be drawn: first,
adaptive models will do only slightly worse than static models; and
second, Kq log n is approximately the number of bits needed to
represent a model of the message, so adaptive models will be about as
efficient as semi-adaptive models.
It can also be shown that adaptive models are "robust", meaning that
at worst an adaptive model will expand the input only slightly. It
should be intuitive that you can make a completely static model do a
really lousy job (e.g. by feeding a file full of '%'s to a static
model of English text).
-=*=-
If I'm doing my job correctly, you should now be convinced that, at
worst, an adaptive model will do only slightly worse than a static or
semi-adaptive model. However, there are cases where an adaptive model
will do considerably better than either.
Suppose I'm using some sort of multi-media format with text, graphics,
and sound all in one whopping big file. If we suppose that none of
the data within the file is compressed (which is a silly assumption,
but hey, this is a contrived example anyway), then we have three sets
of stuff to deal with.
Suppose we run a static or semi-adaptive Huffman compressor on it. A
static set of probabilities is going to gag on the sound and graphics,
but will do a nice job on the text. A semi-adaptive compressor will
end up with a rather flat set of probabilities, because it will have
merged the frequencies from the text (assume English), the graphics
(which will likely tend toward a small set of values), and sound
(which looks almost random).
Since an adaptive Huffman compressor changes the probabilities as it
reads in characters, it will adapt to each section of the file in
turn. This will allow it to compress each section with the best
possible values for the character probabilities.
This sort of adaption can also be useful in just plain text files. If
you break away from normal writing to display ASCII cow art, the
distribution leans toward spaces and characters like '|', '/', '\',
and 'o'. Static models just get bogged down, while adaptive models
can take advantage of the local changes.
-=*=-
One important question is, how quickly can (or should) the model
adapt? If it adapts too slowly, it will miss out on local phenomena
like cow drawings. Too quickly, and the probabilities will be
inaccurate, leading to poor compression. The correct answer is, as
usual, "it depends." For natural languages like English, you usually
want to base your predictions on the last few thousand bytes of data.
A very common way to increase the value of recently-seen data is to
"forget" old data. This can be done with a "sliding window"
(discussed in the upcoming LZSS lesson), by explicitly weighting
recent events, or by "forgetting" old information. In a model based
on character frequencies, we get a certain amount of forgetfulness if
we are restricting the size of the frequencies to prevent overflow.
For example, if we periodically halve the frequency counts, we are
essentially cutting the weight of previous data by 50%. The next time
we cut it, the original statistics are reduced to 25%, and so on.
This isn't always a good thing - local changes might be temporary -
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
but for most kinds of data, recent events say more about what to
expect next than events which happened near the start.
-=*=-
All is not sunshine and roses in the adaptive compressor world. There
is one major down side to adaptive schemes: the cost of updating the
model at every step.
The exact cost varies - Huffman is fairly expensive, LZW is almost
free - but it's never zero. There may be additional speed penalties
depending on the implementation; for example, last week's Huffman
encoder stored the bit patterns in an array while it was encoding. An
adaptive encoder is continuously changing the bit patterns, so this
method is no longer feasible.
As we saw last week, it is wise to limit the frequencies to some
value, so that the frequency table and output codes can be implemented
efficiently. However, we also saw that this meant slashing all of the
frequencies in half whenever the total frequency reached a certain
value.
At first, this doesn't seem significant; ALL of the frequencies have
been cut in half, so the tree doesn't need to change. Life, however,
is unfortunately not so simple. Because of round-off errors, it's
possible for the balance to shift, requiring nodes to exchange
positions. Because there's no easy way to adjust the tree to
compensate, it's necessary to rebuild the entire tree with the new
frequencies.
-=O=- Splay trees
Let me explain something up front. Very little has been written about
splay trees in compression texts. The only place I know of that
discusses them is "Application of Splay Trees to Data Compression", by
Douglas W. Jones, Communications of the ACM, August 1988, and I've
never even read THAT.
What I DO have is a piece of code which I pulled off the net about
four years ago and managed not to lose. Everything I know about splay
trees comes from deciphering that code.
Why bother? Why are splay trees interesting? Because they can
approximate an adaptive Huffman encoder without ANY frequency counts
or other garbage. All of the information is contained in the shape of
the tree itself.
It turns out that the cost of updating the tree is about equal to
adaptive Huffman, and the compression performance is slightly worse,
so there's really nothing to gain from using them (consequently,
there's no assembly code for them in this week's lesson). There is
one big loss however: since there are no frequency counts, there is no
way to control the maximum height of the tree (at least, not without
maintaining some expensive auxilliary data structures). This means
that the maximum code length is equal to N bits, where N is the number
of symbols. Outputting 256 bits for a rare symbol might be efficient
coding, but it's a real drag to implement.
-=*=-
How do splay trees work? Fine question. It's actually quite a bit
like Huffman, in that you have a binary tree, and output 0 if you go
left and 1 if you go right. The only real difference is in the tree
update routine, which is remarkably simple.
Suppose you have a tree which looks like this:
a
/ \
/ \
b c
/ \ / \
/ \ / \
w x y z
If you received the character corresponding to node w, you would swap
w and everything below it (i.e. w's "subtree") with node c's subtree.
Basically, you go one up and one over (the brother of the parent), and
swap. So the result would look like this:
a
/ \
/ \
b w
/ \
/ \
c x
/ \
/ \
y z
(If the next character you got corresponded to node c, you'd end up
switching things right back.) Changes to the other side of the tree
are just reflected across... if node z got updated in the first tree,
it would be swapped with node b. If node z got updated in the second
tree, it would be swapped with node x.
If the tree were taller (and proportionately harder for me to draw),
we would propagate the changes up the tree by updating the "local
root" node. For example, when node z got updated in the second
example, it was swapped with x; b was the "local root", the parent of
the parent. If node a had a parent, then b would've been swapped with
a's brother, and so on up the tree.
We stop when we hit the root or the level below the root.
-=*=-
Why does this work? Why does it even come CLOSE to Huffman? Fine
question. From this example, it should be clear that when a character
appears, it bubbles to the top rather quickly. Each swap moves the
node one level closer, and there can be more than one swap if the tree
is tall enough. Because it's possible for nodes to "oscillate", it
seems likely that frequently seen characters will tend to "hover" in
the same region of the tree. This means that frequently seen
characters will be given short codes, which is what we want.
I suspect that the reason this doesn't do as well as adaptive Huffman
is that it adapts too quickly. Infrequently seen characters will end
up at the bottom, but will rise quickly when encountered. This may be
useful in certain situations, but doesn't model English text very
well. The problem is that you can only capture so much state in the
shape of a tree with 256 nodes.
Anyway. I haven't played with this enough to give a solid analysis.
Read the CACM paper if you're really interested.
-=O=- PROGRAM (Adaptive Huffman)
The model used is the same as last week's: an order-0 character
frequency model. The data structures we will use look very similar,
but with some interesting twists. The binary tree is again stored as
a collection of flat arrays.
First, we have the table of frequencies, with one entry for each
symbol and internal node. Our set of symbols includes all 256
characters plus $100 for the stop symbol. Recall from lesson 4 that
the frequency value of an internal node is the sum of the frequencies
of the children. All of the leaf frequencies are initialized to 1 to
avoid the zero-frequency problem.
Next, we have the "parent" array. At first, it has three distinct
levels. The first level, from 0 to 256, represents the leaves; the
pointers all point to internal nodes. The second level, from 257 to
512, represents the internal nodes (256 internal nodes for 257
characters, remember?) The root of the tree is at the very end in
node 512. The third level is actually BELOW the leaves despite being
above it in the array. It has one entry for each character, and
points to the corresponding leaf.
When we start updating the tree, the leaves and internal nodes will
shift around the first two levels. The pointers in the third level
will continue to track the leaves around, so that when we are encoding
symbols we know where to start, and when decoding we know when to
stop. Remember, encoding walks up the tree, decoding walks down.
The "son" array holds pointers to the child nodes for every entry in
the first two levels. The pointers in the leaf nodes point to the
third level, so that you can tell when you've hit the bottom of the
tree by looking at the size of the index in "son" (if it's larger than
the root, then you are about to reach the third level, and thus are in
a leaf). Besides acting as a flag, it also tells us which character
the leaf represents.
Note that each node has two children; they are found at son[i] and
son[i] +1 (so the brothers are always adjacent).
This may all seem a bit confusing, but it leads to a remarkably
compact and efficient implementation. Take a careful look at
StartHuff(), and figure out what is going where. Make a note of the
two sentinel values in the frequency table and in parent.
-=*=-
encode() and decode() are pretty dull. encode() just keeps calling
EncodeChar() with the character it gets, and decode() keeps calling
DecodeChar() and outputting what it gets back.
EncodeChar() is mildly interesting. It starts at the leaf and walks
up the tree, pushing bits on as it goes. The bits are pushed on at
the left edge and move to the right. When it reaches the root, it
transmits the bits. This is just doing what the static Huffman coder
did last week, but here we have to do it every time instead of
computing it all at once.
DecodeChar() is also only mildly interesting. Since we're decoding,
we take the input one bit at a time, and walk from the root down until
we find a leaf. The character we return is determined by the tree
position. As you look at the code, remember that 'T' is the size of
the tree, so c+T is the position on the third level (the one which is
effectively below the leaves).
-=*=-
The update() routine does a moderate amount of work for each
character. However, after the first 32K (or so) characters, and
roughly ever 16K thereafter, the tree will be entirely rebuilt. I'll
explain that part in a bit. (Note that the frequency of an internal
node is equal to the sum of the frequencies of its children. If you
carry this up the tree, you will see that the frequency of the root is
equal to the sum of the frequencies of the leaves. Thus, we don't
need to maintain an extra "total frequency" counter; the value is in
the root.)
In the average case, the frequency of the leaf for the character we
just got must be increased. However, since the parent's frequency is
the sum of the frequencies of its children, we need to propagate the
change all the way up the tree. Also, since we need to change the
shape of the tree adaptively, we have to swap the node if its
frequency exceeds that of its neighbors.
The code is sort of strung out, but it's basically this:
(1) increment the node's frequency
(2) if we're now larger than our right neighbor, then
(2a) find the largest node that we are still larger than, and
(2b) swap with it
(3) continue up the tree
When the node moves, it doesn't take its children with it. The two
nodes are detached, swapped, and reattached. The reason for doing the
search instead of just swapping is that there could be a span of nodes
with the same frequency.
-=*=-
The reconstruction routine is also pretty simple, though the code is a
bit messy. It starts by taking all of the leaf nodes and collecting
them on the first level of the tree. While we do this, we cut the
frequencies in half, taking care that none of them reach zero
(this uses the same (val+1)/2 method as last week).
So now we have the entire first level of "freq" and "son" set, and the
"prnt" array is pretty much invalid. The next step is to set the
internal nodes while rebuilding the tree according to the frequencies.
The loop uses a trick from StartHuff(), where we step through the kids
by two and the internal nodes by 1, ending up at the root at the same
time. This uses the fact that the sons of node i are at i/2 and
i/2+1.
Anyway. At each step, we look backward through the tree to see if we
already created nodes with higher frequencies. If we find some (which
can be in a leaf or in an internal node), then we slide all
intervening nodes forward, and put the new node into position below
them. This shapes the tree. Is it the most efficient way to go about
it? Maybe, maybe not; it depends on the hardware. It's really very
simple once you see the algorithm through all the i's, j's, and k's.
The final step in the reconstruction is to set the "prnt" array to
reflect the new order. This just steps through the tree, and sets the
parent pointer for the son of each node. Note that internal nodes
have two kids, and leaves have one child (a pointer to the node on the
third level).
-=*=-
The assembly code supplied this week began its life as a direct port
from the C code, but got rearranged slightly for optimization. I had
to "dumb it down" to make it readable for the class - the file was
more than twice as large as it is now because of unrolled loops. I
did leave some of the fancy stuff in, along with some pointers for
optimizations.
Still, it'll be easier to understand the C code, so even if you don't
know C it might be best to have both in front of you.
One thing I had tried but gave up one was pre-loading the tree with a
set of frequencies. The idea was that, for English text, it would
improve compression and reduce the number of adjustments that would
have to be made to the tree. It turns out that this implementation
adapts quickly to the input, so very little was gained in terms of
compression ratio. As far as speed goes, the initial sorting takes
about as long as it does to shift the tree around, so there was little
gain there. (This could be fixed by pre-sorting the static frequency
table, but you're still doing a reconst() at the start, at 16K, and at
32K, whereas in the normal case you do the first reconstruction at
32K. That's two extra reconst() calls, which are not trivial.)
In case you want to play with it, I left the code and a table for
English in the source file, AIFed out.
-=*=-
There's a file in the "Test" subdirectory called "Zippy1.1.b". It's a
ShrinkIt archive packed in BinSCII format (which is similar to
uuencode or Mac BinHex format). Basically, BinSCII takes 8-bit binary
data and expands it to occupy 6 bits of every byte. This is useful
for posting to Usenet or sending through mail systems which don't like
8-bit data (stuff like control characters or even stray spaces may get
eaten, destroying the contents of the file).
If you try to pack the file with ShrinkIt, you won't accomplish much.
LZW rarely compresses BinSCII data by more than 10%. On the other
hand, Huffman does fairly well. Try it and see. Be sure and see how
many bits per symbol the output requires, keeping in mind that BinSCII
uses 6 bits out of every byte.
-=O=- PROGRAM (Splay Tree)
As stated earlier, only C code has been provided. I did provide the
splay() routine itself in assembly, as "splay.fragment".
There are three arrays, "left", "right", and "up", which contain the
left child, right child, and parent pointer for each node. We have
257 leaves and 256 parents, but the tree is upside down compared to
the Huffman trees we've been building: the root is in entry zero, and
the leaves begin at 257. The initialize() routine just sets it up as
a fully balanced tree.
The encode() and decode() routines work just like they did for
Huffman, except that in this case encode() puts the bits into an
actual heap array, since the size isn't limited to something nice like
16 or 32 bits. The heap is declared with 514 entries (which
corresponds to the size of the "up" array), but I don't think it can
go past 257. The encode loop stops when it hits 0 (the root), and the
decode loop stops when it finds a child pointer larger than 257 (a
leaf). This routine also uses an explicit stop character.
-=*=-
The splay() routine itself is a straightforward implementation of the
algorithm described earlier. It's kind of icky and uses 1-character
variable names, but it really isn't doing anything fancy. There may
be a more efficient way to implement this, but it translates fairly
well to assembly as it is.
The "a = c" at the end is just a polite way to terminate the loop.
Dunno why the author did it that way, but there it is. The "handle
odd node at end" comment doesn't make sense to me, either.
-=O=- DEEP THOUGHTS
- Last week's semi-adaptive Huffman compressor halved the
probabilities whenever the total reached about 4K. If you have a
large file with character distributions which change periodically
(like the text/graphics/sound example in today's lesson), will the
probabilities accurately reflect the distribution in the file as a
whole?
- The loss in speed comes from two problems: (1) updating the tree at
each step, and (2) the inability to pre-compute bit patterns for the
encoder. Is it possible to reduce the effects of either or both of
these?
- Would the speed be improved by limiting the frequency to 4181 as we
did for the static Huffman encoder? (HINT: what happens when we hit
4181?)
- For what kinds of input would Splay encoding do well? Will it ever
do better than adaptive Huffman?
-=!=-
This document is Copyright by Genie and Andy McFadden