1

I get the basic gist of edit distance, but there's a part in one of the walkthrough videos for pset6/similarities which I don't understand.

https://www.youtube.com/watch?list=PLhQjrBD2T381-bOArPXzvlXpovpdBhrZ3&time_continue=367&v=YTO92oVoYwA

At 6:08:

He's trying to figure out the edit distance from converting 'C' to 'A'. First he looks one square from the top (i.e. going from ' ' to 'A') which is 1,I.

Then using 1,I he computes 'C' to 'A' with 2,D.

But question is, how is the last operation a D?

If you go from ' ' to 'A', which is 1,I, and then 'A' to 'C', then wouldn't the computation be 2,S with the last operation being a substituion (of 'A' into 'C') instead of a deletion?

Please help me understand how this is a deletion instead of a substitution.

Improve this question
1

1 Answer 1

Reset to default
0

There are three ways to get there: 2,D (cat->acat->aat), 2,I (cat->at->aat), 1,S (cat->aat) (a substitution here costs the same as an insertion or deletion, but it's relative to the left upper neighbour, with the upper left corner having an associated cost of 0).

A substitution advances both indices at once, in the source and in the target.

The algorithm will compare all three (and in the video, all three are shown), and keep the one with the lowest cost associated, here 1,S.

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .