Next, we'll look at Huffman encoding. this
is a classic algorithm that is still
widely-used and effectively used today.
it's definitely on the list of algorithms
that everyone should know cuz it's quite
ingenious. so we start out with the idea
of variable length codes. so far, we've
talked about codes where every character
is represented with the same number of
bits. But there's no reason to do that.
For example, look at Morse code. the idea
in a way that we assign dots and dashes to
letters is that frequently, you'll use
letters should have smaller number of
characters. so for example, an E is only
one dot and so forth. And letters that are
used less frequently, like Q are going to
be longer. More dashes and more
characters. So with this we can, it's an
idea, a compression idea, of let's use
fewer characters for frequent fewer bits
or fewer code characters for frequently
used characters. now, there's an issue
with this and that is that it can be
ambiguous. So, this message everybody
knows, looks like SOS, three dots followed
by three dashes, followed by three dots.
but actually it could be it's any one of
these others. Like V is dot, dot, dot,
dash. Thats good. and then, seven is dash,
dash, dot, dot, dot, so it could be V7. Or
it could be either of these two. There's
lots of different things that this thing
could be. So, Morse code is actually, it's
not just dots and dashes it actually has
they have a little space between the code
words to avoid this problem that there's
an ambiguity caused by the fact that one
code word can be prefix of another and
there's no way to tell that it's not
without separating the code words. so now
that's the way it's solved in Morse code
and that's not necessarily the most
efficient way to solve it, and that's what
Huffman codes addresses. Also, a problem
with Morse code is don't be trying to
transmit a lot of numbers with Morse code,
because the codes for those are pretty
long and, and you'll have much longer
representations for codes that involve a
lot of messages and involve a lot of
numbers. But there's a really elegant way
to avoid ambiguity. And that is to just
adopt a rule that no code word is going to
be a prefix of another one. so fixed
length codes do that. If every code is the
same number of bits and every character
encode different bits, then no code word's
a prefix of another. They're just all
different. another thing you can do is
have a, a special stop character like,
like the space in Morse Code to end to
each code word. That's really what it's
doing. so the code words are all
different. And they end with a character
that's special. And so, none can be a
prefix of another one. but there's also
just an easy way to just make sure that
you use a code that has this prefix free
property. so, for example, this code here
no code word is a prefix of another. And
it means when you have bits there's a
unique way to decode. So here, the
compressed bitstream starts with zero, the
only way that can happen is if the first
letter is A. Then, when you're done with
the A you've got four ones and that means
it's got to be a B. and then, you get rid
of the B, and so forth. And it's three
ones and a zero, it's got to be an R, and
so forth. Since no code word is a prefix
of another you can just read off the code
from the bit string without having any
special stop character or any efficiency,
inefficiency caused by that. all we have
is the bits and we are able to uniquely
decode it. And there is numerous
prefix-free codes. For example here's
another prefix-free code that for the same
five characters and it actually uses fewer
bits. So, the idea of Huffman encoding
within these rules where we must have a
prefix-free, free code. And we've got a
particular message. what's amazing about
Huffman encoding is, that it finds the
code that uses the fewest bits for that
message. and that's why, you know, it's so
effective. So the interesting thing one
interesting thing about prefix-free code
is that they're really easy to represent
with trie. and, and the idea is very
simple. We put characters in the leaves
and we imagine that every, this is binary
trie, so we imagine that there's only two
links per node. And we imagine that every
left link is labeled zero and every right
link is labeled one. and then, just
following the path from the root to a
leaf, so say we go right, so it's one,
zero, zero, that's D. Those bits are not
stored in the trie, we just keep, we just
implicitly keep track of them. if we go
left we keep zero, if we go right we keep
one. And so a try for prefix-free code
uniquely determines the code. and that
means that just working with the trie we
can decompress a bit string just by
starting at the root, reading the bits
take them where they take us, and when we
get to a leaf, we've got a character. so
that's the trie corresponding to that
code, that's the trie corresponding to
that code. this one starts out with one,
one, so starting at the root, we go one,
one, and the first letter is A. And then,
the next letters are zero, zero, and so we
go zero, zero, and we come to B, and so
forth. a simple representation of a
prefix-free code that is that makes for
easy decoding, given the bit, bit string
in the trie, it's pretty easy to decode.
you could also keep a symbol table of
pairs but sorry, for compression, how do
we do compression that was in expansion?
so, for compression, we can just keep the
table and use it. you could also use the
trie to figure out the code by following
the path h, up to the root. and for
expansion, as I just said, you start out
at the root I go left at zero, right of
one and it's very easy. so for among comp,
expansion, so we will look at the code for
both of these. The question is how to
construct, the first question is how to
construct the trie. so let's start with
the data type. so this is similar to other
tree structures that we've built before
where we have a character that we don't
use for internal nodes, just for leaves.
we've got the frequency that we use while
we're building the tribe, not when we're
expanding and then every node has a left
and a right. and th is, is the
constructor, you just fill in all the
fields. we need a method to tells us if
the current node is a leaf. And that's
when so that's if both its links are null.
and we need to compare it to, to compare
nodes by frequency. And we'll see why
that's needed later on. so that's the data
type for the nodes that we're going to use
to build the tries. and so now, let's look
at expansion. So, this is in code what I
just talked about. so, we're going to have
a method that reads in some of the bit
string, and converts it to a trie. Now,
that's one clever part of the algorithm.
and then the first thing is the number of
characters in the code in the message, you
know, we also get that. So, we get the
trie, and then, we get the number of
characters. and then we simply for do a
for loop for the number of characters and
start at the root. if we're not at a leaf
we read a bit. And if it's zero, we go
left, and if it's one, we go right. and
that's it. if as soon as we get to a leaf,
we just write out the character that we
get and then, go back to the root and keep
going. We're not in a leaf if we read a
bit, we have zero, go to the left, one, go
to the right. And when we get to a leaf,
we write out the character extremely
compact code for expanding. given a bit
string, the first thing is to trie. We
have to talk about how to get the trie in
from a bit string number of characters.
and then, the simple loop that expands
according to the trie representation. so
that's networks for any prefix-free code,
not just the Cuffman, Huffman code. in the
running your time, it's obviously linear
in the number of bits cuz for it's just a
loop that chews up a bit every time in the
loop. Okay. So, so again, for any
prefix-free, free code, how are we
actually going to write the trie? well
it's a little, little clever but by this
time, you should be ready for this kind of
algorithm. what you can do is traverse the
trie in pre-order and when you and then
come to an internal node you write a zero.
when you come to a leaf, you write a one f
ollowed by the 8-bit character at that
leaf. so it's a simple pre-order
traversal. if this is a recursive program
to write out in trie if you're at a leaf,
you write a one followed by the 8-bit
characters at the leaf and you're done.
and if you're not at the leaf, you simply
write a zero. and then recursively, do the
two sub-tries. and that gives a unique
representation of the trie that can be
used to construct the trie from that bit
string. so and the idea is that typically,
we're talking about a, a very long message
the trie itself is just basically
encodings of all the possible characters
in a message. and that's going to tend to
be small compared to the length of the
message. so for say, a genomic sequence
there would be only four characters and
the ones that used most frequently,
hopefully would be encoded with not that
many bits. of course, but anyways, the
size of the trie itself is going to be
much smaller than the length of the
message. so reading in the trie and this
requires a little bit of thought, but and
we see the code, the code is extremely
simple. We justreconstructed from the
pre-order traversal to trie. So, this is
the readTrie method that we needed, that
reads the bits from binary standard in and
produces the trie, and it's also
recursive. and if the bit that you read is
zero that sorry, if the bit that you read
is one that means you have to create a
leaf otherwise, you recursively read the
left and read the right. and make a new
node that has a subtree that, that denotes
to the left and the right. And it doesn't
it doesn't use the character in the second
one, the frequency we initialize to zero.
so, in internal nodes, we don't use the
character. So if you look at what would
this code do for this bit string so the
first bit is zero. so it's going to
recursively call itself to read the trie
on the left. and so, the next bit is a
one. so, it's going to read the next eight
bits to get the A. And it's going to
return a new node with that character in
it that's a leaf. so, that's going to be
the left subtree of the initial trie, the
first recursive call. and then, it'll read
the right subtree, which is an internal
node, another internal node. It takes a
little thinking to convince yourself this,
this works. but it does. And it's very
compact and easy code. And again, works
for an prefix code. you encode the trie
with the prefix traversal. And with a very
small amount of code, you can reconstruct
the trie and transmit a bitstream. And so,
this is a compression of a trie structure.
so now, the question is, how do we,
there's a lot of prefix pre-codes, how we
will find the best one? well, and there's
an idea called the Shannon-Fano Algorithm
which says the, the, the key idea is that
you've got characters that appear with
different frequency. And you want to get
the ones that appear very frequent to use
fewer bits. and so, it's of interest to
find the ones that are very frequent, and
so the Shannon-Fano algorithm says, just
divide all the symbols in, into two
roughly equal frequency and start the ones
in the first one with zero and the ones in
the second one with one, it's kind of a
balanced code. and then, and then kind of
re, recur. so if you have A appearing five
times, and you C appearing one time at six
for those and then you get six for all of
those. And then you try to encode those
with and try to use zeroes for roughly
half the character. And one for roughly
half the character. so in order to deal
with that, you have to figure out how to
divide up the symbols. And you can imagine
an algorithm for doing that. but the real
problem with this method is that it's not
optimal. and so that's the kind of
situation that Huffman was faced with way
back when coming up with the algorithm.
and the best way to explain the Huffman
algorithm is through a demo. And so,
that's what we'll do next. So, here's a, a
demo of the Huffman algorithm. So, the
first thing that we do is count the
frequency of each character in the input.
and so that's what the algorithm is based
on. So, in this case, there's five As, two
Bs, o ne C, one D, and so forth. So our
goal is to use fewer bits to encode A and
more bits to encode C, D, and exclamation
point ,!,, for example and we want to
prefix-free code. so it's kind of a bottom
up method. So what we do is we build one
node for each character and we keep in the
node corresponding to each character, a
weight that's equal to the frequency. and
then we imagine keeping them in a sorted
order. so that's how the method starts
out. Now remember, our node representation
had an instance variable that allowed for
storing these frequencies. And then the
idea is to given these are sub-tries of
size one, the idea is to combine two of
them and merge them into a single tribe
with a cumulative weight. And so we're
going to find the ones that are, the two
that have the smallest weight and create a
new internal node for them. And the weight
of that node is going to be the sum of the
two weights. So, that's the frequency of
all the code characters below it. and
then, just put that into the mix. so now
we have five sub-tries to deal with and
that's the algorithm. Select the two tries
with minimum weight. in this case, it's,
since we're keeping them sorted so it's
going to be the ones on the left. combine
them and add their two weights. So, make a
parent node. It doesn't matter which goes
in left which goes right, really. and
then, add the weights to the frequency of
the parent node and then put it into the
list. Now, if you look up at the table at
the right what we're doing when we're
doing this combination is building up the
code corresponding to the characters
moving from left to right. So, so far, we
know that the code for D is going to end
in zero and the code for C is going to end
in one, one. and so for exclamation is
going to end in one zero. so that now
continue the rule. Now the B and R are get
combined. And again we're figuring out how
those code words end. and so now, we have
just three to choose from. Now, we're
going to combine the two big ones and now,
we have new prefix bits for all of them.
and notice that our letter that appear
with highest frequency gets added in late,
which means, it's going to be nearer the
root. so now, we have just the two and we
finish the algorithm. there's only two
left now, so we combine them. I merge into
a single try. And that corresponds to
prepending a one to the codes for all the
other letters and just having a one bit
code for A. And that now winds up with a
single try. that's a demo of Huffman's
algorithm in operation. So, the Huffman
Code is an answer to the question of how
to find the best prefix code that's really
very simple to describe. Count a frequency
for each character in the input. And you
start with one node corresponding to each
character with weight given by its
frequency. And just, until you have a
single trie, you select the two with the
minimum weight and merge them into a
single trie by creating a new node with a
weight sequel or the sum of the
frequencies. this algorithm is used in
many different and familiar compression
applications from PDFs to GZIP to MP3s to
JPEG. and it's pretty simple to code up in
Java given the tools that algorithmic
tools that we've built up. so what we're
going to do is this is the F of the
frequencies have been computed. And we're
going to build a try given the
frequencies. and we're going to use a
priority Q in our generic priority Q, we
might as well put nodes on it. we
implemented a compare-to method. all we
need is the compare-to to be able to build
a priority Q from data of that type. So,
we have a priority Q of nodes and for all
the possible character values, if they,
and if they appear in the message, they
have a nonzero frequency we'll just put in
a new node with the given frequency that's
a leaf onto the priority Q. And then the
Huffman algorithm is just as long as
there's more than one node in the priority
Q. we pull off the smallest two nodes, we
create a new node, that's apparent. it's
character value is not used. we compute
the total frequency, the sum of the two
children and we make those children of
that nod e, and then we put that back onto
the priority Q. And that's it. Take two
off, put one on. it reduces in size by
one. So, this while loop is eventually
going to terminate. when it's done,
there's only one node on the priority Q
and that's the root of the trie. extremely
simple implementation of Huffman's
algorithm using our generic priority Q.
you can also implement it by presorting
the of the nodes as well. but this is a
particularly nice way to do it. now you do
have to prove that it produces an optimal
code. That's in the sense that no code
produces, produce, uses fewer bits. and
that proof is in the book. it's, it's not
terribly difficult but we're not going to
do it in the lecture. the, and that's,
Huffman proved that it in the 1950s. So,
there's no point looking for a better
prefix-free code. and prefix-free codes
are so convenient cuz you don't need to
worry about the ambiguity it's a fine
method that's pretty easy to do. So now
what we have to do, one disadvantage of
Huffman and some other methods don't have
is, we have to have two passes through the
data. we have to go through and read all
the character frequencies and then build
the trie and then we have to go back
through the data and encode the file,
either traversing the trie from bottom up
or using just a symbol table for to look
up the code for each symbol in the
message. and the running time is pretty
clear from the use of the trie, the trie,
the number of characters in the number of
nodes in the trie is just the alphabet
size. and so it's going to be alphabet
size log R because there's trie operation
that might involve depth of log for using
heap implementation. and then you have to
be the for each character, you have to do
some kind of lookup to encode. and
actually a question is, can we do better
in terms of running time? and well, stay
tuned, we'll look at a different method.
That's Huffman compression.