.NET 中检测简单拼写错误的算法

Question

是否有现有的 .NET 算法能够从预定义单词列表中检测拼写错误？

例如，假设单词“Stuff”在我的列表中，并且有人输入“Stuf”、“sutff”或“stff”或“stiff”。我希望能够向该人建议“东西”这个词可能是正确的词。

我不是在谈论任何语法问题，也不是在谈论任何可能有一个字母丢失、替换或混合的事情。

我的目标是防止在不同类型的列表中输入相同的单词。并不是说大写和小写不会对我造成问题，因为所有内容始终都是小写。

Answer 1

这是一个经过充分研究的问题，并且有许多很好的算法可以做到这一点。它们中的大多数通过构建某种数据结构来保存所有合法单词，其中具有相似的单词 可以高效地找到编辑距离。通俗地说，两个字符串之间的编辑距离是将一个字符串转换为另一个字符串所需的更改次数。例如，给定单词“misspell”和“mispell”，编辑距离为 1（只需在单词中插入另一个 's'），而“cat”和“dog”之间的编辑距离为 3（替换每个字母） 。

拼写错误的单词可能与预期的单词只有很小的编辑距离，因此，如果您可以以某种方式存储单词，对于任何字符串，您都可以查询与该字符串的编辑距离很小的单词，那么您可以可以提供用户可能表示的可能单词的候选列表。

保存此数据的一种常见数据结构是 trie，这是一种 26 路树结构，其中每个节点存储单词的前缀，每条边对应于在当前前缀上添加一些字母。如果您有这样的结构，您可以使用简单的递归树搜索来查找与特定单词“接近”（可能相距一定编辑距离）的单词。在每个点，记录您希望距目标单词多远的编辑距离以及到目前为止您已处理的拼写错误单词的数量。在每一点，您可以沿着特里树中与单词中的字母相对应的边，也可以通过沿着特里树中的不同边，用尽一个编辑距离来插入新字母。

另一种常用的数据结构是 BK-tree，它将字符串存储在一种可以有效查询距某个源字符串一定编辑距离的所有单词的方法。这会更直接地解决你的问题，尽管与尝试相比，关于如何构建 BK 树的在线资源较少。

一旦您找到了某个编辑距离内的单词，您可能希望在将它们呈现给用户之前以某种方式对它们进行排名。这要求您了解人们在实践中容易犯什么样的打字错误。常见的拼写错误包括

• 换位，其中两个字母被交换：“thme”而不是“them”
• 替换，其中使用了错误的字母：“arithmatic”而不是“arithmetic”
• 删除，其中一个字母被遗漏：“helo”而不是“hello”
• 重复，其中一个字母重复：“tommorrow”而不是“tomorrow”

为了构建一个好的拼写检查器，理想情况下您应该拥有与每种类型的错误相关的某种概率。这样，当您获得可能的更正列表时，您可以将它们从最可能到最不可能进行排名。

希望这有帮助！

Answer 2

这里有一个很好的逐步实现您正在寻找的在 python 中实现的内容，但也有指向 C# 和其他语言实现的链接。

http://norvig.com/spell- Correct.html

Answer 3

也许您想寻找三元组搜索？三元组搜索需要创建输入的 3 个字母的所有可能性，并在匹配中查找相似的字符串。

Answer 4

发布我在 C# 中的实现，允许长度 >= 2 的字符串。
它检查 2 个单词是否匹配，忽略换位、替换、删除（对于删除后长度 >=2 的单词有效）和 重复（允许多次）。

public bool CheckWordsSameWithTypo(string word1, string word2)
    {
        if (word1.Length < 2 || word2.Length < 2) return false;
        
        //transposition "thme" instead of "them"        
        bool matchWithTrans = false;
        #region transLogic
        var transOptions1 = new List<string>();
        var transOptions2 = new List<string>();
        for (int i = 1; i < word1.Length;  i++)
        {
            var wordArr = word1.ToArray();
            char letter1 = wordArr[i -1];
            char letter2 = wordArr[i];
            wordArr[i -1] = letter2;
            wordArr[i] = letter1;
            transOptions1.Add(new string(wordArr));
        }
        for (int i = 1; i < word2.Length;  i++)
        {
            var wordArr = word2.ToArray();
            char letter1 = wordArr[i -1];
            char letter2 = wordArr[i];
            wordArr[i -1] = letter2;
            wordArr[i] = letter1;
            transOptions2.Add(new string(wordArr));
        }
        if (transOptions1.Any(p => p.Equals(word2)) || transOptions2.Any(p => p.Equals(word1))) matchWithTrans = true;
        #endregion
        
        //substitution "arithmatic" instead of "arithmetic"
        bool matchWithSubst = false;
        #region substLogic
        var substOptionPatterns1 = new List<string>();
        var substOptionPatterns2 = new List<string>();
        for (int i = 0; i < word1.Length;  i++)
        {
            var wordArr = word1.ToArray();
            wordArr[i] = '.';
            substOptionPatterns1.Add(new string(wordArr));
        }
        for (int i = 0; i < word2.Length;  i++)
        {
            var wordArr = word2.ToArray();
            wordArr[i] = '.';
            substOptionPatterns2.Add(new string(wordArr));
        }
        foreach(var patt in substOptionPatterns1)
        {
            Regex regex = new Regex(patt);
            if (regex.IsMatch(word2)) matchWithSubst = true;
        }
        foreach(var patt in substOptionPatterns2)
        {
            Regex regex = new Regex(patt);
            if (regex.IsMatch(word1)) matchWithSubst = true;
        }
        #endregion
        
        //deletion "helo" instead of "hello"
        bool matchWithDeletion = false;
        #region deletionLogic
        var delOptions1 = new List<string>();
        var delOptions2 = new List<string>();
        for (int i = 0; i < word1.Length;  i++)
        {
            delOptions1.Add(word1.Remove(i, 1));
        }
        for (int i = 0; i < word2.Length;  i++)
        {
            delOptions2.Add(word2.Remove(i, 1));
        }
        if (delOptions1.Any(p => p.Length>1 && p.Equals(word2)) || delOptions2.Any(p => p.Length>1 && p.Equals(word1))) matchWithDeletion = true;
        #endregion
        
        //repetition "tommorrow" instead of "tomorow"
        bool matchWithRepetition = false;
        #region repsLogic
        StringBuilder word1_distinctBuilder = new StringBuilder(word1.Substring(0, 1));
        for (int i = 1; i < word1.Length;  i++)
        {
            string currentLetter = word1.Substring(i, 1);
            if(!word1_distinctBuilder.ToString().Substring(word1_distinctBuilder.ToString().Length-1, 1).Equals(currentLetter))
            {
                word1_distinctBuilder.Append(currentLetter);
            }
        }
        StringBuilder word2_distinctBuilder = new StringBuilder(word2.Substring(0, 1));
        for (int i = 1; i < word2.Length;  i++)
        {
            string currentLetter = word2.Substring(i, 1);
            if(!word2_distinctBuilder.ToString().Substring(word2_distinctBuilder.ToString().Length-1, 1).Equals(currentLetter))
            {
                word2_distinctBuilder.Append(currentLetter);
            }
        }
        matchWithRepetition = word1_distinctBuilder.ToString().Equals(word2_distinctBuilder.ToString());
        #endregion
        return matchWithTrans || matchWithSubst || matchWithDeletion || matchWithRepetition;
    }