The primary topics in this part of the specialization are: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees).
Problem Definition
Loading...
Del curso dictado por Stanford University
Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming
684 calificaciones
De la lección
Week 3
Huffman codes; introduction to dynamic programming.
Conoce a los instructores
Tim RoughgardenProfessor
Computer Science
So we clearly have something to be excited about.
There's clearly this opportunity to design binary prefix-free codes which
improve over the obvious fixed link solution.
So, we'd like to have in some sense, optimal algorithm for this problem and
for that, we of course need a crisp problem definition.
So, to do that it turns out to be useful to think of codes as binary trees.
So, this video will develop that connection concluding with the final
formal problem statement. So, the last video introduced us to this
very interesting computational problem, namely given characters from an alphabet
with frequencies, find the best binary prefix-free encoding,
find the code which minimizes the average number of bits needed to encode a
character. Crucial, the reasoning about this problem
is thinking of binary codes as binary trees. So to give you an idea about this
correspondence, let's just revisit three of the binary codes we saw in the
previous video and see what kind of trees they correspond to.
So let's just continue with the four symbol alphabet A B C D.
The obvious fixed length code where we encode A, B, C, D was 0, 0, 0, 1, 1, 0
and 1, 1 is just going to correspond to the complete binary tree with four
leaves. So let me label this complete binary tree
as follows. I'm going to label the leaves A through D from left to right, and I'm
going to label each edge of the tree with a 0 if it corresponds to a left-child
relationship and with a 1 if it corresponds to a right-child
relationship. And now what you see is there's a
correspondence between the bits along root to leaf paths and the fixed length
encoding. So for example for the symbol C, if we
follow the path from the root to the leaf labeled C, we first encounter a 1 because
it's a right-child, then we encounter a 0 because it's a left-child.
That gives us a 1 and a 0, that's the same as our encoding of the
symbol C in this fixed length encoding and the same of course is true for the
other three leaves. Next, when we first started playing
around with variable-length encodings to motivate the prefix-free property, we
studied a code where we replaced the double 0 for an A with a single 0 and the
double 1 for a D with a single 1. Now this code was not prefix-free,
but we can still represent it as a binary tree.
It's just not going to be a complete one. So I'm going to label the edges of this
tree the same way as before. Left-child edges will be given a label of
0, right-child edges will be given a label
of 1. I'm going to label the left and right
children of the root A and D respectively and the two leaves will be given the
labels B and C. The reason I labeled the nodes in this
way is, because then we have the same kind of correspondence between the
encodings that we proposed for the various symbols and the bits that you see
along a path from the root to nodes with those symbols.
So for example, if you at the node labeled D, the path from the root only
has a single bit 1 and that coincides with the proposed encoding of the symbol
D. Now, remember, this code is not
prefix-free and so therefore, as we saw, it had ambiguity.
So if you're wondering what some encoded message means and you see a 0, you're not
sure that 0 might be representing the symbol A or alternatively it might be the
first half of an encoding of the symbol B.
So, this ambiguity is also noticeable in the tree.
And the property in the tree that tips you off to the ambiguity is that there
are symbols at internal nodes of the tree.
The symbols are not merely at the leaves as they were with the first tree with the
fixed length in coding, but there are also two internal nodes
that have symbols. So let's draw the tree for our final
example which, was the variable length but prefix-free code that we looked at in
the previous video. So this is going to correspond to a tree
which is not perfectly balanced, but it will have labels only at the leaves of
the tree. So, if you label the edges of this tree
the way we've been doing, all the left-child edges get a 0, all the
right-left edges get a 1, and we label the leaves of the tree from
A to D going from left to right. You'll see we have the same
correspondence as in the previous two trees.
the sequence of bits from the root to a leaf coincide with the proposed encoding
for it. So, for example, if you look at the leaf
labeled C, because you traverse a right-child, another right-child and a
left-child to get to it, that's the sequence 1, 1, 0 and that is precisely
the proposed encoding for the symbol C. So in general, any binary code can be
expressed as a tree in this way, with the left-child pointers being labeled with
0's, the right child pointers being labeled with 1's,
and the various nodes being labeled the symbols of the given alphabets, and the
bits from the root down to the node labeled with the given symbol
corresponding to the proposed encoding for that symbol.
And what's cool about thinking about codes as trees is that the really
important prefix-free condition, which seems like a nuisance to check in the
abstract, shows up in a really clean way in these trees,
namely the prefix-free condition is the same as leaves being the only nodes that
have labels. No internal nodes are allowed to have a
label in a prefix-free code. The reason for this is that we've set it
up so that the encodings correspond to the bits along paths from the root to the
labeled node. So being a prefix of another corresponds
to one node being an ancestor of the other, and so, if all the labels are at
the leaves, then of course nobody is an ancestor of the other and we have no
prefixes. The other things that's really cool about
this tree representation of codes is, it becomes pictorially obvious how you do
the coding given this sequence of 0's and 1's from a prefix-free binary code,
namely, you start at the beginning and you start at the root of your tree,
whenever you see a 0 you go left, whenever you see a 1 you go right.
At some point you'll hit a leaf, that leaf will have some label and that's the
symbol that's being encoded, and after you hit a leaf, you just start all over
again back to the root. So for example, if you were using our
variable-length prefix-free code for the four letter alphabet, as in our running
example, and you were given the sequence of 0s and
1s, 0, 1, 1, 0, 1, 1, 1. What would you do?
Well, you'd start at the root and you see a 0, so you follow the left-child
pointer, and you immediately get to a leaf.
It's labeled A, so you're going to output and A as the first symbol.
Now you start all over. You return to the root, now what do you see?
You see a 1, so you go right, you see another one, so you go right, and now you
see a 0, so you go left and that gets you to the leaf labeled C.
Now you start all over again. You see a 1, you go right, you see a 1,
you go right again, and then, finally you see yet one more 1 and you wind up at the
lead labelled D. So by repeated traversals through the
tree, you decode the sequence of 0s and 1s as a C, D.
There's never any ambiguity, because when you hit a label, you know you're going to
leave, there's no where to go. And every internal note, it's unlabeled,
you know to expect another bit, another traversal further down in the tree.
So a final important point about this correspondence is that the encoding
lengths of the symbols, the number of bits needed to encode the various
symbols, are just the depths of the corresponding leaves in the tree that
corresponds to the code. So for example, in our running example
the symbol A is the only one that needs only one bit to encode and it's also the
only leaf in level one of the tree. And similarly B needs two bits and shows
up in the next level, the C and the D which need three bits
show up in the third level. So this correspondence is, really just by
construction, so how do you encode a given symbol.
Well, it's just the bits on the path from the root, and that the number of such
bits is just the number of pointer traversals you need to get from the root
down to that leaf, and that's just the depth of that leaf in the tree.
So we're now in a great position to really have a crisp definition of the
problem. The input of course is just the
frequencies for a bunch different symbols i from some alphabet capital sigma.
I'm going to use P sub i as notation for the frequency of symbol i.
So we know what it is we want to optimize.
We want to minimize the expected number of bits needed to encode a symbol, where
the average of the expectation is taken over the provided frequencies of the
various symbols. Well, let's express this objective
function using our newfound correspondence with binary trees.
In particular, the fact that we can think about encoding lengths as depths of
leaves in trees. So, given a tree, T, which corresponds to
a prefix-free binary code. That is it should be a binary tree and
the leaves of this tree should be in one-to-one correspondence with the
symbols of sigma. We're going to define capital L(T) as the
average encoding length. It's an average in the sense that we sum
over all of the symbols of the alphabet, we weight each symbol by the frequency,
and remember, this is part of the input, so whether the provided frequency P
survived that symbol i. And then how many bits do we need to
encode that symbol i? Well, it's just the depth of the leaf
which is labelled i in the given tree, capital T.
So this is what we want to make as small as possible.
So, for instance, using the data from the previous video, the letters A, B, C, D
with frequencies 60, 25, 10, and 5%. Then if we use the complete binary tree,
that is the fixed length encoding, we just get two bits per character.
While if we use the lopsided tree optimized, so that each A only takes one
bit while suffering three bits for C and D, then the average encoding length drops
to 1.55, as we saw in the last video. So what then is the goal,
what's the responsibility of our algorithm?
Well, amongst all binary trees, which have leaves and correspondence to the
symbols of sigma, we want to compute the one which makes this average encoding
length as small as possible which minimizes our objective function capital
L. Turns out Huffman's greedy algorithm does
it. More details to come.
[SOUND]
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2019 Coursera Inc. Todos los derechos reservados.
