Is there a basic proof that there exists some edit distance between two strings?

Title says it all pretty much. I do realize that often edit distance is defined as the minimum number of operations needed to transform one string to another, but I want something to point to that's even more general than that.

I recently saw a brain teaser that claimed that some string was connected in a network to another as "friends" given an edit distance of one. It then went on to claim that friends of friends, friends of friends of friends, etc. (with no given upper bound on the degree of separation), were also in the network of that original string. I can't see how this definition of network doesn't include every possible string, and so I think the brain teaser is ill-formed. Given sufficient edits, a string can transform to any other string, right? -- but is there a name for that observation? I think this is so fundamental as to be near-impossible to Google, but there is always the distinct possibility of me being an idiot.

• Do the strings have to be finite? If yes, then I think you are correct. Apr 3 '14 at 4:53
• I can't quite understand your question. As you comment, every two strings are connected in the graph that you describe, in other words, the graph is connected. In the same way, every two integers have a finite distance, and so you can reach one from the other by adding and subtracting 1. Also, any two points on the plane have finite distance. And so on. Apr 3 '14 at 4:56
• @YuvalFilmus I think the question is why the graph is connected. I also think the question's last sentence is accurate. :D
– Raphael
Apr 3 '14 at 6:41

Given two strings $v,w \in \Sigma^*$ with $m = |v| \geq |w| = n$ (w.l.o.g.), align them like so:

$\qquad\displaystyle\begin{array}{ccccccc} v_1 & v_2 & \dots & v_n & v_{n+1} & \dots & v_m \\ w_1 & w_2 & \dots & w_n & - & \dots & - \end{array}$

This alignment implies an edit distance of

$\qquad\displaystyle 0 \leq d_{\text{edit}}(v,w) \leq d_{\text{Ham}}(v,w[1..n]) + (m-n)$.

In particular, there is an alignment for any two strings. Note furthermore that there are only finitely many alignments of $v$ and $w$ (we forbid columns $\genfrac{}{}{0pt}{}{-}{-}$), so one with minimal score (which is the edit distance) must exist.

Hence, any two strings have finite edit distance and the graph is connected.

• Thanks for spelling it out for me! I do agree with Yuval that the graph is connected -- that's how I saw the problem at first -- but the way the problem was stated just had me second-guessing myself. Apr 3 '14 at 16:18

There is trivially an edit distance between any two strings. The worst possible case is that you delete all of the characters of the original string, and then insert all the characters of the target string.

The Wikipedia page for edit distance discusses the fact that it is a metric and also gives some upper bounds http://en.m.wikipedia.org/wiki/Edit_distance . For example LCS (longest common subsequence) which has only insertion/deletion operations is bounded by the sum of the lengths of the two strings, and Hamming distance (only substitution allowed, and defined for strings of the same length) will be bounded by the length of the string. The bounds are reached if the strings have no common letters. So yes, every two strings have a (bounded) edit distance. (The correctness of the algorithms computing minimal distances surely constitutes a proof of the existence of an edit distance for any pair of strings anyway).

Looking into the notion of metric/ metric spaces will give you the generalization you want.