Explore
For Enterprise
Join for Free
Log In

Amazon Web Services
New! AWS Computer Vision: Getting Started with GluonCV
Learn to combine neural network building blocks into complete computer vision models.
University of London
Bachelor of Computer Science
This bachelor's degree offers 7 concentrations so students can pick where their career goes

Explorez l'intégralité de Coursera

Parcourir
Meilleurs cours
For Enterprise
Connexion
Inscrivez-vous gratuitement

Computing Edit Distance

Loading...

Algorithmic Toolbox

Université de Californie à San Diego

4.7 (5,706 évaluations) | 170K étudiants inscrits

Cours 1 de 6 dans Structures de données et algorithmes Spécialisation

S'inscrire gratuitement

The course covers basic algorithmic techniques and ideas for computational problems arising frequently in practical applications: sorting and searching, divide and conquer, greedy algorithms, dynamic programming. We will learn a lot of theory: how to sort data and how it helps for searching; how to break a large problem into pieces and solve them recursively; when it makes sense to proceed greedily; how dynamic programming is used in genomic studies. You will practice solving computational problems, designing new algorithms, and implementing solutions efficiently (so that they run in less than a second). Do you have technical problems? Write to us: coursera@hse.ru

Visualiser le programme de cours

Compétences que vous apprendrez

Dynamic Programming, Debugging, Software Testing, Algorithms, Computer Programming

Avis

4.7 (5,706 évaluations)

5 stars
4,249 ratings
4 stars
1,158 ratings
3 stars
202 ratings
2 stars
43 ratings
1 star
54 ratings

PR

Feb 10, 2019

The course is perfectly designed. The perfect start for those who start with data structures and algorithms. The Dynamic programming was a little bit tough but overall course is perfectly designed

RS

Dec 23, 2018

This course is just awesome and outstanding in every term. Teachers are very good at explaining even the toughest of problems and really helped throughout the course, i enjoyed and leaned a lot.

À partir de la leçon

Dynamic Programming 1

In this final module of the course you will learn about the powerful algorithmic technique for solving many optimization problems called Dynamic Programming. It turned out that dynamic programming can solve many problems that evade all attempts to solve them using greedy or divide-and-conquer strategy. There are countless applications of dynamic programming in practice: from maximizing the advertisement revenue of a TV station, to search for similar Internet pages, to gene finding (the problem where biologists need to find the minimum number of mutations to transform one gene into another). You will learn how the same idea helps to automatically make spelling corrections and to show the differences between two versions of the same text.

The Alignment Game8:39

Computing Edit Distance6:37

Reconstructing an Optimal Alignment4:55

Enseigné par

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Neil Rhodes
Adjunct Faculty
Pavel Pevzner
Professor
Daniel M Kane
Assistant Professor

Essayer le cours pour Gratuit USD

Transcription

Let's now see how dynamic programming algorithm solves the edit distance problem. We start by considering two strings, A of length n and B of length m and we will ask the question question what is an optimal alignment of an i-prefix of A, which is the first i symbols of A, and the j-prefix of B which are the first j symbols only. The last column of an optimal alignment is either an insertion or a deletion or a mismatch, or a match. And please notice that if we remove the last column from the optimal alignment of the strings, what is left is an optimal alignment of the corresponding two prefixes. And we can adjust the score of the optimal alignment for i prefix and j prefix by adding plus 1 in the case of insertion, plus 1 in the case of deletion, plus 1 in the case of mismatch and adding nothing in the case of match. Let's denote D (i, j) to be the edit distance between an i-prefix and a j-prefix. And in this case, this figure at the top of the slide illustrates the following recurrency. D(i,j) equal to the minimum of the following four values: D(i,j-1)+1, D(i-1,j)+1, D(i-1,j-1)+1, in the case the last two symbols in the i prefix of A and j prefix of B are different. And D(i- 1, j- 1), if the last symbols in i and j prefix are the same. Our goal now is to compute the edit distance D, i, j between all i prefixes of string A and all j prefixes of string B. In the case of string editing and distance we will construct eight by nine grid and our goal is to compute all edit distances D(i, j) corresponding to all nodes in this grid. For example, for i and j equal to four and four. How will we compute the corresponding distance D(i, j)? Let's start by filling distances D(i, 0) in the first column of this matrix. It is easy because indeed we are comparing an i-prefix of string A against a 0-prefix of string D and therefore this edit distance for i-prefix will be equal to i. That's what's shown here, similarly we can easily fill the first row in this matrix. And now let's try to compute what will be the distance D(1,1) corresponding to comparison of string consisting of single symbol E, with a string consisting of single symbol D, there are three possible ways to arrive to the node (1, 1): from the nodes (0, 0), (0, 1), and (1, 0). Which one should be the way we will select to find the optimal edit distance. According to the previous recurrency, we should select the one of three directions that gives minimal value for D(i, j), which is minimum of 2, 2, and 1 and therefore we arrive to node (1, 1) by diagonal edge. Let's keep this in memory that the right direction to arrive at node (1, 1) was the diagonal direction. We will now try to compute the edit distance for the next node in the matrix. And in this case D(2,1) is equal to minimum D(2,0) + 1, D(1,1) + 1 and D(1,0) of each tells us that's the optimal way to arrive to this node would be again, by diagonal edge. You continue further, once again compare three values and it turn out that the best way to arrive to this node will be by vertical edge. We'll continue further and we'll fill the whole second column in the matrix. Now let's continue with the circle, what about this node? For this node D(1,2) = minimum {D(1,1) + 1, D (0,2) + 1, and D (0,1) + 1}. And it is minimum of 2, 3, and 2. In fact, there are two optimal ways to arrive to this node and in this case we show both of them by diagonal edge into this vertex and by horizontal edge of this vertex. You'll continue further and slowly but surely we will fill the whole matrix. The edit distance pseudocode implements the algorithm we just discussed. It first fills in the first column and the first row of the dynamic programming matrix and then it continues filling it up by computing the cost of moving to vertex (i, j) using insertion, deletion, or mismatch or match or in other words, exploring all possibility. Moving to the vertex i, j using vertical edge, horizontal edge, and diagonal edge. And then it finds out which of these possibilities results in the minimum edit distance.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera

À propos
Direction
Carrières
Catalogue
Certificats
Certificats MasterTrack™
Diplômes
For Enterprise
For Government
Pour le campus

Communauté

Étudiants
Partenaires
Développeurs
Testeurs bêta
Traducteurs
Blog
Blog Tech

Plus

Conditions
Confidentialité
Aide
Accessibilité
Presse
Contact
Répertoire
Filiales

Apprendre partout

Suivez-nous

© 2020 Coursera Inc. Tous droits réservés.