Updating Classes

Loading...

From the course by University of California San Diego

Algorithms on Strings

438 ratings

University of California San Diego

Algorithms on Strings

438 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

Hi, in this video you will learn how to update the equivalence classes

of the double cyclic shifts after sorting them.

And that will be the last step before we can actually present the whole algorithm

for building the suffix array.

So to update classes, we need to compare the pairs of

single shifts which constitute the double cyclic shifts which we have just sorted.

We have already sorted the pairs.

So, we just need to go through them in order and

compare each pair to the previous pair.

If it's the same, then we need to assign it to the same class.

If it's bigger, then we need to create a new class and assign it to this pair.

To compare the pairs, we can compare them separately by first element and

then by second element.

Of course the elements of the pairs are cyclic shifts and

we don't want to compare them directly character by character.

But, for that we already know their equivalent class is of

the single cyclic shift, and we can just compare

the equivalence classes instead of the cyclic shifts themselves.

So we can compare any two pairs of single cyclic shifts in constant time.

Let's look at an example.

S is our initial string and suppose we've already sorted

the doubled cyclic shifts of length 2, and

our initial cyclic shifts were of length 1.

So we have our array class of the equivalence classes of

the cyclic shifts of length 1, which is basically letters.

And remember that this array has one element which is equal to 0

which corresponds to the dollar, and it is in position six.

We have four elements which are equal to 1 which correspond to letters

a in positions 0, 2, 4, and 5.

And we have two elements which are equal to 2 which correspond to letters b in

positions 1 and 3.

So these are the equivalence classes of the single cyclic shifts.

Now for the double cyclic shifts we can write them down in

the order because we've already sorted them.

And we know the new order which is the order of the double cyclic shifts.

They go 6, 5, 4, 0, 2, 1, 3.

From $a to ba.

And along with each doubled cyclic shift,

we'll also write down the pair of the equivalence classes of its halves.

For example, for $a, the equivalence class for dollar is 0 and

the equivalence class for a is 1.

So it corresponds to pair 0, 1.

And for ab, for example, the equivalence class of a is 1, and

equivalence class of b is 2.

So we write down the pair 1, 2.

These are the pairs of the equivalents classes of the single cyclic shifts.

And now we need to compute the equivalence classes of the doubled cyclic shifts.

And write them down into the array newClass.

To do that, we go through the double cyclic shifts in the sorted order

using array newOrder.

And we start from the first one, which is $a.

And we write down value 0 for its class in position 6 because

it is in position 6 as we see from the array newOrder.

Then we'll proceed to the next doubled cyclic shift.

And to assign class to it, we need to compare it to the previous one.

And of course in this picture, we could compare directly these double cyclic

shifts the previous one, and determine that it's different.

But in practice, in general stage we don't want to do that.

And instead of comparing the cyclic shift directly,

we compare the pairs of numbers written to the right from them and

we see that the pair 1, 0 is different from the pair 0, 1.

And we do this comparison just by two comparisons of numbers

instead of comparing full cyclic shifts.

As far as this double cyclic shift is different, we need a new class for it.

And we assign it to class 1.

And write it into position 5 because this is the position for

this double cyclic shift as we see from array newOrder.

Now we proceed to the next one which is aa.

We again compare it with the previous one, by pairs.

1, 1 on 1, 0 are different pairs, so we write down a new class again,

class 2 in position 4, as given in the array newOrder.

Then proceed to ab.

It is again different.

1, 2 is different from 1, 1.

So we create a new class 3 and put it in position 0 as given by array newOrder.

Then we'll look at ab again and it is the same as the previous ab.

As we see from pairs 1,2, 1,2 which are equal.

So, we don’t need to create a new class.

We write down the same class 3 into position 2 as given by the array newOrder.

Now look at ba, it is different from ab.

So, we create new class 4.

And then the second ba's of course are equal to the previous ba, so

we write down 4 in position 3 as given by the newOrder array.

So this is how it works, updating of the classes.

Now let's look at the code.

So the procedure UpdateClasses does exactly the same as we did in the example.

It takes as input array newOrder, the order of the double cyclic shifts.

It also takes classes of the single cyclic shifts.

And also it takes the length of the single cyclic shifts as inputs.

And it will return the array with equivalent classes

of the double cyclic shifts as a result.

First we initialize variable n with the size of newOrder.

Basically n will be equal to the length of the string but

we don't have string as an input so we need variable to compute it's length.

And we initialize the array newClass with an array of size n.

And first we assign class 0 to the smallest double cyclic shift which is

given by newOrder of 0.

And then we go through all the double cyclic shifts from position 1 to n-1,

and we need to compare the double cyclic shift number i with

the double cyclic shift number i-1.

To do that, we first compute their starting positions.

Cur is the starting positions of the doubled cyclic shift number i, and

prev is the position of the previous one.

And also need to compute the positions of their middle

of the position where their second half starts.

So, we need to compare them half by half.

So, cur and prev are the starting positions of the doubled cyclic shifts and

mid and midPrev are the starting positions of their second halves.

To compute them, we just take the position clockwise to the right by L.

So we add L and take everything modular n.

Which is the length of the string.

And now we do just what we did in the example.

We compare the classes of the current position and the previous position.

And the classes of the starting positions of the second halfs.

If at least one of the halfs is different,

it means that the pair is different from the previous one.

And we need to create a new class, increase the current class by 1 and

assign to the current position.

Otherwise, the pair is the same as the previous one, and

we don't need to create a new class.

We just assign the same class to the current position.

And we then return the array with the new classes of the double cyclic shifts.

We state that the running time of this algorithm UpdateClasses is linear.

And that's easy to prove because, well basically, we only have one for

loop with linear number of iterations and constant time operations happening inside.

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