2
$\begingroup$

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

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

Now isn't $\text{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?

$\endgroup$

1 Answer 1

4
$\begingroup$

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

$\endgroup$
12
  • $\begingroup$ Why is the edit distance 2 here? $\endgroup$
    – user6818
    May 17, 2015 at 20:43
  • $\begingroup$ Because you allow insertions and deletions. $\endgroup$ May 17, 2015 at 20:44
  • $\begingroup$ Oh okay - I understand - you want to insert a 1 at the beginning and delete the last 1. $\endgroup$
    – user6818
    May 17, 2015 at 20:48
  • $\begingroup$ So is there any mathematical notion of distance which corresponds to this notion of "edit distance" ? $\endgroup$
    – user6818
    May 17, 2015 at 20:48
  • $\begingroup$ That is a new question... or a different version of your question. $\endgroup$ May 17, 2015 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.