自定义拼写检查器需求：优化NotMatching方法及拼写纠错匹配

一、改进NotMatching方法 #

原方法依赖固定差异数阈值n=3，仅能在已知差异数量时生效，现在需要修改为通用场景：当两个单词差异过大（无匹配价值）时返回true，反之返回false。

问题分析 #

原方法仅逐位比较相同位置的字符差异，忽略了插入、删除、替换等编辑操作带来的差异（例如badc和abc，原方法仅比较前3位，差异数为3，最终返回false，但实际两者的编辑距离为2，属于有匹配可能的情况）。因此改用**编辑距离（Levenshtein Distance）**衡量单词相似度，再基于单词长度设定动态阈值，更符合通用场景需求。

改进后的代码 #

public static bool NotMatching(string a, string b)
{
    // 完全相等直接返回false（匹配）
    if (a.Equals(b, StringComparison.OrdinalIgnoreCase))
        return false;

    int lenA = a.Length;
    int lenB = b.Length;

    // 计算编辑距离
    int[,] dp = new int[lenA + 1, lenB + 1];
    for (int i = 0; i <= lenA; i++) dp[i, 0] = i;
    for (int j = 0; j <= lenB; j++) dp[0, j] = j;

    for (int i = 1; i <= lenA; i++)
    {
        for (int j = 1; j <= lenB; j++)
        {
            int cost = a[i-1] == b[j-1] ? 0 : 1;
            dp[i, j] = Math.Min(Math.Min(dp[i-1, j] + 1, dp[i, j-1] + 1), dp[i-1, j-1] + cost);
        }
    }

    // 设定动态阈值：编辑距离超过较短单词长度的1/3则判定为无匹配
    int threshold = Math.Min(lenA, lenB) / 3;
    // 特殊情况：短单词（长度<=3）允许最多1个编辑差异
    if (Math.Min(lenA, lenB) <= 3)
        threshold = 1;

    return dp[lenA, lenB] > threshold;
}

说明 #

• 编辑距离：衡量将一个字符串转换为另一个字符串所需的最少单字符编辑操作（插入、删除、替换）次数。
• 动态阈值：根据单词长度调整，避免对短单词过于严格，对长单词保持合理容错度。

二、实现拼写纠错匹配 #

需求说明 #

输入两组字符串数组，为phrase中的每个单词在validWords中寻找匹配的建议单词，无匹配时输出(没有匹配建议)。

实现代码 #

public static void SpellCheck(string[] phrase, string[] validWords)
{
    foreach (string word in phrase)
    {
        List<string> suggestions = new List<string>();
        foreach (string validWord in validWords)
        {
            if (!NotMatching(word, validWord))
            {
                suggestions.Add(validWord);
            }
        }

        if (suggestions.Count == 0)
        {
            Console.WriteLine($"{word.ToLower()}: (没有匹配建议)");
        }
        else
        {
            foreach (string suggestion in suggestions)
            {
                Console.WriteLine($"{word.ToLower()}: {suggestion}");
            }
        }
    }
}

// 调用示例
public static void Main()
{
    string[] phrase = "Acetsa e un texzt excelent da tet".Split();
    string[] validWords = "acesta e un text de test".Split();
    SpellCheck(phrase, validWords);
}

输出结果 #

acetsa: acesta
e: e
un: un
texzt: text
excelent: (没有匹配建议)
da: de
tet: text
tet: test

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