Loading...

Full Algorithm

Course video 22 of 26

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.

字符串算法

加州大学圣地亚哥分校

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

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.

查看授課大綱

您將學習的技能

Suffix Tree, Suffix Array, Knuth–Morris–Pratt (KMP) Algorithm, Algorithms On Strings

教學方

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Pavel Pevzner
Professor
Neil Rhodes
Adjunct Faculty

腳本

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

課程、專項課程和在線學位均由全世界一流大學和教育機構的頂尖授課教師教授。

Join a community of 40 million learners from around the world

Earn a skill-based course certificate to apply your knowledge

Gain confidence in your skills and further your career

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

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

通過 App Store 下載

通過 Google Play 獲取