String similarity problem

Question

We are given two strings $x=x_1,x_2,x_3,\ldots,x_m$ and $y=y_1,y_2,y_3,\ldots,y_n$ over some finite alphabet. We consider the problem of converting $x$ to $y$. Using the following operations:

1.Substitution: replace one symbol by another one.

2.Insertion: inserts one symbol

3.Deletion: delete one symbol.

For example, if $x$="logarithm" and $y$="algorithm", we convert $x$ to $y$ in the following way:

1. start with "logarithm"

2. inserting "a"at the front gives "alogarithm".

3. deleting "o"gives "algarithm"

4. replacing the second "a"by "o"gives "algorithm".

The similarity problem between the string $x$ and $y$ is defined to be the minimum number of operations needed to convert $x$ to $y$.

For example, the similarity between $x$="logarithm" and $y$="algorithm" is 3, because $x$ can be converted to $y$ using three operations. If the string $x$ has length $m$ and the string $y$ is empty, then the similarity between $x$ and $y$ is similar to $m$.

Give a dynamic programming algorithm (in pseudocode) that computes, in $\mathcal o(mn)$ time, the similarity between the string $x$ and $y$.

It is as the edit distance problem but there is the corresponding minimization problem problem where we measure similarity instead of distance .

Answer 1

Just like @Hendrik mention all you need to do is calculate Levenshtein distance which does exactly what you need.

Levenshtein distance can be expressed in following formulae $$ \mbox{lev}_{a,b}(i, j) = \begin{cases} \max(i,j) &, \mbox{if } \min(i,j) = 0 \\ \min \begin{cases} \mbox{lev}_{a,b}(i-1,j) +1 \\ \mbox{lev}_{a,b}(i, j-1)+1 \\ \mbox{lev}_{a,b}(i-1,j-1) +[a_i \neq b_i] \end{cases} &, \mbox{else} \end{cases} $$ Where $a, b$ are compared strings, $i, j$ are strings length and $[a_i \neq b_i]$ is $1$ iff $a_i \neq b_i$ and $0$ otherwise.

From this formula it can be easy translated to pseudocode.

Lev(a, b)
  len_a = len(a)
  len_b = len(b)
  cost = 0

  if(a[0] != b[0])
    cost = 1

  if (len_a == 0 or len_b == 0)
    return max(len_a, len_b)
  return min(Lev(a[1..len_a-1], b) + 1,
             Lev(a, b[1..len_b-1]) + 1,
             Lev(a[1..len_a-1], b[1..len_b-1]) + cost)

However there is small problem with this solution, its running time is $\mathcal O(nm)$ and you requested $\mathcal o(nm)$ so I hope you just made a typo.

You can also calculate this distance online using this website.