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?


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

  • $\begingroup$ Why is the edit distance 2 here? $\endgroup$ – user6818 May 17 '15 at 20:43
  • $\begingroup$ Because you allow insertions and deletions. $\endgroup$ – André Souza Lemos May 17 '15 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 '15 at 20:48
  • $\begingroup$ So is there any mathematical notion of distance which corresponds to this notion of "edit distance" ? $\endgroup$ – user6818 May 17 '15 at 20:48
  • $\begingroup$ That is a new question... or a different version of your question. $\endgroup$ – André Souza Lemos May 17 '15 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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