一个基于贝叶斯定理的拼写校正器 (PHP, C#)

项目网站

有关此项目的更多信息，请访问 http://www.horizonideas.com/spellingdice/

引言

无论您是否是英语母语者，您都可能时不时地犯一些拼写错误。如果电脑能为您不确定的输入提供一些拼写建议，那不是很棒吗？最著名的例子应该是谷歌建议。每次您输入一些错误时，下一页都会出现“您是不是想找？XXX XXX XXX”。我们知道整个系统是基于贝叶斯网络，但它是如何实现的呢？另一方面，如果我们的网站或小型程序能包含这个强大的功能，那将是吸引人们的宝贵资产。

谷歌研究总监 Peter Norvig 揭示了谷歌建议的秘密。我相信这并不是完整的算法，但它足以让我们自己添加一些内容，并将其用于我们自己的小型程序中。

我相信他的论文比我下面的描述要好得多。您可以在以下网址找到他的论文：

此处 [英文]

此处 [中文]

此处 [日文]

此处 [俄文]

假设有人输入“Majar”，程序应该能够识别用户实际想表达的是“major”。

好的，那么它是如何工作的呢？

我们让 P(s|i) 表示在提供输入词 i 的情况下，一个建议词 s 的概率。

所以我们有 P(s|i) = P(s,i) / P(i)

P(i) 是一个随机输入字符串的概率。由于用户可以输入任何内容，因此该概率可以忽略不计。我们将其设为 1。所以我们有

P(s|i) = P(s,i) / 1 = P(s,i)

同时，

P(s,i) = P(i|s) * P(s) 所以我们有

P(s|i) = P(s,i) = P(i|s) * P(s)

其中 P(s) 是一个单词的概率。问题：我们如何定义这个数字？

答案：找任何一本书通读一遍，然后统计每个单词的出现次数。或者下载包含 5000 个最常用英语单词的 API。例如，“the”这个词的概率肯定比“tae”[治疗性动脉栓塞]高得多。

好的，那么 P(i|s) 呢？从字面上看，P(i|s) 是在提供推荐字符串的情况下，一个输入字符串的概率。但这没有意义。因此，它变成了通过计算编辑距离来确定一个建议字符串的概率。

哦，编辑距离。您不知道是什么？请阅读 http://en.wikipedia.org/wiki/Edit_distance

最著名的是 Levenshtein 距离，它是 PHP 中的一个内置函数。另一个例子是信息论中的 Hamming 距离。例如 D(01010, 10010)=2。现在您明白我说的编辑距离是什么意思了，对吗？

好的，我们继续。编辑距离越小，概率就越高。

例如，如果有人输入“hallo”，“hello”的 P(i|s) 远高于“helen”。如果单词是正确的怎么办？换句话说，如果字典中的某个单词与输入匹配。那么程序不应该返回任何建议。为了节省时间复杂度，程序应该在这里中断。

明白我说的吗？如果不明白，请再次参考他的原始文章。

好的。我们仔细看看“hallo”。程序可能会找到“Hallow”、“Mallo”（如果确实存在这样的词）和“Hello”。它们可能具有相同的 P(s)，因为我们不会看到太多人在正式写作中使用大量的“hello”。它们具有相同的编辑距离，那么它们应该按字母顺序排列吗？不！绝对不。动动脑筋思考！有多少人会打错第一个字母？没那么多~ 所以去掉“mallo”。酷！然后你会发现人们倾向于打错更多的元音而不是辅音。原因是人类眼睛发现辅音的错别字非常明显。所以他们可能会在提交给电脑之前纠正它们。因此，“hello”的 P(i|s) 肯定比“hallow”好得多。这清楚吗？

以上所有内容都出自 Peter Norvig 博士的论文。但我认为这些对于确定 P(i|s) 来说还不够。所以我观察人们的打字习惯，发现我们有些人，比如我，手指很粗。所以我们不是输入“hello”，而是输入“hrllo”或“hekko”。如果您仔细查看键盘，您就会明白为什么。因为“e”和“r”靠近，“k”和“l”也靠近。所以这里我们有另一个标准，如果一个字母被键盘上的相邻字母替换，P(i|s) 将会增加。所以当输入“hrllo”时，“hello”的概率肯定比“hillo”（如果确实有这个词）更高。好的，我希望您没有在这里迷失。这就是 SpellingDice 的思想。如果您不想了解算法，可以跳过以下内容，直接到 此处 下载 PHP 和 C# 的 API。

示例

试用在线 SpellingDice Corrector PHP

请点击 此处

算法

Array<string> ReturnSuggestion(string inputWord)

{

Array<string> result=null;

if( inputWord[0].ToLowerCase()>='a' && inputWord[0].ToLowerCase()<='z') // 仅当它是英文字母时才继续

{

Array<string> Candidates = ReadFromXML(inputWord[0].ToLowerCase()); // 为了加快处理速度，只读取以第一个字母开头的字典。例如，如果输入是“hallo”，只读取“h.xml”。

Maps<string, double> RefinedCandidates;

foreach(string candidate in Candidates)

{

if(LevenshteinDistance(candidate, inputWord)<=2) // 只检查编辑距离与输入相比小于或等于 2 的单词。否则候选列表会很长，而且帮助不大。

{

RefinedCandidates[candidate]=CalculateConditionProbability(candidate, inputWord)*probability(candidate);

}

}

Sort(RefinedCandidates);

result=ConvertMapIntoArray(RefinedCandidates);

}

return result;

}

API

要下载此套件，请点击 此处

PHP

SpellDice::ReturnSuggestion($inputString);

// 无论输入是句子还是单词，它都会返回一个建议的句子或 5 个建议的单词。如果没有建议，则返回 null。注意：当输入是单词时，返回值将是字符串数组；如果输入是句子，将返回一个句子字符串。

SpellDice::SentenceProcess($inputString);

// 只处理一个句子，返回一个建议的句子

SpellDice::WordProcess($inputString)

// 只处理一个单词，将返回一个最多包含 5 个建议单词的数组。

C#

namespace SpellCheck

public class SpellingDice

{

public SpellingDice() // 初始化方法

public List<string>ReturnSuggestion(string input); /// 无论输入是句子还是单词，它都会返回一个建议的句子或 5 个建议的单词。如果没有建议，则返回 null。注意：当输入是单词时，返回值将是字符串数组；如果输入是句子，将返回一个只包含一个元素的数组。

public List<string> WordProcess(string word) // 只处理一个单词，将返回一个最多包含 5 个建议单词的数组。

}

代码片段

PHP

        function GuessCandidates($compareString)
        {
        global $vocabularyArray;
        $letter=$compareString[0];
        if(count($vocabularyArray[$letter])==0)
        {
        $parser = xml_parser_create(); 

        xml_parser_set_option($parser,XML_OPTION_SKIP_WHITE,1); <o:p />
    
        xml_parser_set_option($parser,XML_OPTION_CASE_FOLDING,0);
        <o:p> </o:p>
        $data = implode("",file('dictionary/'.$letter.'.xml'));  
        xml_parse_into_struct($parser,$data,&$d_ar,&$i_ar)
            or print_error();
        $counter=0;
        for($i=0; $i<count($i_ar['WordEntry']);
            $i++) {       
             if($d_ar[$i_ar['WordEntry'][$i]]['type']=='open') {
                 for($j=$i_ar['WordEntry'][$i]; $j<$i_ar['WordEntry'][$i+1];
            $j++) {
                     if($d_ar[$j]['tag'] == 'word')
            {
                         $word = $d_ar[$j]['value'];
                     }elseif($d_ar[$j]['tag'] == 'probability')
            {
                         $probability = $d_ar[$j]['value'];
                     }
                 }
                 $editDistance=SpellDice::StringDistance($compareString,$word);
                 if($compareString==$word)
                 return $word;
                 else  
                 if($editDistance<=20)
                   $CandidateArray[$compareString][$word]=$probability*(20/$editDistance);
             }
        }
        xml_parser_free($parser);
        }
        arsort($CandidateArray[$compareString]);
        if(count($CandidateArray[$compareString])>5)
        $CandidateArray[$compareString]=array_slice($CandidateArray[$compareString],
            0, 5);
        $result=array();
        foreach ($CandidateArray[$compareString]
            as $key=> $value)
        { 
                         array_push($result,$key);
        } 
        return $result;     <o:p />
 

        } 
 

C#

public List<string> WordProcess(string
            word) 

                 {
                      List<string> result = new List<string>();
                     SortedDictionary<double, string>
            listOfCandidates = new SortedDictionary<double, string>(); 
                     if (word[0] <= 'z' &&
            word[0] >= 'a')
                     {
                         if (candidatesList[word[0]].Count
            == 0)
                             ReadFromXMLFile(word[0]);
                         foreach (Dictionary
            DictionaryItem in candidatesList[word[0]])
                         {
                             if
            (DictionaryItem.word == word)
                             {                           
        result.Add(word);                          
        return result;
                             }
                             else
                             {                
        int LD = Levenshtein(word, DictionaryItem.word);       
                      if (LD <= 2)                        
        {             
                double editDistance = StringDistance(word, DictionaryItem.word,
            LD);              
                                                          
                    listOfCandidates[1 / (DictionaryItem.probability * (1 / editDistance))] = DictionaryItem.word;
                                
        }                }   } <o:p />
     foreach (KeyValuePair<double,string> kvp in listOfCandidates) 
                         {
                             result.Add(kvp.Value);
                         }
                         // result.Reverse();
                         if (listOfCandidates.Count > 5)
                             result.RemoveRange(5,  listOfCandidates.Count - 5);
                     }
                     else
                         result.Add(word); <o:p />
                 return result; 
                 } 

结论

这个算法的性能实际上非常好，因为我们有一些启发式方法来确保最少的循环。

读取字典需要 O(n)

然后遍历字典需要 O(n)

检查每个单词需要 O(m)（m 是单词的长度）

排序需要 O(nlogn)

所以总的来说，我们正在研究一个 O(n) + O(nlogn) + O(n*m) 算法。

PHP 版本比 C# 稍快，因为它有一些简洁的内置函数。C# 没有自动排序的数据结构来处理数组（SortedDictionary 只对键排序而不是值，而且是从低到高，这与我们想要的方式相反）。

该程序在很大程度上也取决于您的词典。我提供的词典包含 5000 个英语单词。但这还不够。您可能需要自己扩展词典。我将它们制作成 26 个 XML 文件。您可以自己做得更多。这个程序可以处理常规的拼写校正，但我不能保证它能提供与 Google Suggest 相同的效果，因为它们存储了更大的数据量和拥有其他优势。

总而言之，这是一个小巧快速的程序，可以帮助您在网站或小型项目中实现一个简洁的功能。如果您有任何问题或意见，请直接与我联系。