General Strategy

Loading...

From the course by University of California San Diego

Algorithms on Strings

462 ratings

University of California San Diego

Algorithms on Strings

462 ratings

Course 4 of 6 in the Specialization Data Structures and Algorithms

World and internet is full of textual information. We search for information using textual queries, we read websites, books, e-mails. All those are strings from the point of view of computer science. To make sense of all that information and make search efficient, search engines use many string algorithms. Moreover, the emerging field of personalized medicine uses many search algorithms to find disease-causing mutations in the human genome.

From the lesson

Constructing Suffix Arrays and Suffix Trees

In this module we continue studying algorithmic challenges of the string algorithms. You will learn an O(n log n) algorithm for suffix array construction and a linear time algorithm for construction of suffix tree from a suffix array. You will also implement these algorithms and the Knuth-Morris-Pratt algorithm in the last Programming Assignment in this course.

Suffix Array6:50

General Strategy6:43

Initialization9:19

Sort Doubled Cyclic Shifts8:01

SortDouble Implementation6:36

Updating Classes8:06

Full Algorithm3:43

Meet the Instructors

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Pavel Pevzner
Professor
Department of Computer Science and Engineering
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering

In this video you will learn in general how to efficiently construct suffix array;

what are the steps and the substeps, and

we will work out the details in the next few videos.

But first, we need to go from suffixes to cyclic shifts.

A cyclic shift of a string is a string we get

if we write our initial string around the circle.

And then start from any position and go through the whole circle.

So for the initial string ababaa$, we can write down all the seven

characters around the circle and then we will have the following cyclic shift.

The initial string, the string babaa$a, which we'd gather if we start from

character b and so on, moving around the circle.

So these are the seven cyclic shifts of the initial string.

And if we sort cyclic shifts instead of suffixes,

let's see what happens, so these are all the cyclic shifts.

Let's suppose we somehow manage to sort them in lexicographic order.

And then we remove all the characters after the first occurrence of $,

in each of those cyclic shifts.

What we get is actually the suffix array we wanted.

All those strings in the third column are suffixes of S in the sorted order.

This is actually always true, we have a lemma that after adding to the end of

string s character $, which is smaller then all other characters in that string.

Sorting cycle shifts of the string and

sorting suffixes of the stream is equivalent.

We won't prove this lemma, we'll leave this as an exercise,

we'll just use it in the following.

Apart form total full cyclic shifts, which go the full circle starting

from some position in the circle or string S, we'll also need partial cyclic shifts.

And those are basically sub strings of cyclic string S.

So it can take any position in the cyclic string and

go a few characters in the order in the clockwise order from there,

and you will get a partial cyclic shift.

For example, if we take the same initial string and want to build

all cyclic shifts of length 4, you can start from the first character a and

you will get abab, or we can start from b and get baba, and so on.

We will have again, seven different cyclic shifts of length four ending in the $aba.

Now that we only go in the clockwise order, because this is the order when you

try our cyclic string S as three a's written around the circle.

So the general strategy for constructing a suffix array of the string S,

is we start with a simple task, we sort all the single characters of the string

S and those single characters are actually partial cyclic shifts of length one.

So we assign L to one and now we have our base.

We have sorted all the cyclic shifts of length L and

then we will do iterations while L is still less than the length of the string,

we will use our order of cyclic shifts of length L

to sort the cyclic shifts of twice the length.

And we will do that efficiently using the order of the current cyclic shifts of

length L and thus will increase the length of the source suffixes twice.

And then we will again increase it twice and so on and

at some point L will be greater than or equal to the initial string S.

And then we will have sorted the cyclic shifts of length greater than or

equal to the length of the initial string and the order of those cyclic shifts is

the same as the order of the full cyclic shifts of the initial string.

So, this is the general strategy how we'll build the suffix array of the string.

Now let's look at an example of application of these

general strategy in practice.

We use the same string in all the examples.

So this is our string, and we start with sorting the partial cyclic shifts of

length 1, which is just single characters of the string.

And the smallest is $, then go four instances of letter a and

then two instances of letter b.

And six is the position of dollar in the string and 0, 2, 4 and

5 are the positions of letters a and 1 and 3 are the positions of letters b.

In this case, the order of the partial cyclic shifts is 6, 0, 2, 4, 5, 1 and 3.

And on the next step we go from cyclic shifts of

length 1 to cyclic shifts of length 2 and their ordered changes.

First goes $a, because $ is the smallest character and then goes a$, and

then aa, and then two instances of ab, and then two instances of ba.

And the order in this case is already 6, 5, 4, 0, 2, 1, 3,

and that's because dollar is in position 6.

And then a, after which there is a $, is in position 5.

And then a, after which there is an a, is in position 4, and so on.

On the next step we go from cyclic shifts of length 2 to cyclic shifts of length 4

and we get $aba and so on up to baba.

And the order changes again it is 6, 5, 4, 2, 0, 3, 1.

And on the last step we go from these partial cyclic shifts of

length 4 to partial cyclic shifts of length 8,

which are already longer than the initial stream.

And we start from $ababaa$ and end with babaa$ab.

And the order actually didn't change in this case.

And now we have the order of cyclic shifts of length a which

is the same as the order of the full cyclic shifts of the string s,

which is in turn the same as the order of the suffixes of this string.

So if we remove everything after the first occurrence of $ in all those

partial cyclic shifts, we'll get the order of the size fixes of the initial string s.

And so order is now our suffix array.

And in the next video we'll start working through the details of

this general strategy.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play