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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.