c++ - 插入和替换成本不统一的 Levenshtein 距离 :

Question

我一直在尝试在 C++ 中实现一个 levenshtein 距离函数，它根据要替换或插入的字符为替换和插入赋予不同的权重。

成本是根据 qwerty 键盘上按键的距离计算的。例如，在标准的编辑距离算法中，google、hoogle、zoogle的距离是一样的； 1. 我想要的是这些不同的距离。类似于 google -> hoogle = 1，google -> zoogle = 4，hoogle -> zoogle = 5。

我关注了 Wikipedia algorithm使用矩阵进行内存并在 C++ 中实现。这是我的功能。

int levDist(string s, string t) {

    int i,j,m,n,temp,subsitutionCost, deletionCost, insertionCost, keyDist;
    deletionCost = 1;

    m = s.length();
    n = t.length();
    int d[m+1][n+1];

    for(i=0;i<=m;i++)
        d[i][0] = i;
    for(j=0;j<=n;j++)
        d[0][j] = j;

    for (j=1;j<=n;j++)
    {
        for(i=1;i<=m;i++)
        {
            // getKeyboardDist(char a, char b) gives distance b/w the two keys
            keyDist = getKeyboardDist(s[i-1],t[j-1]); 

            subsitutionCost = (s[i-1] == t[j-1]) ? 0 : keyDist;

            // this line is the one i think the problem lies in
            insertionCost = (i > j) ? getKeyboardDist(s[i-1],t[j-2]) : getKeyboardDist(s[i-2],t[j-1]);


            insertionCost = insertionCost ? insertionCost : 1;

            d[i][j] = min((d[i-1][j]   + deletionCost),
                      min((d[i][j-1]   + insertionCost),
                          (d[i-1][j-1] + subsitutionCost)));`
        }
    }
    return d[m][n];
}

我相信现在替换工作正常，但问题是插入。我不知道如何找到哪些字符来获得插入之间的距离。尤其是在字符串的开头或结尾插入的情况。

我将不胜感激，如果需要任何其他信息，请告诉我。

提前致谢。

Answer 1

您尝试做的事情对于替换是有意义的。您假设一个人试图敲击键 X 比在远处敲击物理上靠近 X 的键更容易出错。

对于插入和删除没有太大意义，因为敲击额外键(插入错误)或跳过键击(删除错误)的行为与键距离没有任何明显关系。

您可能被此处“距离”的两种不同含义误导了。 Levenshtein 距离是在插入/替换/删除操作中的字符串之间测量的。键盘距离是一种物理分离。这些是碰巧用同一个词描述的苹果和橙子。它们混合得不好。

您正在尝试确定 Levenshtein 操作的权重。键之间的物理距离为替换赋予了合理的权重。

插入和删除的权重——每个只涉及一个字符——与物理分离没有任何明显的关系。

您真正需要的是有关人们实际错误插入和删除哪些键的频率数据。您会赋予最常见的相对较低的权重和最不常见的较高权重。

@user6952491 认为重复前一个 key 可能是高频插入错误的想法有其优点，但很难将其扩展到完整的加权方案。

如果您有猜测的心情，您可以假设在键盘中间附近比在边缘更容易错误地插入一个键。假设 f 和 j 获得最低权重，而像 ~ 这样的字符被移动并且在键盘极端处获得高权重，因为你不太可能不假思索地打字的 body Action 。

我将留给您对删除进行类似的猜测。

对于一般的打字，我的猜测是键盘输入错误与拼写错误的关系至少与物理错误一样多。也就是说，人们会输入“recieve”是因为他们忘记了“i 在 e 之前，除了在 c 之后”这一规则，而不是因为 i 相对于 e 的键盘位置。

其他类型的打字，例如计算机代码，很可能有完全不同的错误模式。想起忘记的分号!那些将具有非常低的权重!

因此，我几乎可以肯定，现代拼写检查器提供的建议 Root 于机器学习算法，这些算法从过去成千上万人在类似任务中犯过的错误中得出结论，而不是基于键盘距离的简单指标.