Given two strings x and y over the alphabet ? one defines the edit-distance ed(x

Question

Given two strings x and y over the alphabet ? one defines the edit-distance ed(x,y) as the minimum number of substitutions, insertions and deletions of characters required to transform x into y.

If m=max(len(x),len(y)) then padding with appropriate zeroes on the smaller string one can define x and y as both being elements of ?m. Now both x and y are vertices of the cube ?m.

Now isn't ed(x,y) the shortest distance between x and y in this cube graph? Why isn't edit distance found by finding shortest paths in this cube?

Explanation / Answer

Consider the two strings 01010101 and 10101010. They have distance 8 on the cube but their edit distance is 2.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.