寻求优于莱文斯坦距离的模糊搜索匹配度量算法

传统Levenshtein距离的局限性 #

Levenshtein距离常被用作模糊搜索的标准度量算法，但实际应用中存在明显缺陷。例如当查询词为abc，目标字符串为xyz和abc123456时，传统Levenshtein距离计算得出xyz的距离值更小，但实际上abc123456包含查询词，才是更优的匹配结果。因此我们需要能在目标字符串中定位与查询词最接近子串的度量算法。

GPT提出的滑动窗口改进方案 #

GPT给出一种改进思路：通过将短字符串沿长字符串滑动，计算所有等长子串的最小Levenshtein距离，代码实现如下：

public static int SubstringAwareLevenshtein(string a, string b)
{
    int minDist = int.MaxValue;

    // Compare a with all substrings of b
    for (int i = 0; i <= b.Length - a.Length; i++)
    {
        string sub = b.Substring(i, a.Length);
        int dist = ComputeLevenshteinDistance(a, sub);

        if (dist < minDist)
            minDist = dist;
    }

    // Compare b with all substrings of a
    for (int i = 0; i <= a.Length - b.Length; i++)
    {
        string sub = a.Substring(i, b.Length);
        int dist = ComputeLevenshteinDistance(b, sub);

        if (dist < minDist)
            minDist = dist;
    }

    return minDist;
}

该算法虽提升了匹配效果，但存在两个问题：一是无法保证最优匹配的子串长度与查询词一致；二是因多次调用Levenshtein算法，性能表现更差。

未完成的改进思路及待解决问题 #

我提出了另一种改进方向：先定位目标字符串中包含查询词所有字符的子串，再计算该子串与查询词的Levenshtein距离，代码如下：

public int ComputeDistance(string p, string t)
{
    if (p.Length > t.Length)
    {
        var x = p;
        p = t;
        t = x;
    }

    var d = 0;

    var min = int.MaxValue;
    var max = int.MinValue;

    for (int i = 0; i < p.Length; i++)
    {
        var j = t.IndexOf(p[i]);

        if (j != -1)
        {
            if (j < min)
                min = j;

            if (j > max)
                max = j;
        } 
        else
        {
            // Not sure what to do here
        }
    }

    return ComputeLevenshteinDistance(t.Substring(min, max - min), p);
}

但该思路存在未解决的问题：当查询词中的字符在目标字符串中不存在时，无法妥善处理；若直接添加惩罚项，会导致算法不再是合格的度量函数。

内容的提问来源于stack exchange，提问作者Mightywill