# 字符串处理和模式匹配算法

## String Processing and Pattern Matching Algorithms

Learn about pattern matching and string processing algorithms and how they apply to interesting applications.

501 次查看

edX
• 完成时间大约为 4
• 中级
• 英语

### 你将学到什么

Key ideas for pattern matching and suffix trees

Suffix arrays

Burrows-Wheeler Transform for compression

Applications of string algorithms in bioinformatics

### 课程概况

The world and internet are full of textual information. We search for information using textual queries and read websites, books and e-mails.

These are all strings from a computer science point of view. To make sense of all this 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 course, part of the Algorithms and Data Structures MicroMasters program, you will learn about:

suffix trees;
suffix arrays;
how other brilliant algorithmic ideas help doctors to find differences between genomes;
power lightning-fast Internet searches.

### 课程大纲

Weeks 1 and 2: Suffix Trees 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.
Week 3 and 4: Burrows-Wheeler Transform and Suffix Arrays 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.

### 预备知识

Basic knowledge of at least one programming language. Successful completion of the Algorithmic Designs and Techniques and Data Structures Fundamentals courses.

Apple 广告
##### 声明：MOOC中国十分重视知识产权问题，我们发布之课程均源自下列机构，版权均归其所有，本站仅作报道收录并尊重其著作权益。感谢他们对MOOC事业做出的贡献！
• Coursera
• edX
• OpenLearning
• FutureLearn
• iversity
• Udacity
• NovoEd
• Canvas
• Open2Study
• ewant
• FUN
• IOC-Athlete-MOOC
• World-Science-U
• CourseSites
• opencourseworld
• ShareCourse
• gacco