Edit Distance

Question 1

What is the minimum edit distance?

Answer 1

Given two strings. How “similar” are they?

The minimum edit distance is the minimum number of editing operations needed to transform one string to another.

Question 2

Uses of the minimum edit distance

Answer 2

Given two strings, how “similar” are they to each other?

• Correcting spelling errors.
• Finding morphological relationships.
• Bioinformatics.

Question 3

Possible operations for the minimum edit distance

Answer 3

Deletion, Insertion, Substitution.

Substitution is the same as a deletion + insertion

Question 4

What is the name of the minimum distance between two strings if substitutions has a cost of 2?

Answer 4

The Levenshtein distance

Question 5

How is minimum edit distance solved?

Answer 5

Dynamic Programming

Question 6

What is Dynamic Programming?

Answer 6

Solving sub-problems and combining these solutions to solve the overall problem

Question 7

What is the “alignment” between two strings?

What does it mean to find the “best alignment”

Answer 7

The alignment of the individual chars of two different strings (including empty spaces). For example, the alignment of “STOP” and “TOP” could S-d-_, T-|-T, O-|-O, P-|-P, where d is a deletion and | is “keep the same”

Finding the minimum edit distance is finding the best alignment.