用Damerau-Levenshtein编辑距离算法检测错误

Question

我正在创建一个拼写校正工具，并希望用Bayes定理实现一个噪声通道。为了做到这一点，我需要计算概率P(X=W)，其中X是给定的(拼错的)单词，W是可能的更正。概率是通过从混淆矩阵中得到一个值来给出的，这取决于是否知道发生了哪种类型的错误，这意味着如果例如X= "egh“和W= "egg”，那么编辑距离将为1，而该错误将是发生在字符2上的替换错误。

我试图找到一种方法来获得错误“类型”以及它发生的字符，但似乎无法使它发挥作用。每当检测到错误时，我都尝试创建一个TreeMap并插入i/j值，但是它没有工作。

我可能假设只有一个错误，这意味着编辑距离正好是1。

这是我的密码：

public static int DLD(String s1, String s2) {
    if (s1 == null || s2 == null) {  // Invalid input
        return -1;
    }

    if (s1.equals(s2)) {  // No distance to compute
        return 0;
    }

    // The max possible distance
    int inf = s1.length() + s2.length();

    // Create and initialize the character array indices
    HashMap<Character, Integer> da = new HashMap<>();
    for (int i = 0; i < s1.length(); ++i) {
        da.put(s1.charAt(i), 0);
    }
    for (int j = 0; j < s2.length(); ++j) {
        da.put(s2.charAt(j), 0);
    }

    // Create the distance matrix H[0 .. s1.length+1][0 .. s2.length+1]
    int[][] distances = new int[s1.length() + 2][s2.length() + 2];

    // initialize the left and top edges of H
    for (int i = 0; i <= s1.length(); ++i) {
        distances[i + 1][0] = inf;
        distances[i + 1][1] = i;
    }

    for (int j = 0; j <= s2.length(); ++j) {
        distances[0][j + 1] = inf;
        distances[1][j + 1] = j;

    }

    // fill in the distance matrix H
    // look at each character in s1
    for (int i = 1; i <= s1.length(); ++i) {
        int db = 0;

        // look at each character in s2
        for (int j = 1; j <= s2.length(); ++j) {
            int i1 = da.get(s2.charAt(j - 1));
            int j1 = db;

            int cost = 1;
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                cost = 0;
                db = j;
            }

            distances[i + 1][j + 1] = min(
                    distances[i][j] + cost, // substitution
                    distances[i + 1][j] + 1, // insertion
                    distances[i][j + 1] + 1, // deletion
                    distances[i1][j1] + (i - i1 - 1) + 1 + (j - j1 - 1));

        }

        da.put(s1.charAt(i - 1), i);
    }

    return distances[s1.length() + 1][s2.length() + 1];
}

任何解决这一问题的暗示/方向都将不胜感激。

谢谢!

编辑1:，我想出了点什么，虽然我不能百分之百肯定，但它似乎正在起作用。我将使用min()方法的代码段替换为：

int sub = distances[i][j] + cost;
int ins = distances[i + 1][j] + 1;
int del = distances[i][j + 1] + 1;
int trans = distances[i1][j1] + (i - i1 - 1) + 1 + (j - j1 - 1);

distances[i + 1][j + 1] = min(sub, ins, del, trans);

if ((distances[i][j] == 0 || distances[i - 1][j] == 0 || 
     distances[i][j - 1] == 0 || distances[i + 1][j + 1] == trans) &&
                    distances[i + 1][j + 1] == 1) {
                
    TreeMap<String, Integer> error = mappingTermAndError.getOrDefault(s2, null);
    if (error != null) {
        error.clear();
    } else {
        error = new TreeMap<>();
    }

    if (distances[i + 1][j + 1] == trans) {
        error.put("trans", i - 2);

    } else if (distances[i + 1][j + 1] == del) {
        error.put("del", i - 1);

    } else if (distances[i + 1][j + 1] == ins) {
        error.put("ins", i - 1);

    } else {  // distances[i + 1][j + 1] == sub
        error.put("sub", i - 1);
    }
    mappingTermAndError.put(s2, error);
}

