So the analysis of trie parameters is one
of the most challenging in, in the
analysis of, of algorithms and quite
interesting to contemplate.
So that's what we're going to look at
next.
So again, it's the basis of understanding
performance in lots of large scale and
important applications that are part of
our infrastructure right now.
So one of the big questions is how much
space does a trie take?
Also, numbers of total numbers of external
nodes.
And then, if you have the number of
strings you're representing, then you
figure out the number of extra nodes, the
number of void nodes, that's really the
extra space that, that you're using.
What about the expected search cost?
Well, like with BSTs , that's the external
path length.
That's the distance from the root to all
the external nodes average distance.
So external path length, average external
path length of this trial is 3.92.
That's the search cost.
Now, you notice that even if half your
nodes are void, that's only going to add
half to this extra cost, so that's part of
the reason that our tries are effective.
You can have plenty of void nodes, it's
not going to effect the search cost all
that much.
And then, in a leader election, that's the
length of the rightmost path as I talked
about before.
It turns out we can analyze all of these.
I'm going to talk about external path link
and the others will be exercises.
And again, the easiest model, the usual
model is to think of the trie as built
from inserting n infinite random bit
string.
Eventually, they're going to differ and
that's where the differ, that's where
you're going to get a nonvoid node, node,
that might represent an infinite tail, but
we don't care.
The bit strings distinguish themselves,
eventually the trie represents them,
according to distinguishing them on the
leading bits.
And from an analysis standpoint it's makes
for a reasonable model. because, we can
assume that every time, every node that
will randomly go to the left or to the
right and this model fits real data
perfectly well when it's been studied.
So the starting point if you think back to
the analysis that we did for binary
research trees, it's very similar.
It's just that so that is we have a trie
of size n.
There, there's k on the left and n minus k
on the right for some value of k.
The difference is that two differences.
One is what's the probability that there's
k nodes on the left which in the case of
binary search trees was just 1 over n.
And the other difference is that you might
have no nodes on the left and n nodes on
the right.
So that's a technical thing.
That definitely comes directly from the
definition of drive, but it makes the
recurrence just a bit, tiny bit trickier.
So that's a recurrence down at the bottom.
What's the probability that, that when
you've end strings, end random strings,
what's the probability that the k will
start with a 0 bit.
This is just 1 over 2 to the n times n
choose k.
So and the external path length of a trie
if, if you look at the root, that adds N
to the external path length because
there's n nodes down below it.
And then 1 over 2 to the n so it's the
probability that there's k on the left,
which is n choose k to 2 to the n.
And then, its external path length c sub
k, external path length n minus k, with
the appropriate starting conditions.
Again, it's just a little tricky to
realize that there's a cn on the
right-hand side when k equals 0.
So for BST, the probability that the k on
the left is 1 over n.
We looked at random Catalan trees where
that's probabilities as a Catalan number
and we have the Catalan distribution.
And for tries it's a binomial
distribution, so, that's the recurrence
and we can use that to calculate small
values, or the distribution.
But that's the one that we want to solve.
And again, just by correspondence to the
distributions that we looked at for random
cattle entries.
And for binary search trees for binary
search trees, the distribution is totally
flat are equally likely for any node to be
at the root.
For cattle entries remember we found that
there were very likely to have one side or
the other to only have a small number of
nodes.
And so the distribution was very skewed
and very skinny trees.
For AVL trees, we're trying to make them
more balanced, and the distribution shows
this amazing pattern that we haven't
characterized analytically.
And for tries, the probability that the
root's K is binomial, and that's really a
characteristic that we're looking for
that's going to tell us that these things
are going to be pretty well balanced.
Because it tends to n over 2 is the most
likely thing.
And within the square root if n over 2 is
where the divisions are mostly going to
be, which means its going to be pretty
well balanced.
But let's look at that analytically.
Now I'm not going to cover every detail in
great detail, but I think you'll see how
we go from one step to the other and you
can check details.
Offline.
So this is the basic recurrence.
We're going to use exponential generating
function for this.
And the reason is the N, N choose k allows
to if you divide by this equation by N
factorial, then you have C of N over N
factorial on the left.
Then some net of [inaudible] you get c of
z using the x the exponential generating
function.
And then the n [inaudible] a part of it
is, is a convolution of c k over k
factorial and 1 over k factorial.
In without very much calculation at all,
you can verify this formula, c of z
equals.
This is by dividing by n factorial,
summing, multiplying by z to the n, then
summing both sides.
Pretty quickly comes down to this formula.
And you can also actually get this
directly through the symbolic method with
an appropriate operation having to do with
the way trans defied So very simple
formula on the generating function.
It's a convolution of E to the Z over 2
and C to Z over 2.
That's the generating function equation.
Now, it's not, can't be characterised as
the simplest of generating function
equations that we're going to be able to
solve explicitly.
Because we have Z over 2 in the argument.
But one way to, deal with it is just to
iterate.
So if we apply the same equation for c of
z over 2, just plug in the same equation.
Then the z, e to the z becomes z over 2
minus z, because minus z over 2 and then 2
0 4 c to the z over 4 can iterate.
And then we the argument gets smaller and
smaller and simplify.
So, that's just selecting terms.
We still have an equation that we can
iterate.
In another step you can see the pattern is
that, what we are going to wind up with is
Z times E to the Z.
In every case, and then we have the
declining Z over 2, C3, 3Z over 4, 7Z over
8, and so forth.
So we get a sum of terms in the form Z
times E to the Z minus.
E to the half, E and three quarters, E
seven eighth C, and so forth.
So it's not, you have to prove that this
thing goes away as you go to infinity.
But anyway that's the iteration that we
get, an explicit formula for the
generating function for the average
external path link, because it's the
average external path link in a trie.
Okay, so we're looking for the coefficient
of Z to the N in that.
So well, in factorial times Z to the N in
that.
And if you go ahead and expand the, the E
to the Z multiplied by a factorial and get
the coefficient of Z to the N.
Then we have this difference one minus one
minus one over two to the J to the N minus
one, so I'm on J.
Again, that's a fairly simple formula,
explicit formula for the average external
path length in a trie.
It still does have the infinite sum and
we're going to have to work with a little
bit.
I'm working through this with elementary
analysis just to make sure that people see
ah[COUGH] The, what underlies this
solution, and because we get to a kind of
surprising result.
And it's good to see what, what's
underlying, what the structure is.
And so that's what we're going to do.
To characterize this fully, analytically,
requires complex analytic methods that
we'll talk about.
About in part two of the course.
So what we're going to see is on the next
slide we're going to use the [unknown] x
log approximation.
This, this thing becomes like 1 over 1
minus e to the minus n over 2 j.
And that's not a difficult calculation
using X blog.
And in the next slide, we'll show that
that's pretty close to N log based two of
N.
So that's the external path link in a
trie.
So, this step is, is not difficult.
I didn't mean to skip through it so
quickly.
But it's not difficult at all to show that
with X blog.
But now what I'm interested in is looking
at this, sum on J greater than 0, 1 minus
even minus N over 2 to the J.
How we're going to characterize that, and
that's a really interesting function to
take a look at.
What I'm going to try to do with this
analysis is try to isolate the, the
periodic terms that there's an oscillation
in here and I want to try to isolate the
part that, that.
Oscillates.
And so the way that's going to happen is
we're going to take the function log base
two events and we;re going to work the
integer part of log base 2 event.
And then the fluctuation is Every time you
come to an integer is you go from one
integer to the next There's fluctuation in
the, in the function as you're working the
real function log X, but you're only
picking off the integer parts of it
unless.
So let;see how it works.
So all we're going to do is take that
infinite sum, and we're going to break it
into two parts.
The part where j is less than floor of log
n, and the part where it's greater than or
greater or equal to the floor of log n So
that's just split the sum into two parts
at that one point.
And the key thing to notice about this is,
when j bigger then log base 2 of n.
Then 2 to the J,uh, is, going to be bigger
than N.
And so, we're going to have,uh, minus N
over something huge.
We're going to get a number very close to
1.
It's going to go away.
So and it's, when it's, j is small like
say j is 2 or something we have e to the
minus 10 which is tiny, the sum is just 1.
So basically we're going to have log in
terms they are very close to 1 and all the
rest of them are going to very close to 0.
We've just a little bit left in the
center.
So lets look at how that goes.
So, in this case we just split off the,
the log n.
So we get floor of log n and then we have
the second [inaudible] e to the minus n
over 2 to the j.
And that's just putting the first sum into
two parts.
So, and then this one is the same so no
change there so now what we are going to
do is let this j go is for negative as at
once doesn't matter because if that j goes
for negative this thing is exponentially
small.
So, it doesn't matter.
And we're off by an exponentially small
amount, so...and that's going to allow us
to combine the two sums in that part.
So, now this is not Change j to, j plus
log n in this sum, and, same way i changed
j to j minus log n, in that sum.
And so now we have some floor to the log
n's, coming in, in to these sums.
But then, there's n over floor to the log
n.
Well that's like taking the function log N
and tracking off the integer part.
All that's left is the fractional part.
So the end sum of this thing is.
What's floor of log n?
That's the integer, biggest integer less
than log n.
That's the function log n minus floor of
log n.
As n increases, this function fractional
part of log n goes from 0 to 1 and back
again.
So it's a fractional part of log n.
It's an oscillating function.
And then but these other functions also
are just functions of the fractional part
of login.
Again, again, I skipped through just a
lil, a tiny bit of subtracting login from
floor login, but you'll see that, that
works out.
So now I have these three parts that are
all functions of the fractional part of
login, that is the oscillate.
So this is my external path length over n,
and so right here this is proof that it's
asymtotic to n log base 2 n, because the
other things are all 0 to 1.
But what's really interesting about this
is if we look at these functions, so this
is the proof I just went through.
If you have that recurrence, then that
leads to this result.
And but let's look at it in just a little
more detail these three terms.
So the first one is, again, the fraction
part of log n.
And so that's just a plot of the
fractional part of, of log n.
Uh,[cough] now the second one is the sum
of e to the minus 2 for actual [inaudible]
log n minus j.
And that one also oscillates as, as it
increases in it oscillates and that's the
approximate magnitude of it.
And this is the third one that also
oscillates.
So we have these three terms that
oscillate that we're adding together to
give us the difference between log in and
our function.
And what's amazing is you add these all
together you get a smooth oscillating
curve that's very tiny in magnitude.
Now 10 to the minus 6 in magnitude.
Not something you would notice if you
didn't do the math.
In, we're going to see in part two, we'll
look into a little bit, how to do the
math, but certainly It's quite a surprise
to see these functions that are so
difficult, different in character adding
up to this continuous function.
So this is a proof that CN over N minus
log N is this strange oscillating function
that you wouldn't see unless you look out
to six decimal places and the question is,
is there a reason why a recurrence like
that which seems such a natural, natural a
recurrence involving our integer cost/g
should have this strange periodic
behavior.
And the answer is yes.
We're going to see when we get to complex
analysis, analytic techniques into knowing
transferring/g.
That uh,there's a perfectly valid
explanation for such periodicity.
And not only that, it's bound to appear in
the analysis of lots of algorithms that
are based on properties of bit strings
like tries.
So applying that result and taking a look
at the distribution that we get with tries
you can see that it's even more Tightly
bound towards a particular shape basically
divided the center, even then have BSTs.
And so just to quote the results that we
get from this kind of analysis.
The extra space is about 44% of the
external nodes are void.
The expected search cost is about N log
based two of N.
So that's a number of bits you have to
examine.
So and that's a very acceptable search
clause and competitive.
And for leader election, well, that'll be
an exercise.
That's a discussion of trie parameters.