Now, we're going to finish up by looking at some extra operations that are
supported for string keys when we use Tries.
So, we're going to look at a couple of character based operations that can, that
are quite useful and, and can be supported by the string symbol table API with tries.
One important one is a prefix match. So that's given a prefix, like say sh,
What we want is the method to return all the keys.
Let's start with that prefix. In this case, it'll be shells, shore and
she. Another one is so-called wild card match.
So that's when we don't specify one of the characters, or multiple characters.
So we put a dot to say we'll take any key that matches the other characters and we
don't care what that one is. So he. would match she and the.
And another one is so-called longest prefix.
So now we've got a long key and we want to find the best match that's in our symbol
table that matches that key. The key in the symbol table that has the
longest match with our key. So going, in this case, the ones that's
the longest prefix of shells sort is shells.
Later on we're going to see applications of some of these and the important idea
for now is that these are easy to articulate.
And not only that, they're easy to implement with tries.
Nts tr, and Turner research tree. So, we're going to take our standard API
and add these four methods. So, while there's keys that returns all
keys. And, and, as is our usual practice.
When we have a lot of things to return, we're going to return'em as a, as an
iterable. So the clients can just, iterate through
the what's returned. And that's usually what clients want to
do. And then we have keys with prefix.
Give a string s, and the iterable will return all the keys in the symbol table
that have s as a prefix. If the client wants to find the associated
values, they can do gets to get the values.
And then we have keys that match so that's where we allowed dot to be a wild card, in
S, and we want to return all the keys that, match, S, taking dot to be a wild
card. And then longest prefix of S is the key in
there that's the longest prefix of S. We're gonna see later on.
This particular one plays, an important, role in a, in a more complicated
algorithm. We could also go ahead and add all the
ordered symbol table methods that we considered when we looked at binary search
trees like floor, and, and rank. And, we're not going to take time to do
that right now. It's very straightforward.
So one thing that we haven't really talked about but it's a good warm up for the
kinds of methods that we're going to look up.
Look at for these implementations is ordered iteration.
And this is trie-traversal, so we are going to do an in-order traversal of the
trie, that is, visit the left, now visit the middle, visit the right.
In that traversal, we can maintain the sequence of characters on the path from
the root to the current node just by adding an, adding a character when we go
down and removing a character when we go up.
And when we encounter values, Then we can put out this, the characters
that we have, and that's the way to pull out all the keys in the trie.
So, for example, in this case we go down and we have b, and then we hit the y's.
So we can output,. Say onto a queue we can output by.
And then we go back, we have s, e and a. And, we find a value, so we go ahead and
put out the a. Now we drop the a and do the l, and that's
the l, l, l, l,. and then we get to that s, we have a value we can put ourselves.
And then we can drop these, get back to the s, and get the sh.
She, finite value, and put, put the she in the queue.
Lls and put shells on the queue. Drop all those values down to the h, and
get us sho, shor, shore, Find the value and drop shore onto the
queue. And then finally, t, th, the and, find a
value and put the, down the queue. So it's easy to, very easy to keep track
of the sequence of characters on the path from the rout to every node and every node
check for value and programmer key. That's a ordered iteration and
implementations of these extra operations are just based on multiplying ordered
iteration. So this is a implementation of keys with,
which is essentially of the operation that I was tracing on the last slide.
So if client wants keys, we make a queue. Then we call a recursive routine that
collects all the keys in the try, starting at that node.
And, given a null string, which is, the, sequence of characters on the path to the
given node. When that recursive routine, returns, then
we just return the queue. And the recursive routine does encode what
I said in words, most of the time. This is for a try.
You can do the same thing for a Turner research tree with just a little more
code. So for every character we just move down
the trie for that character add the character to the prefix and also pass the
queue along. If we get a null value, we put what we
have on the queue when we get null when we return. So a very simple implementation of
ordered iteration of the recursive. So that's the implementation of the keys
method. So prefix matches an other things like
that going to work. Are going to work, just by modifying that,
and you're familiar with, prefix matches, When you type, nowadays, in your browser,
a search, function, you're getting, a prefix match of all the things that you
typed or other people have typed, that, matches those strings.
And you find that also nowadays when searching in your address books.
It's a quite, common function nowadays. So let's look at how that looks, in an
R-way trie. So what about finding all the keys in a
symbol table that start with a given, prefix.
Well, we just search for that prefix. And then, then just do a collect at the
keys in that sub tri. So that's, very straightforward.
So you get the node. That is the one you get to by starting
with that prefix and then you just call the recursive collect and boom you're
done. Extremely simple, implementation of keys
with a prefix in an R-way trie.. What about longest prefix?
And here's one that, is, is, very, actually very heavily used, in the
internet. If your query strings are IP addresses on
the internet and you have some given destination IP address, the router has a
lot of IP addresses in a routing table. An it wants to choose the one that will
get you as far as close to the destination as you can.
So it's going to choose the longest prefix.
So if you want to get to 128 by 112, you can think of these as hops on the way to
where you want to get, where eleven is the final destination.
And essentially this table says, it knows how to get this far and so that's what it
wants is the longest prefix. The longest prefix matches this one. Well,
it doesn't know how to get any further than 112 and this other one only to 128.
I, and this operation gets performed extremely often on the internet nowadays.
Just a quick note, It's not the same as the floor function
and it actually is a kind of a string operation.
These things actually, usually on the internet, they're not represented as
strings. They're represented as binary numbers.
But in machine or assembly language implementation tries are even easier.
You can just take a bunch of bits and use them as index into a table to move down
the try. And actually tries are pretty old because
so easy to implement data structures in that way in the past.
You'd be surprised at how much of our computational infrastructure is built by
Program or consists of programs that are written in machine or assembly language
that can make use, efficient, really efficient use of low level representations
like this. But it's also useful in higher-level
languages. So what does it look like in an R-way
trie.. Well, all we're going to do is just do a
search and then we're going to keep track of the longest key that we encountered.
So, we have a path. And on that path there is the most
recently seen value that's the longest key that we found If we end that at no link
that's fine. It's the, if there is a value on that node
that's kind of a no link that's the value we're going to return.
So that's a very straightforward implementation.
Just keeping track of the longest key encountered on the search for our key.
That's implementation of longest prefix of and the usual set up of, of making
recursive calls. And this code is quite straightforward.
And application of this one and so-called T9 texting.
And now you know, when we do a course like this, we try to keep up with modern
technology. And modern technology is moving almost as
fast as we can. There are lots of young people who really
don't know about texting with keypads anymore.
But there's a certain range of, you know, five or ten years where people got
extremely adept at doing so called multi-tap input, where the only keys on
the phone were the nine keys to dial numbers.
And then you had three letters associated with each number,
Like on old dial telephones. And to enter a letter you had to like to
enter an H you had to tap twice, cuz that's the second letter on the four key
you had to tap four twice or something like that.
So, The so-called T9 text input would use the
kinds of algorithms that we're talking about to make it so that maybe you didn't
have to do multi-tap. So rather than type two 4's, you would do
a tries type search to figure out which word that you typed.
And that now looked, It'll look good to us as a potential
application for a while. Glad we didn't spend too much time on it.
If you study this keyboard, maybe you'll see, see why.
Well you think about how to implement it. But once we get into it, we realize, Kevin
realized there's no S in this sample keypad, what happened to the S?
So what are we going to implement because even if there's no S there, so what
exactly are they doing and well maybe this is a bit of a fantasy that this is the
response that, maybe these people lived in a world with no S's.
Mmm. Well anyway, we've moved on from tries
from, from that type of, way of entering text.
But I still want to mention a few more ideas because the basis behind tries and
Turner research trees is still out there and is still really an important part of
our infrastructure. And there's some really great algorithms
that we just don't have time to cover. Now one of them's an old algorithm called
Patricia. And, This one, is a really interesting and
intricate algorithm. Particularly when implemented for binary
tries, where you just do a bit at a time. And people, again, implemented this kind
of algorithm in machine language. And got extremely efficient performance.
If we cast it in, in, our way tries that we've talked about it's really the best
way to think about it is, a way to remove one way branching.
It seems wasteful, to have, all these nodes that just have one branch.
And so one of the main ideas behind Patricia there's others that, don't
really, show up, in the level, high level representation we're using.
But one of the main ideas behind Patricia was rather than associate a character with
each node, Associated sequence of characters with
each node, so you just don't have any one way branching.
Implementing this is maybe one step beyond this course but maybe it's within what we
could do in this course. Where just not going to take the time to
do so. And you'll find implementations that in
practice avoid the one-way branching that are used in many, many applications,
performance critical applications for searching nowadays, I already mentioned IP
routing tables. There's probably, you know, no piece of
code that's executed more often than that one.
That's based on a trie type algorithm. And we have these other applications
listed as well. It's got some other names too.
Another thing, is, so called, suffix tree. So, that's, building a tree from a suffix
table. So, we talked about having, for suffix
sorting, we talk about applications. You can also build a search structure from
suffixes of a string. That admits, all kinds of, fast string
processing application. And again, usually, eliminate on way
branching in suffix trees, and also amazing, amazingly you can get'em
constructed in linear time. And there's all kinds of interesting
applications of suffix trees probably the most important now a days are in
computation biology databases. Again extensions of the kinds of
algorithms that we've talked about today. So I think the bottom line for considering
string search trees is that it's a real success story in algorithm design and
analysis. It's a number of clever algorithms that
really have made a difference in the kinds of operations that we can perform in the
amount of data that we can handle in modern applications.
We, we started with red-black BST's which is a pretty good solution for a general
symbol table. And also hash tables, which are also
widely used. But with tries, and Turner research tries
we have a performance guarantee where we'll only have to really access log-in
characters. And when you think about that, that's,
even when N is huge, that's going to be a pretty small number.
Say we're looking among billions, billions of things log in, even in you only have
two wave branching would be 30. And when we have 256 way branching, it's
way, way smaller. And that's just the number of, so it's the
number of characters accessed. And the, really the bottom line is, if
you, you can set things up nowadays even on the internet when there's huge, huge
amounts of data out there you can set things up so that you can only need to
look at maybe 100 bits to get at anything. We think about 100 bits, that's specifies
two to the 100th of possibilities. And two to the 100th is a huge number.
There are not two to the 100th pieces of information, even on the internet, even
will ever exist on the internet in the. Into this galaxy.
But with just 100 bits, which really isn't too much, we can search for anything
efficiently. And that's an amazing success story for
algorithm design and analysis. So that completes our look at tries and
Turner research tries.