它主要做的是得到每个错误类型的值，然后计算最小值。如果新的最小值为1(这是第一个错误)，并且距离矩阵中的前一个单元格为0(意味着有一条路径没有导致该点的错误)，或者如果该错误是移位的(我们只有在我们已经有错误之后才能知道这一点)，那么我就用新的错误替换以前注册的错误，并得到与错误所对应的字符对应的'i‘。

我知道这个解决方案很难看，而且可能不太有效，所以如果有人对如何改进有任何想法的话，那就太好了。

Answer 1

所涉及的错误类型和字符必须存储在某个地方。您可以将它们放在单独的数据结构中，也可以将它们封装在对象中。

下面是使用对象的样子。为了简单起见，我只实现Levenshtein距离，但我相信您可以很容易地将该技术应用于Damerau-Levenshtein。

首先，您需要定义一个类来封装有关编辑的信息:成本、父级和任何额外的信息，如类型(替换、插入、删除)或所涉及的字符。为了保持简单，我为这个额外的信息保留了一个名为" type“的字符串，但是您需要为错误类型、字符索引等添加单独的字段。您甚至可能希望使用继承来创建不同行为的编辑的不同子类型。

class Edit implements Comparable<Edit> {
    int cost;
    Edit parent;
    String type;

    public Edit() {
        // create a "start" node with no parent and zero cost
    }

    public Edit(String type, Edit parent, int cost) {
        this.type = type;
        this.cost = parent.cost + cost;
        this.parent = parent;
    }

    @Override
    public int compareTo(Edit o) {
        return Integer.compare(this.cost, o.cost);
    }

    @Override
    public String toString() {
        return type;
    }
}

然后，您将使用这个类，而不是仅仅使用int作为距离表。在0,0处有一个特殊的开始节点，没有父节点。在所有其他点上，您根据到达该节点所需的最小成本选择一个具有一个父节点或另一个父节点的节点。为了更灵活，让我们将矩阵的构建从editDistance方法中分离出来：

Edit[][] buildMatrix(String s1, String s2) {
    Edit[][] distance = new Edit[s1.length() + 1][s2.length() + 1];

    distance[0][0] = new Edit();
    for (int i = 1; i <= s1.length(); i++) {
        distance[i][0] = new Edit("-" + s1.charAt(i - 1), distance[i - 1][0], 1);
    }
    for (int j = 1; j <= s2.length(); j++) {
        distance[0][j] = new Edit("+" + s2.charAt(j - 1), distance[0][j - 1], 1);
    }

    for (int i = 1; i <= s1.length(); i++) {
        for (int j = 1; j <= s2.length(); j++) {
            int replaceCost = s1.charAt(i - 1) == s2.charAt(j - 1) ? 0 : 1;
            distance[i][j] = Collections.min(List.of(
                // replace or same
                new Edit(s1.charAt(i - 1) + "/" + s2.charAt(j - 1), distance[i - 1][j - 1], replaceCost),
                // delete
                new Edit("-" + s1.charAt(i - 1), distance[i - 1][j], 1),
                // insert
                new Edit("+" + s2.charAt(j - 1), distance[i][j - 1], 1)));
        }
    }

    return distance;
}

然后，“编辑距离”函数只需计算最后一个节点的成本：

int editDistance(String s1, String s2) {
    Edit[][] distance = buildMatrix(s1, s2);
    return distance[s1.length()][s2.length()].cost;
}

但是，由于有了“父”指针，您还可以轻松地构造将一个字符串更改为另一个字符串所需的编辑列表，也称为"diff"：

List<Edit> diff(String s1, String s2) {
    Edit[][] distance = buildMatrix(s1, s2);
    List<Edit> diff = new ArrayList<>();
    Edit edit = distance[s1.length()][s2.length()];
    while (edit != distance[0][0]) {
        diff.add(edit);
        edit = edit.parent;
    }
    Collections.reverse(diff);
    return diff;
}