比较字符串与容差

• Z时代
• 2024-01-10
• 分类：问答

我正在寻找一种将字符串与字符串数组进行比较的方法。进行精确搜索当然很容易，但是我希望我的程序容忍拼写错误，字符串的缺失部分等等。

是否存在可以执行此类搜索的某种框架？我想到的是，搜索算法将按匹配百分比或类似的结果返回一些结果顺序。

回答：

您可以使用Levenshtein距离算法。

“两个字符串之间的Levenshtein距离定义为将一个字符串转换为另一个字符串所需的最小编辑次数，允许的编辑操作是单个字符的插入，删除或替换。”

-Wikipedia.com

这是来自dotnetperls.com：

using System;
/// <summary>
/// Contains approximate string matching
/// </summary>
static class LevenshteinDistance
{
    /// <summary>
    /// Compute the distance between two strings.
    /// </summary>
    public static int Compute(string s, string t)
    {
        int n = s.Length;
        int m = t.Length;
        int[,] d = new int[n + 1, m + 1];
        // Step 1
        if (n == 0)
        {
            return m;
        }
        if (m == 0)
        {
            return n;
        }
        // Step 2
        for (int i = 0; i <= n; d[i, 0] = i++)
        {
        }
        for (int j = 0; j <= m; d[0, j] = j++)
        {
        }
        // Step 3
        for (int i = 1; i <= n; i++)
        {
            //Step 4
            for (int j = 1; j <= m; j++)
            {
                // Step 5
                int cost = (t[j - 1] == s[i - 1]) ? 0 : 1;
                // Step 6
                d[i, j] = Math.Min(
                    Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
                    d[i - 1, j - 1] + cost);
            }
        }
        // Step 7
        return d[n, m];
    }
}
class Program
{
    static void Main()
    {
        Console.WriteLine(LevenshteinDistance.Compute("aunt", "ant"));
        Console.WriteLine(LevenshteinDistance.Compute("Sam", "Samantha"));
        Console.WriteLine(LevenshteinDistance.Compute("flomax", "volmax"));
    }
}

实际上，您可能更喜欢使用Damerau-

Levenshtein距离算法，该算法还允许转置字符，这是数据输入中常见的人为错误。您可以在这里找到它的C＃实现。

以上是 比较字符串与容差 的全部内容， 来源链接： utcz.com/qa/414243.html