So, Huffman coding is an optimal
prefix-free code. And can we have a better
data compression algorithm? and as you
might suspect the answer is yes. And
that's we're going to look at next it the
LZW algorithm, named after Abraham Lempel
and Jacob Ziv, and W is for Terry Welch
who got involved. and so the way that we
improve on Huffman coding is by changing
the rules under which it operates. And
we've already changed the rules once, so
let's take a high level view. so one idea
for codes is that we're going to, for all
text that we ever encounter, we're going
to use the same code or the same model of
the text. and so everybody's got that
model, we don't have to transmit it. but
the problem is that one text might have a
lot of As another one might have a lot of
Zs. They have different statistical
properties. so, it's not going to be
optimal for a given text. but still, over
the preponderance of text that we see this
can be effective. And so, that's really
what an ASCII is. but now, for Huffman,
well, we consider, we change that rule.
And we said, well, we're going to use
different encodings depending on what the
text is. so, we're going to look at the
text, figure out the frequencies and then,
go ahead and create a code that works for
that text. now, we have to transmit the
code. that's what the Huffman's code is.
for every text we've got a code that's
suited for that text. what we're going to
look at now is another change in the
rules, where it's called an adaptive
model, where we're going to just read the
text one character a time. but we're going
to use the text to update the model and
learn about the model as we read it. and
we're going to assume the decoder does the
same thing. And this gives perhaps it does
give more accurate modelling and better
compression over the, throughout the text.
And it's a very effective method, so let's
look at how it works. we'll just do this
through an example. now, this is, We're
going to use hex values. so, in LZW
encoding we start with our input, which is
which is characters. O r say, ASCII
characters. and what we're going to do is
keep a dictionary of code words. and the
code words are going to be fixed length.
and so, we'll use eight bits or two hex
characters as an output. And we'll start
out with just the ASCII value for all the
characters that we're going to use in the
message. so, that's the starting point.
so, at the beginning, so this is going to
be compression for this string here. at
the beginning we just pick off characters
and output their value from the from the
table. but every character that we read,
it gives us a little new information. For
example, in this case we've seen AB and
what we're going to do is say, okay, we've
seen AB, maybe that occurs again in the
text if it does we'll since, since we've
seen it, we know where it is, we know what
it is. we'll just give it the value 81 and
we'll maintain this table. If we see AB
again we'll use those eight bits. so we
put out the B, but we remember the fact
that we saw AB. And similarly, when we see
BR then that will be an 8-bit code word
that we can put out. and the idea is that
the decoder or the expander can do the
same thing. We don't actually have to
transmit this table. we can know that the
expander is going to do the same thing,
and we'll have the same a table. So now,
we see the R. So, this is BR. So then, and
that's going to be encoded with 82 but the
R is asking for R52 so we put that out.
now we see the A and so, that's going to
be 83. If we if we see it again and, but
the A is just 41 and then the AC is going
to be 84 the C is the 43. CA is going to
be 85 and then 41. and so, what we're
doing is building up a table that is a
model for what the string has and it will
allow us to get better compression as we
get layer into the message. so now, we're
reading the A after the B, so D is going
to be 87. but now, we see that the next
letter is B, we look in our table in for
AB and it's there. So, we can put out 81
instead of just putting that A out there.
So at this point when we look at the B we
can know that we had AB. And we can look
that up on the table and just put out 81.
and similarly we when we, but now, when we
look at the R our previous character was
AB. So now, we're going to code ABR with
88. and again, RA if we look that up in
the table and we can put out 83. and now,
we can remember RAB is going to be 89. so
now, what happens next? Now, we look at
our next characters. we look for the
longest prefix that we can match in the
table and that's going to be the code word
that we put out. So in this case, we have
BR that's in there that's 82. and the next
character is A so I'm going to put a BRA
in there. and now this is the remaining to
be encoded and we're going to look for the
longest prefix that we know the code for,
and in this case, it's going to be ABR,
which is 88. So the previous characters in
the text built a model that allow us to
more effectively encode the text. and
that's 88 ABR and then all that's left is
the last A. so, for this small example
the, compression is not great, but the
idea is still there's definitely some
savings in there, cuz these code words,
the input was 8-bit ASCII code words, and
these code words are, are also eight bits,
and the key thing is we don't have to
transmit the table, cuz we can assume that
the expander is going to rebuild the
table, the same way that we built it. so,
that's the basic idea beside behind LZW
compression. We also have a stop character
at the end that says, it's the end of the
message. So, this is the summary of LZW
compression. we created a symbol table
that associates fixed length code words
with string keys. We initialize it with
code words for single character keys. Now,
when it's time to encode part of the
input, we look for the longest string in
the symbol table that's a prefix of the
part of the input we haven't seen. and
that string, that's the longest one, its
the best we can do. we're going to have a
fixed length code word for that string.
And then, we look ahead to the next
character in the input and add a new entry
into the symbol table with tha t one extra
character. that's the LZW compression. so
one question that comes up is how do we
represent that code table in, in code. And
actually, the answer is really simple.
we're going to use a trie. because what a
trie can do for us is if you remember,
when you looked at the tries, if you don't
know, when we looked at tries, what we did
was support longer prefix match operation.
so, this trie represents all the prefixes
that we have seen so far in the message,
and it's very easy if the next four
characters in the text for ABRA, then we
have the code word for it. for anything
that we've seen in the text we've got a
code word for a fixed length code word.
So, as the trie gets bigger, as we move
down more into the trie, we get better
compression cuz we're using the same
length code word to compress more letters.
so here's the implementation of LZW
compression. again very simple
implementation for such a sophisticated
algorithm, really. and we're actually
going to use the TST so that we'll have to
worry about the extra space. and so, first
thing we do is initialize the TST with a
code word for each of the single
characters, so it's rated XR, so there are
different letters. and we'll just put an
entry into the trie for each one of the
letters along with its coding. and so we
didn't show, we only showed a few letters
in the examples, but in general, we'll,
we'll assign the code word i to each one
of the, to the ith letter. and then, the
rest of the trie is built from the input
string. And you know, so the very first
thing we do is find the longest prefix of
the input string in the symbol table. and
that longest prefix of method just marches
down the trie eating off the characters in
the input string one character at a time
until it gets to the bottom, because the
bottom it has a code word. so it, it
actually, the symbol table method actually
gives us back the string. and so, then we
can use that to get the value associated
with that string out in the symbol, in the
second call. And that gives us the code
word. an d then what we want to do is get
the length of that longest prefix match
and add one more character to it and add
which is the next character in the input.
and add that code word to the to the
symbol table. and then scan past that in
the input. so that's the entire
compression algorithm for LZW compression
using a trie. and so, what it's doing is
writing out a fixed-length code word and
chewing up the longest substring that
we've seen before. and then, at the end,
it writes out a stop close code word, and
closes out the input stream. so, using the
tech, trie technology that we've developed
we have a compact implementation of LZW
compression. now, let's look at the
expansion. And expansion is going to be
basically the same code. All that the
expansion algorithm get, gets is the list
of fixed length code words. and it's going
to maintain its own code word table in
order to get the expansion done. now, we
can start it out again by generating the
table for a each other single letter
that's going to be in the message or if
it's only a few may be. there is some
other sliding coding that needs to be done
at the beginning. but so, it seems 41 in
roles are switched. the fixed length code
words of the key and the values are
strings. So, we just look up the key and
write out the values as we see at 42,
that's a B we see. a 41, that's an A. but
not only do we want to put, put out the,
the character corresponding to the code
word. but we also want to build up code
words in the same way that the compression
method would have done it. So, the
compression method I want to see is an AB
would have associated the string AB with a
new key. And now, we read a 52. Look up
52, that's an R but we also put a new
entry in the table for the string BR. Same
way the compression algorithm would have
done. We see 41 we get an A. Now, we put
RA in the table 43 we put a C and we put a
C in the table 41, we put an A. we put CA
in the table now 81. we look up at our
table, and it's I'm sorry. the D is 44 and
AD in the table. And now 81, we look at
up, and we have AB and once we have seen
the AB then we know the compression were
to put DA on the table. And that's a
little bit tricky because the expansion is
kind of one step behind the compression.
It's got to put out the characters before
it knows it. And it does lead to a
slightly tricky situation that we'll talk
about. So now 83 is going to be RA. And
once we put out the RA, then we know that
compression would have done ABR now, so
now 82 is BR. And again, we know
compression would have put RAB in there.
and 88 is ABR and compression would have
put BRA in there. 41 is A and then 80 is
the stop character. Oh, and we would have
put and once it did the a, then it would
have put ABRA in there. And then, 80 is
the stop character. So, that's an
expansion just building the table in the
same way the compression would have and
then, using the table to figure out the
string associated with, with each fixed
length code word. so this is a summary of
expansion which is pretty much the same as
for compression except the reverse. so
we're going to create a symbol table that
has fixed linked keys and associates
string values with them. We put in the
single character values. we read a key, we
find the string value and write it out.
And then, we update the symbol table from
the last the two things that we, the first
character, the thing we just wrote out and
the thing we wrote out before that. and
again you know, to represent the, the code
table this time we can just use an array.
and because we, our keys are, are fixed
linked. And we assign them one, one bit at
a time. So, we can just store the strings
in an array. And use the, the key bits,
the key values, the fixed bits, key values
we get to index into the array and give us
the right string. so that part's easier.
so now there's a tricky case that really
everyone needs to work through this case a
few times to really understand what's
going on. And it's worth doing once even
in lecture. so, let's look at this case
where we have AB, AB, ABA and just follow
through th e algorithm for this for this
case. so we get an A, and we look it up,
and it's 41. and so, that's what we're
going to put out. and then, we look at the
next character. And it's AB so we're going
to remember 81 in our code word table.
then, we read a B. and we look it up, and
it's 42. and the next character is A. So,
we're going to say, well, BA is going to
be, be 82. then next character is B. We
look up AB and we have 81. and so, we can
put out the 81. And now, the next, look
ahead, the next character is A. So, we're
going to do a code for ABA. That's going
to be 83. now, we have the rest of our
string to be encoded is ABA and our
longest prefix match is ABA. so, we're
going to put out 83. and that's the end of
the string. so, we do the 80, which is the
end of the string. So, that's compression
for that string, working the same way as
for the other example. now, lets look at
expansion for this case. they start up the
same way. so now, we see a 41 and we look
it up in our table. and again, this can be
just an indexed array. so it's going to be
a so that's a starting point and now, 42
is going to be a B and then we look back,
we just put out an A and a B so our
compression algorithm would have encoded
an AB as 81, we know that. So now, we can
when we see 81 we've got AB so we can put
a B. and so now, we look at the and we put
out the AD and the next entry in our table
is going to be BA, because that's what our
compression were to put out. but now, we
just got a problem. the next character
that we see that we need to expand is 83
but we need to know what key has value 83
but it's not in the symbol table yet. so
that's definitely a tricky case for the
now it is possible to when we go through
that one again. so I, at the time that we,
we read the 83, we need to know which key
has value 83 before it gets into the
symbol table. in all of its first
characters is going to be A, so that means
that ABA has convenience with the code. In
a book which you can examine has a way to
test for this case, and it's definitely a
tr icky case that at least can be
considered for LZW expansion. we expand 83
at the same time that we put it in the
symbol table, in this example. okay. So
there are all different kinds of details
for LZW, we've just given one sometimes
people find it effective to clear out the
symbol table after a while v maybe how big
do we make this symbol table, how big do
we let it get. maybe it's not worthwhile
to keep older parts of the message. It
should adapt the pieces of the message.
there's many other variations like that,
that have been developed. so, so, for
example, what GIF does, is when the symbol
table is full, we just throw it away and
start over. Unix compress it's throws the
keeps a measure of how well it's doing.
And throws it away when it's not being
effective. and there's many, many other
variations. why not put even longer
substrings? Why just one character at a
time? Why not the double ones and so
forth. And there have been many variations
like that have been develop, developed.
and actually in the real world the, the
development of this tech, technology was
influenced by patent law. There's a
version called LZ77 and another version
called LZW because these guys worked for a
company in the summer and then it was
patented for a while you couldn't use LZW
unless you paid the patent holder. But
that expired in 2003 and then things
started to go up again. so there's lots
and lots of different effective methods
that are variants of LZW. and really to do
a good job you might also, you need to
include Huffman coding for the characters
or run-length encoding and in really just
combinations of these basic, basic methods
that we talked about that are, are most
effective. so you see this technology
author up computational infrastructure
that you use everyday. and, and at the
time we were talking about tries, they
seemed a bit abstract, but actually they
are, tries are definitely part of the
algorithmic infrastructure and they are
really fine example of a clear, clean,
elegent data structure and algorithmic
idea of be ing used to great effect in the
real world. and this is there's people,
plenty of people still doing that
research. Even on lossless data
compression there's still ideas being
developed. and these are the kind that
does a famous benchmark of set of texts
that if you think you have a good new
compression algorithm you can run it on
this benchmark. where it's asking you is a
seven bits per character, it's eight bit
but one of the bits is redundant, so you
will immediately get down to seven. these
are the kinds of compression ratios that
people have achieved with various mostly
levels of variance down to less than half
of what you can get with asking. but it
continues to drive down and there was a
completely new method called the
Burrows-Wheeler method developed in the
90s' that took a, a big jump down and
there's a few more that have continued to
improve even through the 90s'. So there's
still room for improvement in lossless
data compression, but it's a really fine
example of the power of good algorithmic
technology. so here's our quick summary on
data compression. so, we considered two
classic fundamental algorithm. The first
one, Huffman encoding, represents fixed
length symbols with variable length codes.
so the prefix code uses, tries to use
smaller number of bits for the most
frequently used symbols. the other way
the, the LempelZiv method takes variable
length symbols and uses fixed length code.
So, it's interesting to think about those
two ends of the spectrum. there's plenty
of compression algorithms out there that
don't try to get an exact compression, but
just try to get an approximation using FFT
and wavelets and many other mathematical
techniques. And that's appropriate for
things like pictures and movies where
maybe you can miss a few bits. But
lossless compression is still a very
important when you download an application
which is machine code onto your computer.
you can't afford to have one of the bits
be wrong. so that's why lossless
compression will always be with us.
there's a theory on compress ion.
This theoretical limits that is, is a
measure of the and it's called the
entropy, Shannon entropy of a text that
says a, a very fundamental way to indicate
how much information there is in a text as
a function of its frequency. So, it's a
sum of overall characters of the product
of the frequency. The log and the
frequency with these methods we can get
very close to the entropy in some
theoretical session settings. but actually
in, in practice the most effective methods
uses tricks and techniques that have extra
knowledge about the data being compressed
to really get the most effective kind of
results. as I explained, if you're doing a
page like this, you better use a method
that does really well on huge amounts of
wide space for example. that's LZW
compression and our last compression
algorithm.