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

Question

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?

Answer 1

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

Answer 2

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

Answer 3

According to wikipedia, deletion, insertion, and substitution can assign separate costs. We can simply set substitutions cost to deletion plus insertion, which is 2 if deletion and insertion are both 1.

Here is the java code:

public static int deleteAddEditDistance(String s1, String s2) {
    if (s1 == null) {
        return 0;
    } else if (s2 == null) {
        return 0;
    } else if (s1.equals(s2)) {
        return 0;
    } else if (s1.length() == 0) {
        return s2.length();
    } else if (s2.length() == 0) {
        return s1.length();
    } else {
        int[] v0 = new int[s2.length() + 1];
        int[] v1 = new int[s2.length() + 1];

        int i;
        for (i = 0; i < v0.length; v0[i] = i++) {
        }

        for (i = 0; i < s1.length(); ++i) {
            v1[0] = i + 1;
            for (int j = 0; j < s2.length(); ++j) {
                int sub_cost = 2; // substitute cost
                int add_cost = 1;
                int del_cost = 1;
                if (s1.charAt(i) == s2.charAt(j)) {
                    v1[j + 1] = v0[j];
                } else {
                    v1[j + 1] = Math.min(v1[j] + add_cost, Math.min(v0[j + 1] + del_cost, v0[j] + sub_cost));
                }
            }

            int[] vtemp = v0;
            v0 = v1;
            v1 = vtemp;
        }
        return v0[s2.length()];
    }
}