# Compute the edit distance between two words in which substitution is not allowed

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?

## 2 Answers

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}$$

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