Now we're going to look at Tries, which is
a class of common material objects that
now really hasn't only come into study in
recent years due to computer applications.
And are not found in classical
comminatory, but actually are very
interesting rich comminatorial analytic
properties.
So I'll spend some time,really, just
talking about what Tries are and, and
their applications before we talk about
the analysis.
So, one way to look at a Trie is just at,
as a binary tree.
Where the external nodes can be marked.
Black ones are called void nodes and then
the white ones are non-void.
So you take a binary tree, and mark some
of the external nodes to be void.
Now there's a rule, and that is that you
can never have two void nodes that are
siblings of each other in a leaf.
So, and assembling of a void that's not
void, that's the rule so that's what a
Trie is.
Now that seems kind of arbitrary, but
you'll see, when we look at applications
how these rules play a role.
That actually for an exercise you might
give a recursive definition of what a try
is.
So the most usual way that we think of
tries is as representing a set of
bitstrings.
Each try corresponds to a set of bitstring
where each non void external node
represents one bitstring.
And the, you get the bitstring by taking
the path from the root to a node.
Taking a zero when you go left, and one
when you go right.
For example, if we go zero, zero, left,
left, right, right, left we get down to
that non-void external node.
Then we say that, that node represents the
bitstring that we got.
That defines the path that we got there 0,
0, 1, 1, 0.
Or over here 0,0, 1 0, I'm sorry, 1, 0, 1,
0.
That non-void node represents the
bitstring 1, 0, 1, 0.
The path from the root to a node defines
the bit-string.
So now, eh, the, non, the void nodes, have
a different interpretation that derives
right from this definition.
For example if we go right, 4 times, and
then left, we come to a void node.
What that means is that no string with
that prefix is in the set of strings
represented by this trial.
We're trying to represent in this case 1,
2, 3, 4, 5, 6, 7 bitstrings and then the
void nodes represent the prefixes of all
the bitstrings that aren't represented.
So that's what we think of as a Trie
corresponds to a set of bitstrings, or
another way to look at it is it's all
worked out here.
So this Trie represents as I said, 7
different bitstrings.
And those are shown at the top.
Now, on the left is the bitstrings that
from that set that start with 0.
And on the right, the try on the right
represents the bitstrings for that set
that start with the 1 with the 1 stripped
off.
And so recursively going down, that's
another way to see the sets of bitstrings
that are represented Now this only works
for bits, sets of bitstrings said to be
prefix free So that is no member of this
bit, this set of bitstrings is a prefix or
another, of another one of that set.
We can handle that by a using void and not
void internal nodes.
But in applications, I'm going to talk
about that are typical with, it's okay to
just work with prefix free set.
That's so like, for example, fixed-length
all the bits bitstrings are the same
length.
And it's prefix free because they're all,
all different.
They're all the same length and they're
different.
You can't have one be the prefix of
another and that's a typical and useful
application of Tries There's lots of
applications of tries.
If you look in our algorithms book, you'll
find Trie code for sorting, for simple
tables with string keys, and for suffix
arrays, which I'll refer to in a minute.
But they play a role in classic data
compression algorithm and Huffman's code
and Lempel-Ziv-Welch Compression.
And we'll look at the use of tries to
understand decision-making collision
resolution leader election algorithms.
They play a very important role nowadays
in network systems, in bioinformatics,
internet search all kinds of commercial
data processing.
Very important data structure that's often
overlooked.
That's why I'm taking the time to talk
about now some of these applications to
motivate the analysis, because they're not
so easy to analyze as we'll see.
So here's the, the basic application which
is for symbol tables.
So Trie represents a set of bitstrings.
So what we have is, just going from the
definition a search algorithm for
determining whether a given bitstring is
in the set represented by the Trie.
And the basic idea is if the leading bit
of your key is 0, go to the left.
If it's 1, go to the right, then use the
remainder of the string recursively.
If you get to avoid external node, It
means that the one you're looking for is
not in the set represented by the tri.
If you get to a non void external node,
and you're at the end of your bitstring,
then you report success.
You did find the key.
So for example, let's say we're going to
search for the bitstring 0011 in this
Trie.
Start with the 0, go to the left.
Next one is a 0, go to the left.
Next one is a 1, go to the right.
Next one is a 1, go to the right.
We're at the end of our string and we're
on a, non-void external node, so that.
String is in the set of its string
represented by our Trie.
Let's look for 10110.
So start with a 1, go to the right, 0, go
to the left, 1 go to the right, 1 go to
the right.
We hit a void external node, so that
string is not in the set represented by
our Trie.
It's a very natural search algorithm.
Have the Trie represent a set of
bitstrings.
Of course, everything can be represented
as a bitstring.
So this is a natural algorithm for
anything represented in a computer.
So of course we're going to want to for an
algorithm like this want to know what's
the expected search time under a
reasonable model for of randomness.
That's a type of thing that we want to
analyze.
Now what about inserting new keys, or new
bitstrings into the set represented by the
Trie?
Well, what we'll do is we'll insert by
searching until we get to a void external
node.
So if we wind up at a, a, an internal node
or non-void external node, that means that
we'll have a prefix pre-evaluation and we
can deal with that in some way, but insert
a new key, it's going to wind up at a void
external node.
So to insert 0, 1, 1, 1, 0, we go left for
the zero, one, right for the one, and now
we're at a void external node.
And so now, what we want to do is, if for
each remaining bit in our key that we want
to insert, we want to add a new internal
node and, with one void, external child
and then the other one corresponding to
our bit.
So in this case, our next bit is 1, so we
put, if the key start at 0, 1, 0, then
it's not in the set of strings, but 0, 1,
1, that could be this one.
And then we do it again for another one,
and then the next bit is 0.
So we put the void external mode to the
right and then non-void to the left.
So that's how we would insert 0, 1, 1, 1,
0, into this Trie.
Now, there are variants where you just
keep track of the tail in someway with
pointers and people in those are well
studied.
And there's lots of reasons to do that
sort of thing, but the simplest version
also is very effective that's what we'll
stick with right now.
So that's it, a search algorithm and an
insertion algorithm that gives the basis
for a simple table using the Trie data
structure , which is a very useful
algorithm.
And then natural question that probably
already occurred to many of you is what
about these void external nodes.
That seems kid of a waste to have all
these void external nodes there in, in the
scape structure.
And so we're going to want to analyses how
many there are to make sure that we
understand how much space a Trie takes.
But it's a very compact data structure and
that analyses is certainly interesting
and, and relevant in practice.
Okay so, here's another application of
Tries.
What we want to do is, we have a, a given
string, s, and just for an example I'll
use a genova string made up of As, Cs, Ts,
and Gs.
And these things could be huge, it could
be billions of letters.
And we want to know, is a particular
substring in, in our string.
So like for this string, is ACCTA in
there, and the answer is yes, starting at
0.
What about CCT?
Yeah, there's plenty of places where CCT
occur in this string.
What about TGA?
No, there's no occurrence of TGA.
If we have a specific string that's huge
and we want to be able to do substring
search, there's all kinds of applications
in genomics, where it's important to be
able to do an operation like this quickly.
So search in genomic data.
And this is also useable, useful in
internet search.
When you do a Google search you not only
get to the page that you're looking for,
but you get context you get where the
substring is in that page.
And that's uses a beta structure like this
and many other applications.
So the solution method that I'll talk
about is the so called suffix multiway
Trie generalizing the Trie for this
problem.
And so the idea is to if you have, if
you're given string, what we're going to
do is work with all the suffixes of the
string.
So the original string ACCTAG, GCCT, we
leave off the A then we have CCTA and so
forth.
So if the string is of size N, we have N
strings for all the suffixes.
And we're going to treat those as
different strings and just insert them
into the Trie, that's called a suffix
Trie.
Now notice that's prefix tree, prefix
free.
None of these is a prefix of another.
Because they're, they're all different
lengths.
It's a prefix free set.
And they all end we have them all end with
a character that isn't found anywhere else
in the try.
So then the idea is that every internal
node of this Trie corresponds to some
substring of, of our original string.
So to answer the question is X a substring
of X.
We use the characters of our query to
traverse the try.
So for example, if we're looking for A, C
CTA then we can when we get to a nonvoid
external node that tells us that one is in
there, and it tells us what position it
is.
So if built the try AC if we see something
that starts with AC then we look starting
at position zero and continue our search,
and the ACCTA is there.
If we encounter a void node then so for
example, if we're looking for CCT.
Then we find a void node.
Sorry, CCT is there because we found it in
an internal node.
But something like TGA we end up at an
void node in rather So this is a very
simple algorithm to answer is this is x
the substring of questions and a find
application of Tries.
And again the number of void nodes in what
does it mean to be a random try and how
long is the search and so forth?
All of these kinds of questions are going
to be important and relevant in practice.
Here's another application of tries.
Tries as a model for an algorithm so
called, leader election algorithm.
This is important in distributed systems.
So the idea is you have a group of
individuals and they would need to elect a
leader and what they're going to do is
each flip a coin.
So it's distributed, there can be a large
number of them that flip a coin.
And we'll count ones as winners and zeroes
as losers.
And so everybody that gets a one when they
flip a coin survives for the next round.
And the first that got zero are gone.
So now we just worry about the one is,
that got one is and again they each flip a
coin.
In this case the 2 green one is get a 0 so
they're the losers and they're eliminated
and only the one is that got one continue
to the next round.
They each flip a coin, again two are
eliminated and three are left, the ones
that got 1s, they each flip a coin.
In this case, that all get 1's so they all
advance to the next round and then we have
a void no.
And then, again they nobody eliminated.
Now they each flip a coin and only the
blue one survives so that's the winner.
So this is a very simple method for
choosing a leader in its distributed
banner among n people.
Now there's a possible problem, and that
is a procedure might fail.
What if they all throw 0 then in that case
they're all losers.
There's no winner, procedure might fail.
So obviously we're going to be interested
in what's the chance of failure.
Well, it's the probability that the
rightmost path in a random try ends in a
void no.
What do I mean by a random Trie?
Well, it turns out that the model that
associates with this and also works for
symbol tables is it's a try that you get
by inserting infinite length random
bitstring into an initially empty try.
So there's 3 diverse applications of the
Trie data structure for a symbol table.
For sub-strain search and for distributed
leader election.
And all of this is to motivate studying
this combinatorial structure.
So for distributed leader what I want to
know, what's the number of rounds?
Well, it's the expected length of the
rightmost path in a random Trie that
somebody rounds, and then your probability
of success from that you can calculate how
effective this method is going to be.
So that's a brief description of tries and
next we'll look at analysis of Trie
parameters.