When a spell checker encounters a possible misspelling, it looks in its dictionary for other words that are close by. What is the appropriate notion of closeness in this case?
\n A natural measure of the distance between two strings is the extent to which they can be aligned, or matched up. Technically, an alignment is simply a way of writing the strings one above the other. For instance, here are two possible alignments of SNOWY and SUNNY:<\/p>\n

S _ N O W Y
\nS U N N _ Y
\nCost: 3<\/p>\n

_ S N O W _ Y
\nS U N _ _ N Y
\ncost: 5<\/p>\n

The edit distance between two strings is the cost of their best possible alignment. Do you see that there is no better alignment of SNOWY and SUNNY than the one shown here with a cost of 3?<\/p>\n

Edit distance is so named because it can also be thought of as the minimum number of
\nedits- insertions, deletions, and substitutions of characters-needed to transform the first
\nstring into the second. For instance, the alignment shown on the left corresponds to three
\nedits: insert U, substitute O ! N, and delete W.<\/p>\n

When solving a problem by dynamic programming, the most crucial question is, What are the
\nsubproblems? It is an easy matter to write down the algorithm: iteratively solve one subproblem after the other, in order of increasing size.
\nOur goal is to fnd the edit distance between two strings x[1….m] and y[1….n].<\/p>\n

Let, an example
\nE X P O T E N T I A L
\nP O L Y N O M I A L<\/p>\n

we have to find the minimum number of operation to convert them from one to another.
\nFor this to work, we need to somehow express E(i; j) in terms of smaller subproblems.
\nLet’s see-what do we know about the best alignment between x[1…..i] and y[1….j]? Well, its
\nrightmost column can only be one of three things:
\n x[i] or _ or x[i]
\n _ y[j] y[j]<\/p>\n

But this is exactly the subproblem E(i-1; j)! We seem to be getting somewhere. In the second case, also with cost 1, we still need to align x[1….i] with y[1….j-1]. This is again another subproblem, E(i; j-1). And in the final case, which either costs 1 (if x[i] != y[j]) or 0 (if x[i] = y[j]), what’s left is the subproblem E(i-1;j-1). In short, we have expressed E(i; j) in terms of three smaller subproblems E(i-1; j), E(i; j-1), E(i-1;j-1). We have no idea which of them is the right one, so we need to try them all and pick the best:
\n E(i; j) = min{1 + E(i – 1; j); 1 + E(i; j – 1); diff(i; j) + E(i – 1; j – 1)};
\nwhere for convenience diff(i; j) is defined to be 0 if x[i] = y[j] and 1 otherwise.<\/p>\n

For instance, in computing the edit distance between EXPONENTIAL and POLYNOMIAL,
\nsubproblem E(4; 3) corresponds to the prefixes EXPO and POL. The rightmost column of their
\nbest alignment must be one of the following:
\nO _ O
\n_ L L<\/p>\n

Thus, E(4; 3) = min{1 + E(3; 3); 1 + E(4; 2); 1 + E(3; 2)}.<\/p>\n

So,the psudocode:
\nHere, m is the number of letters in POLYNOMIAL and n is the number of EXPONENTIAL
\n[code]
\nfor i = 0; 1; 2; : : : ;m:
\nE(i; 0) = i
\nfor j = 1; 2; : : : ; n:
\nE(0; j) = j
\nfor i = 1; 2; : : : ;m:
\nfor j = 1; 2; : : : ; n:
\nE(i; j) = min{E(i – 1; j) + 1;E(i; j – 1) + 1;E(i – 1; j – 1) + diff(i; j)}
\nreturn E(m; n)
\n[\/code]<\/p>\n

And in our example, the edit distance turns out to be 6:
\nE X P O N E N _ T I A L
\n_ _ P O L Y N O M I A L<\/p>\n","protected":false},"excerpt":{"rendered":"

When a spell checker encounters a possible misspelling, it looks in its dictionary for other words that are close by. What is the appropriate notion of closeness in this case? A natural measure of the distance between two strings is the extent to which they can be aligned, or matched up. Technically, an alignment is … <\/p>\n

Continue reading “Edit Distance”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0},"categories":[14],"tags":[],"_links":{"self":[{"href":"http:\/\/blog.ujjal.net\/index.php?rest_route=\/wp\/v2\/posts\/12"}],"collection":[{"href":"http:\/\/blog.ujjal.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/blog.ujjal.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/blog.ujjal.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/blog.ujjal.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=12"}],"version-history":[{"count":0,"href":"http:\/\/blog.ujjal.net\/index.php?rest_route=\/wp\/v2\/posts\/12\/revisions"}],"wp:attachment":[{"href":"http:\/\/blog.ujjal.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=12"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/blog.ujjal.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=12"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/blog.ujjal.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=12"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}