.finally Finally we're going to look at suffix arrays and string processing using
this data structure that has really played a very important role in, string
processing applications that would not otherwise be possible.
To get a feeling for the idea, we're going to look at a really old idea that you're
actually familiar with called keyword in context search.
And the idea is that you're given a text, a huge X and what you want to do is
pre-process it to enable fast substring search.
That is, you want a client to be able to give a query string and then you want to
give all occurrences of that query string in context.
So, if you look for the word, search, it will give all the occurrences of where the
word search occurs in context. Or better thing is another one.
And that's a, a very common operation. One, you're certainly familiar with it
from web searching, in your browser. And there's many other applications.
This is a pretty old idea that dates back to the late 50's, early 60's people have
always wanted to do this. And there's an easy way to look at it
called suffix sorting. The idea is you take your input string,
and then, form the suffixes. remember when I talked about at the beginning with
JAVA's string data type, you can get this done in linear time because each suffix is
basically a pointer back into the input string.
So the suffix, remember, the I suffix just start the character I and take the rest of
the string. So, what this does is, it gives, sort
keys, that, contain, kind of the, the, Pieces of the string itself in context and
all we do is just, run a sort on that suffix.
And what that sort does is, it brings if you do a search, it brings the things that
you're searching for, close together. And, you can use, once you've done that
suffix sort, you can use a binary search to find all occurrences of the string out
of there. That's the, basic idea of a keyword and
context searching. You suffix sort the text, then do binary
search to find the query that you're looking for.
And then you can, scan for wherever the binary search ends up.
And so, this is all the places where, the word search occurs, in the text of Tale of
Two Cities, And then, you can use this index, to,
print out the context of whatever's needed.
It's a fine and effective way, for solving this important practical problem.
And that's interesting, but I want to talk about another really important problem
that, it has, hugely important applications. This is the longest repeated
substring problem. So you're given a string of characters,
find the longest repeated substring. in this case, this is genomic data, and,
there's the example of the longest, repeated substring. And now, in scientific
data, the long repeated substring is often something that scientists are looking for.
And so, and these strings are, are huge. it might be billions of these, characters.
And so, it's really important, not only to know that you can find long substrings
efficiently, but also, that you can do it for, huge, huge strings.
Another example is, cryptanalysis. Where, a long repeat in a file that's
supposed to be, encrypted random file indicates that somebody did something
wrong. It might be the key to, breaking the code.
Another example is data compression. When you've got a file that's got a lot of
repeated stuff in it, you might, want to do this operation, to take advantage of,
of these long repeats and not keep multiple copies of them.
Here's another example, this for, studying or visualizing repetitions in music.
In this example, every time there's a, a repeat of the notes then, there's, a, an
arch drawn to, visualize the repeat. And it's, the arch is thick if, the number
of repeats is long. And it's high if the repeats are far away.
And this, tells, is an interesting way to analyze, repetitions, in music.
So, how are we going to solve this problem?
Very simple to state problem. Given a sequence of N characters, find the
longest repeated substring. As with many problems, there's, an easy,
brute force algorithm, that, at least gives us an idea of what, what the
computation is like. But it's not going to be useful for huge
strings. And that's you try all possibilities, all
pairs of indices I and J and then just compute the longest common prefix for each
pair. The problem with that is that if N is the
length of the string, you've got, N squared over two pairs.
And for every one of those pairs, you might have to, match them up to length D.
It's definitely quadratic time, more than quadratic time in the length of the
string. And can't be using that for, you're not
going to be able to use that for strings that are billions of characters long.
Another way to look at one way to solve the longest repeated substring, is to use
a suffix sort. In fact, just we talked about before.
So, I would take out our input string. Reform the suffixes.
And then sort the suffixes and that brings the long repeated substrings together.
So, that's a quite elegant and efficient solution to this problem. just build the
suffix array that's a linear time process. Do the sort.
We, we just saw we can do that, with n log n character, character compares.
And then go through and find the repeated the substrings.
So, it's just one passthrough to check for adjacent substrings to see which one's the
longest. And this is very easy to code up.
Here's the Java code for computing the longest repeated substring.
We get the length of our string out. We build our suffix array.
Remember that's linear time and space because of Java string implementation
allows us to do substring and constant time.
Then we go ahead and sort the suffixes, and then find the least common prefix
between the, adjacent suffixes in sorted order.
Just keep track of the max so that's longest, repeated substring.
And if so, for example, this sentence about such a funny, sporty, gamy, jesty,
joky, hoky-pokie, lad, is the longest repeated substring in the text of
Melville's Moby Dick. And now we run that one to, prove that
we've got a linear-rhythmic algorithm because there's a lot of characters in
that. And you're not going to find this, without
a good algorithm. And, and this is just a humorous approach
to what we've, talked about today. If you have, five scientists that are
looking for a long substring, in a genome, that, they might encounter, this problem,
with a billion nucleotides, and there are plenty of scientists that are not aware
of, important algorithms are the ones, like the ones that we are talking about.
And the one that uses the good algorithm is definitely more likely to find a cure
for cancer. But there is a flaw even in this, that
computer scientists discovered as they got into ever more complex algorithms for
problems like this, and that is if the, the longest repeated substring is long,
there's a problem. So this is just some, experiments, for,
finding the longest, repeated substring in various files.
From just a program to, the text of Moby Dick.
Or a chromosome with 7.1 million characters.
And, using, the, brute force method, you get stuck, and too slow, very soon.
But using, a suffix sort, you can get these jobs done, even for huge files like
the first ten million digits of pi. By the way, if there was a really long
repeated substring in the first in the digits of pi, that would be news.
Maybe it would help us, understand more, about this number.
So lots of people, write programs of this sort.
But the big problem is if you have a really long repeated substring, then
suffix sort is not going to work. Our fast algorithm, doesn't complete.
So what's going on? In the explanation is really simple.
If, for example, you have two copies of something.
When you form the suffix array, what happens is that if you have the longest
repeat, but you also have every version of that repeat appears.
And you have to look for those when checking, for the longest repeated
substring. So, if D is the length longest match,
then, just to check for the longest common prefix, you got to do, at least one + two
+ three + four up to D character compares. Which means it's going to be quadratic
just for checking for the longest common prefix of adjacent, elements in this
algorithm. It's also a problem for the sort.
So, if you have very long repeats, we still don't have an algorithm.
So, the question is, that was confronting, computer scientists, in the late 80's,
early 90's is how can we get this done? What's the best algorithm for this
problem? And there was a great algorithm called the
Manber-Myers algorithm, That I'll talk about in just a minute.
That got the job done in linear rhythmic time.
And actually, there's a clever old algorithm that uses the data structure
called, suffix trees. But it was really the Manber-Myers
Algorithm that, got people, excited about this area.
And so, I want to describe that, briefly. Actually, these two computer scientists,
one of them went on the become chief scientist of an internet company.
The other one went on to become chief scientist of a company that won the race
in sequencing the genome. In both cases, good algorithms for
processing long strings are very important.
And this is a great algorithm. Now, it's a little too complex to give all
the details in a lecture, but I can give a pretty good idea of how it works.
So the overview is that, it's kind of like an MSD, sort.
But, what it manages to do is double the number of characters that it looks at in
each passthrough of the array. And, the idea is that, you, since you're
doubling the number of characters that you look at each time.
It, it finishes in, log in time that's the size of the, suffix array.
If, if you double until you get n, it's log n.
And it turns out, what's really ingenious about the algorithm is that, you can do
it, do each phase in linear time. So, this is an example of how it works.
So, it's, we going to do a suffix sort. And then I'll, I'll talk about the least
common prefix as well in a minute. So, sorting the first character, while we
just use key, key index counting or something like that.
So we know how to do that, in linear time. And then the idea has given that sorted on
the first character. We can sort it, easily sort on the first
two. Well again, we could use, key index
counting. So now, what we can do is, double the
number of characters that we, involve each time.
So, the next phase of the Manber-Myers algorithm, now gets it sorted on four
characters. And, of course, as we, the more characters
we have sorted on at the leading part, the smaller the [INAUDIBLE] files in the
trading, in the trailing part. So, that's, certainly a feature.
And then, in this case, after we get to, eight characters, and all our sub files
are of size one, and we're done with the sort.
Now, the key to the algorithm is, the idea that, once it's going, it uses what's
called an index sort, Which essentially means that it can do
compares in constant time in the middle of the algorithm.
Now, lets just take a look at, at, at how that works.
So lets look at, trying to compare string zero with string, nine.
And we know that we've already got the thing sorted on, four characters and we
want to sort it on eight So, zero and nine are equal on the first four characters.
They're in the same subfile. So, now we're going to get it sorted on
the other. But the thing is if we add four to our
given indices. So, we're at zero, and we add four.
That gets us to four, and we're at nine. We add four that gets us to thirteen. we
already know that the thing is sorted on those characters.
And, we know that, thirteen appears before four in this sorted list.
It's already sorted. And we can keep track of that by, using an
inverse array which says, for every index, where it appears in the sorted order.
So, this says that thirteen appears at position six, and four appears at position
seven. That is, thirteen appears before four.
So, when we're trying to compare, the, this, string here, that's the zeroth
suffix with the ninth suffix, We can go in and again, add four to get
four, add four to get thirteen go into the index array and see which one is less and
the one that appears first is going to be less.
So, that's a constant time, comparison. Thirteen is less than or equal to four
because the inverse of thirteen is less than the inverse four, which means that
suffixes of nine, if you take eight characters out of nine and eight
characters out of zero, it's less. It's a really, simple and of course,
Easy to implement operation. So, maintaining the inverse, I can get
constant time string compare. So, what does that imply, for the whole
suffixsort??uh Well,
With a constant time compare, then, I can get, at a minimum, I can get an, an analog
N sort, just by using quicksort or mergesort.
And then, I get much faster than quadratic performance no matter what the strings
are. That's a big key to the success of this
algorithm. And actually, if, if you use a version of
three-way quicksort, it's been proven that it even gets down to linear time for the
sort, No matter what the input is.
That's one thing, and then the other thing is when you need to do, the longest common
prefix to look for the, longest match after the array is sorted you can also do
this constant time, string compare and get the job done.
So this is really an in-, ingenious algorithm that, can get, suffix sorting
done very fast. even in the presence of, a huge repeat.
And I think really underscores, the importance of careful algorithmic
thinking, in addressing new computational challenges.
So, string sorting, just to summarize, is a really, interesting area of inquiry.
For one thing, we can develop linear time sorts for many, many applications.
We, we thought, we're doing well when we had, n log n sorts, but actually we can do
much better for many applications. And in fact, we can even get to sublinear
where we don't even have to examine all the data.
In today's world, when we have huge amounts of data, to be able to, get it
sorted without even looking, at it at all is really quite a miracle.
Three-way string quicksort,,you you can't do better than that in terms of the
numbers of characters that you have to, examine.
And it's a lot of deep mathematical analysis, behind that result.
But I think the other lesson to learn is that algorithms like three-way string
quicksort and Manber-Myers, show that we really have a lot to learn still in string
processing. And they're not really random.
In fact, a lot of times we're looking for non-randomness and we might want to use
specialized algorithms. So, at string processes or introduction to
string processing, We're going to look at many other string
processing examples in the coming lectures.