Full Algorithm

Loading...

來自 University of California San Diego 的課程

Algorithms on Strings

502 個評分

University of California San Diego

Algorithms on Strings

502 個評分

課程 4（共 6 門，Specialization 数据结构与算法）

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.

從本節課中

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

與講師見面

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

Now to the full algorithm for building the suffix array, finally.

So procedure BuildSuffixArray takes in only string S and

returns the order of the cyclic shifts or of the suffixes of this string.

We assume that S already has $ in the and, and

$ is smaller than all the characters in the string.

We start with sorting the characters,

single character cyclic shifts of S, and save the result in the right order.

And also compute the equivalence classes of those characters and

save the result in the right class.

And we initialize the current length as one.

And then we have the main loop, which proceeds while the current length is still

less, strictly less than the length of the string.

If it is, then we first need to sort the double cyclic shifts of length to L.

And then we also need to update their equivalence classes so

that the next iteration can use them to again sort the doubled cyclic shifts.

And then we just multiply L by 2, and go on in our while loop

until we get to the station when L is more than or equal to the length of S.

And by the time array order will contain the correct order of all the full

cyclic shifts of the string S, which is the same as the correct

order of all the suffixes of the string S if it has a $ on the end.

And the running time of BuildSuffixArray procedure is length

of S times logarithm of that, plus size of the alphabet.

So the size of the alphabet is because of the counting sort

of characters in the beginning.

because we're sorted them in time proportional to length

of the string plus size of the alphabet.

But if we wanted, we could just sort them in time S log S

without using the count and sort to sort the characters.

So we could actually remove the plus alphabet from

the BuildSuffixArray asymptotics.

Although in practice usually the alphabet is very small, so

we don't need to do that.

And using counting sorts is better than actually sorting the characters in

S log S.

And also compute the classes of the characters in linear time after that.

In each while loop iteration, we do both sorting of the double cyclic shifts and

update their clusters in linear time.

And we have only logarithmic number of iterations, because L is doubled every

iteration, and as soon as it gets at least S or more, we stop.

So it's on a logarithmic number of iterations, so all in all,

the while loop runs for S log S.

And adding to that, the initialization cost,

we get S log S plus size of the alphabet.

So now you finally can build suffix array of a string S in time length of S

times logarithm of that using linear mode mode of memory.

And you can do not only that, but

you can also sort all cyclic shifts of a string in the same time.

And you know that suffix array handles many fast operations with the string.

And also, in the next lesson you will learn to build suffix tree of the string

from its suffix array in linear time.

And that combined will give you an algorithm to build suffix tree in

time S log S.

And of course you already knew how to build a suffix tree in quadratic time, but

S log S is much, much better than that.

So you will learn that in the next lesson.

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2019 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取