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

Question

有没有现成的.NET算法，能够从预定义单词列表中检测出错别字？

例如，假设我的列表中有单词"Stuff"，而有人输入了"Stuf"、"sutff"、"stff"或者"stiff"，我希望能够建议这个人"Stuff"可能是正确的单词。

我不是在谈论语法或者更多的东西，只是指一个字母丢失、替换或混淆的情况。

我的目标是防止同一个单词以不同的打法出现在列表中。大小写对我来说并不是问题，因为所有字母都是小写。

- David Brunelle

---

也许可以查看 http://stackoverflow.com/search?q=spellchecker+c# - Anthony Pegram

我想编辑这个问题的标题，但我怀疑它可能只是一种精妙的、有意的反讽。 - Justin Morgan

Soundex 可能是一种选择。 - rossum

Answer 1

这是一个经过深入研究的问题，有许多良好的算法可以解决。它们大多通过构建某种数据结构来容纳所有合法单词，并以一种能够高效地找到具有相似编辑距离的单词的方式工作。非正式地说，两个字符串之间的编辑距离是将一个字符串转换为另一个字符串所需进行的更改次数。例如，给定单词"misspell"和"mispell"，编辑距离为1（只需在单词中插入另一个's'），而"cat"和"dog"之间的编辑距离为3（替换每个字母）。

一个拼写错误的单词很可能与预期单词只有很小的编辑距离，因此，如果您可以以一种能够查询与字符串相差很小的单词的方式存储单词，那么您可以提供一个可能是用户想要输入的单词的候选列表。

一种常见的数据结构用于存储这些数据是trie，它是一种26路树形结构，每个节点存储一个单词的前缀，每个边对应于在当前前缀后添加一些字母。如果您拥有这样的结构，可以使用简单的递归树搜索找到与特定单词“接近”的单词（可能相差某个编辑距离）。在每个点上，跟踪您希望与目标单词相隔多远的编辑距离以及您已处理的错误拼写单词的程度。在每个点上，您可以按照单词中的字母跟随trie中的边，或者您可以使用一个编辑距离通过跟随trie中的不同边来插入一个新字母。

另一种经常用于此的数据结构是BK-tree，它以一种能够高效查询所有距离某个源字符串某个编辑距离的单词的方式存储字符串。这将更直接地解决您的问题，但与尝试构建BK树相比，在线资源较少。

一旦您找到了在某种编辑距离内的单词，您可能希望在向用户呈现它们之前对它们进行排序。这需要您对人们在实践中往往犯的哪些拼写错误有一些想法。常见的拼写错误包括：

- 交换，其中两个字母被交换：“thme”代替“them” - 替换，使用错误的字母： “arithmatic”代替“arithmetic” - 删除，留下一个字母：“helo”代替“hello” - 重复，其中一个字母被复制：“tommorrow”代替“tomorrow”

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

希望这可以帮助您！

- templatetypedef

Answer 2

这里有一个使用Python实现的逐步指南，可以实现您想要的内容，但也提供了C#和其他语言的实现链接。

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

- Jacob Eggers

---

这是25行Python代码，基于字典实现，正好适用于这种小规模任务！ - Francois G

Answer 3

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

- Micromega

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;
    }

- pawszo