|
所在平台: Coursera |
课程主页: https://www.coursera.org/learn/algorithms-on-strings
课程评论：没有评论
课程名称：字符串算法 课程概述：在这个世界和互联网中，文本信息无处不在。我们通过文本查询搜索信息，阅读网站、书籍和电子邮件。在计算机科学的角度来看，这些都是字符串。为了理解这些信息并提高搜索效率，搜索引擎使用了许多字符串算法。此外，新兴的个性化医学领域也运用许多搜索算法来寻找人类基因组中导致疾病的突变。在此在线课程中，您将学习一些关键的模式匹配概念：前缀树、后缀树、后缀数组，甚至包括巴罗斯-惠勒变换。 课程大纲： 1. **后缀树**：您将学习如何在常数时间内搜索字符串中的最长重复子串。1973年，彼得·维纳提出了一种基于后缀树的惊人解决方案，这一关键的数据结构在模式匹配中被广泛应用。 2. **巴罗斯-惠勒变换和后缀数组**：虽然使用后缀树进行精确模式匹配很快，但使用后缀树进行近似模式匹配的方式并不明确。1994年，迈克尔·巴罗斯和大卫·惠勒发明了一种出色的文本压缩算法，即巴罗斯-惠勒变换。这个算法在生物学家寻找基因组突变方面发挥了重要作用。 3. **克努斯-莫里斯-普拉特算法**：在这一模块中，您将了解如何在O(|Text|)时间内进行精确模式匹配，而不是像暴力算法那样的O(|Text|*|Pattern|)时间。此外，您还将了解如何快速构建后缀数组和后缀树的高效算法。 4. **构建后缀数组和后缀树**：本模块将继续深入字符串算法的算法挑战。您将学习一个O(n log n)的后缀数组构建算法和一个线性时间的从后缀数组构建后缀树的算法，并将在课程的最终编程作业中实现这些算法以及克努斯-莫里斯-普拉特算法。 通过本课程，您将掌握字符串算法的关键概念和实现方法，这些知识在计算机科学和生物信息学中都具有重要应用。
Name:Suffix Trees
Description:How would you search for a longest repeat in a string in LINEAR time? In 1973, Peter Weiner came up with a surprising solution that was based on suffix trees, the key data structure in pattern matching. Computer scientists were so impressed with his algorithm that they called it the Algorithm of the Year. In this lesson, we will explore some key ideas for pattern matching that will - through a series of trials and errors - bring us to suffix trees.
Name:Burrows-Wheeler Transform and Suffix Arrays
Description:Although EXACT pattern matching with suffix trees is fast, it is not clear how to use suffix trees for APPROXIMATE pattern matching. In 1994, Michael Burrows and David Wheeler invented an ingenious algorithm for text compression that is now known as Burrows-Wheeler Transform. They knew nothing about genomics, and they could not have imagined that 15 years later their algorithm will become the workhorse of biologists searching for genomic mutations. But what text compression has to do with pattern matching??? In this lesson you will learn that the fate of an algorithm is often hard to predict – its applications may appear in a field that has nothing to do with the original plan of its inventors.
Name:Knuth–Morris–Pratt Algorithm
Description:Congratulations, you have now learned the key pattern matching concepts: tries, suffix trees, suffix arrays and even the Burrows-Wheeler transform! However, some of the results Pavel mentioned remain mysterious: e.g., how can we perform exact pattern matching in O(|Text|) time rather than in O(|Text|*|Pattern|) time as in the naïve brute force algorithm? How can it be that matching a 1000-nucleotide pattern against the human genome is nearly as fast as matching a 3-nucleotide pattern??? Also, even though Pavel showed how to quickly construct the suffix array given the suffix tree, he has not revealed the magic behind the fast algorithms for the suffix tree construction!In this module, Miсhael will address some algorithmic challenges that Pavel tried to hide from you :) such as the Knuth-Morris-Pratt algorithm for exact pattern matching and more efficient algorithms for suffix tree and suffix array construction.
Name:Constructing Suffix Arrays and Suffix Trees
Description: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.
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. In this online course you will learn key pattern matching concepts: tries, suffix trees, suffix arrays and even the Burrows-Wheeler transform.
