查找由 Damerau-Levenshtein 编辑距离算法检测到的错误

Question

我正在创建一个拼写校正工具，并想用贝叶斯定理实现一个嘈杂的频道。为此，我需要计算概率 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];
}

任何 hint/direction 解决此问题的方法都将不胜感激。

谢谢！

编辑 1： 我想出了一些办法，它似乎在工作，虽然我不是 100% 确定。我将使用 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。

首先，您需要定义一个 class 来封装有关编辑的信息：成本、父级以及任何额外信息，如类型（替换、插入、删除）或涉及的字符。为了简单起见，我为这些额外信息保留了一个名为“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;
    }
}

然后你使用这个 class 而不是 int 作为距离 table。在 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;
}

但多亏了“父”指针，您还可以轻松构建将一个字符串更改为另一个字符串所需的编辑列表，也称为“差异”：

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

查找由 Damerau-Levenshtein 编辑距离算法检测到的错误

Finding which error(s) are detected by Damerau-Levenshtein edit distance algorithm

java

spell-checking

edit-distance

levenshtein-distance

damerau-levenshtein