How do I compute the edit distance between two words in which substitution is not allowed?

The allowed operations include insertion (with cost 1) and deletion (with cost 1), but not substitution.

How is this supposed to be computed without substitution?


You can use the same dynamic programming algorithm as the one for the Levenshtein distance with a bit of modifications.

Let $u=u_1…u_n$ and $v=v_1…v_m$ be two words. We want to build a $(n+1)\times(m+1)$ matrix $M$ such that for $0\leq i\leq n$ and $0\leq j \leq m$, $M[i][j]$ is the edit distance between $u_1…u_i$ (or $\varepsilon$ if $i = 0$) and $v_1…v_j$. The answer is then $M[n][m]$.

Now note that for $0< i\leq n$ and $0< j \leq m$:

  • if $u_i = v_j$, then $M[i][j] = \min\left\{\begin{array}{rl}M[i-1][j]+1 & (\text{deletion of }u_i)\\M[i][j-1]+1&(\text{insertion of }v_j)\\M[i-1][j-1] & (\text{no modification})\end{array}\right.$
  • otherwise, $M[i][j] = \min\left\{\begin{array}{rl}M[i-1][j]+1 & (\text{deletion of }u_i)\\M[i][j-1]+1&(\text{insertion of }v_j)\end{array}\right.$

This is a straighforward modification of the classical dynamic programming algorithm.

Let the first string be $s = s_1 s_2 \dots s_n$ and the second string be $t = t_1 t_2 \dots t_m$. In the dynamic programming algorithm you define $D[i][j]$ as the edit distance between $s_1 s_2 \dots s_i$ and $t_1 t_2 \dots t_j$. As a consequence, the edit distance between $s$ and $t$ will be $D[n][m]$.

The bases cases are $D[0][j]=j$ and $D[i][0]=i$ (for any $i = 0, \dots, n$ and $j=0, \dots, m$), and the recursive formula (for $i>0$ and $j>0$) is:

$$ D[i][j] = \min \begin{cases} 1 + D[i-1][j] & \mbox{ deletion of $s_i$};\\ 1 + D[i][j-1] & \mbox{ insertion of $t_j$};\\ 1_{s_i \neq t_j} + D[i-1][j-1] & \mbox{ substitution of $s_i$ with $t_j$}. \end{cases}, $$ where $1_{s_i \neq t_j}$ is $1$ if $s_i \neq t_j$ and $0$ otherwise.

You can simply modify the above formula by not contemplating the last case when $s_i \neq t_j$, i.e.: $$D[i][j] = \min \begin{cases} 1 + D[i-1][j] \\ 1 + D[i][j-1] \\ D[i-1][j-1] & \mbox{only if $s_i = t_j$}. \end{cases} $$

  • $\begingroup$ You should still need to consider the case where $s_i = t_j$. $\endgroup$
    – Nathaniel
    May 16 at 11:30
  • $\begingroup$ @Nathaniel. Thanks! $\endgroup$
    – Steven
    May 16 at 11:33

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.