Problem Detail: 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.
Asked By : ProbablySomeIdiot
Answered By : Raphael
Given two strings $v,w in Sigma^*$ with $m = |v| geq |w| = n$ (w.l.o.g.), align them like so: $qquaddisplaystylebegin{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 $qquaddisplaystyle 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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/23382
