每个用户在编写搜索查询时都曾经打过错字。缺少纠正错别字的机制会导致发布不相关的结果，甚至导致结果的缺失。因此，为了使搜索引擎更加面向用户，内置了纠错机制。

乍看之下，纠正错别字的任务似乎并不复杂。但是，如果您从各种错误入手，那么实施解决方案可能会很困难。通常，错字校正分为上下文无关和上下文敏感（其中考虑了字典环境） 。在第一种情况下，针对每个单词分别纠正错误，在第二种情况下-考虑到上下文（例如，在上下文无关的情况下针对短语“她回家”，每个单词分别进行纠正，我们可以得到“她回家”，在第二种情况下，正确的更正将显示“她已回家”）。

在说俄语的用户的搜索查询中，仅针对上下文无关的校正，可以将错误分为四个主要组[ 1 ]：
1）单词本身有错误（例如mr →hi），此类别包括字母的各种省略，插入和排列-63.7％，
2）单词的连续拼写-16.9％，
3）布局失真（ghbdtn→hi）-9.7％，
4）音译（女权→喜）-1.3％，
5）混合错误-8.3％。

用户在大约10-15％的情况下会打错字。同时，83.6％的请求有一个错误，11.7％-两个，4.8％-大于三个。在26％的情况下，情境很重要。

这些统计数据是根据2013年Yandex每日日志（基于10,000个查询）的随机样本编制的。在公共领域，Yandex在2008年发表了一篇更早的演讲，它显示了相似的统计分布[ 2 ]。由此我们可以得出结论，平均来说，搜索查询错误的分布不会随时间变化。

通常，错字校正机制基于两个模型：错误模型和语言模型。此外，对于上下文无关的校正，仅使用错误模型，而在上下文相关的校正中，一次使用两个。误差模型通常是编辑距离（Levenshtein，Damerau-Levenshtein距离，各种加权因子，类似于Soundex的方法等），也可以在此处添加-在这种情况下，该距离称为“加权”）或Bril-Moore模型，研究从一条线到另一条线过渡的概率。 Bril和Moore将他们的模型定位为更加完美，但是，在最近的SpellRuEval竞赛之一中，Damerau-Levenshtein方法显示了更好的结果[ 3 ]，尽管事实上Damerau-Levenshtein距离（未加权）没有使用有关后卫统计数据的先验信息。。如果DeepPavlov库中的自动校正器的不同实现方式使用了相同的培训文本，则该观察结果尤其具有指示意义。

显然，上下文相关校正的可能性使自动校正器的构造复杂化，因为除了错误模型之外，还增加了对语言模型的需求。但是，如果您注意错别字的统计信息，则¾所有不正确书写的搜索查询都可以在没有上下文的情况下得到纠正。这表明至少一个与上下文无关的自动校正器的好处可能非常重要。

而且，用于校正请求中的错字的上下文相关校正非常耗费资源。例如，在Yandex的一份演讲中，用于纠正单词错字（字母组合）的单词对列表与单词（字母组合）的数量相比，相差10倍，那么三字母组合又是什么呢？显然，这基本上取决于查询的可变性。当自动校正器占用拟议公司产品一半的内存时，它看起来有点奇怪，其目的不是着眼于解决拼写问题。因此，在软件产品的搜索引擎中实施上下文相关的更正的问题可能会引起很大争议。

乍一看，给人的印象是，对于任何一种编程语言，都有许多现成的解决方案，可以在无需过多沉浸于算法操作细节的情况下使用它，包括在商业系统中。但是实际上，他们解决方案的开发仍在继续。例如，相对较近期，Joom做出了自己的决定，即使用语言模型进行搜索查询来纠正错字[ 4 ]。使用交钥匙解决方案是否真的很困难？为此，已尽可能对现有解决方案进行了广泛概述。在开始审查之前，我们将决定如何检查自动校正器的质量。

质量控制

检查自动校正器质量的问题很有争议。一种简单的验证方法是通过Precision和Recall。根据ISO标准，准确性和完整性通过正确性（英文为“ corectness”）进行补充。

完整性（Recall）的计算方式如下：将正确的单词列表提交给自动更正器（Total_list_true），并且自动更正器认为正确的单词数（Spellchecker_true）除以正确的单词总数（Total_list_true）将被视为完整性。

召 回 = 拼 写 检 查 器_{t} r u e \总 计_{l} i s t_{t} r u e

$召回= {拼写检查器\ _true \总计\ _list \ _true}$

为了确定准确性（Precision），将不正确的单词列表（Total_list_false）提供给自动校正器的输入，并且将自动校正器认为不正确的单词数（Spell_checker_false）除以不正确的单词总数（Total_list_false）定义为准确性。

精 度 = 拼 写 检 查 器_{f} a l s e \超 过 合 计_{l} i s t_{f} a l s e

$精度= {拼写检查器\ _false \超过合计\ _list \ _false}$

这些指标通常具有多方面的信息意义，以及它们如何有用，每个指标均独立确定。毕竟，实际上，该测试的本质是在训练词典中检查单词。 正确性可以被认为是更明显的度量标准，根据该度量标准，不正确单词测试集中每个单词的自动校正器会形成一个替换候选者列表，可以针对此不正确单词对其进行纠正（请记住，训练词典中可能不包含某些单词） 。假设这样一个替换候选列表的大小为5。基于该列表的大小为5的事实，将形成6个组，在其中一个中，我们将根据以下原则输入原始的错误词：在第一组中-如果在在替换候选列表中，我们应该输入的正确单词是第1个，如果是第2个，则应该在第二个中，依此类推；在最后一组中，如果假定的正确单词不在替换候选列表中，则在最后一组中。当然，进入第1组的词越多，进入第6组的词越少，自动校正器的效果越好。

作者考虑了文章[ 5 ]中考虑的方法，在该方法中，比较了与ISO标准有偏差的上下文无关自动校正器。它还提供了其他质量评估方法的链接。

一方面，这种方法不是基于总体统计，而是可以基于Brill-Moore误差模型[ 6 ]或Damerau-Levenshtein加权距离误差模型。

为了检查与上下文无关的自动校正器的工作质量，我们创建了自己的错字生成器，该错字生成器根据Yandex提交的错字统计信息生成布局错误的错字和拼写错字。对于拼写错误，生成了随机插入，替换，删除，重新排列，并且错误数量也根据这些统计信息而有所不同。对于布局失真的错误，完全根据字符转换表逐个字符更改了正确的单词。

然后，针对训练词典中的整个单词列表进行了一系列实验（根据特定错别字的概率，将训练词典中的单词校正为不正确的单词） 。平均而言，自动校正器可以在75％的情况下正确校正单词。毫无疑问，当在学习词典中添加距离编辑距离很近的单词（种类繁多的单词）时，该数量将减少。可以通过补充语言模型来解决此问题，但应记住，所需资源的数量将大大增加。

现成的解决方案

考虑现成的解决方案时要着重于自己的使用，并且优先考虑满足以下三个条件的自动校正器：
1）实现语言，
2）许可类型，
3）可更新性。

在产品开发中，Java被认为是最流行的Java之一，因此在搜索库时优先考虑Java。相关许可证中：MIT，Public，Apache，BSD。可更新性-距上一次更新不超过2年。在搜索过程中，记录了其他信息，例如，有关受支持的平台，所需的其他程序，应用程序功能，首次使用可能遇到的困难等信息。本文末尾提供了与资源的基本和有用资源的链接。通常，如果不限于上述标准，则现有解决方案的数量很大。让我们简要看一下主要内容，并只关注其中一些。

从历史上看，最早的自动校正器之一是1971年用汇编器编写的Ispell （国际拼写法），后来转移到了C语言，并使用Damerau-Levenshtein编辑距离作为错误的模型。对于他来说，甚至还有俄语词典。随后，他被两个自动校正器HunSpell （以前是MySpell ）和Aspell所代替 。两者均以C ++实现，并根据GPL许可进行分发。 HunSpell还包含在GPL / MPL中，并用于纠正OpenOffice，LibreOffice，Google Chrome和其他工具中的错别字。

Internet和浏览器有很多JS解决方案（包括： nodehun-sentences ， nspell ， node-markdown-spellcheck ， Proofreader ， Spellcheck-API-一组基于Hunspell自动校正器的解决方案； grunt- spell-用于NodeJS ； yaspeller- ci - Yandex.Speller自动更正器的包装器，由MIT发行； rousseau-JS中的轻量级校对器 -用于拼写）。

付费解决方案的类别包括： Spellex ; 源代码拼写检查器 -作为桌面应用程序；对于JS： nanospell ； Java： Keyoti RapidSpell Spellchecker ， JSpell SDK ， WinterTree （WinterTree甚至可以花5000美元购买源代码）。

彼得·诺维格（Peter Norwig）的自动校正器得到了广泛使用，其Python代码可在“ 如何编写拼写校正器 ”一文[ 7 ]中公开获得。基于此简单的解决方案，自动校正器以其他语言构建，例如： Norvig-spell-check ， scala-norvig-spell-check （在Scala上）， 玩具拼写校正器 -Golang Spellcheck （在GO上）， pyspellchecker （在Python上）。当然，这里我们不是在谈论语言模型和上下文相关的校正。

对于文本编辑者，尤其是为VIM制作的vim-dialect ， vim-ditto －是根据公共许可证发行的；适用于DspellCheck在C ++，GPL许可下开发的Notepad ++； Emacs有一个在打印时自动检测语言的工具，称为“ 猜测语言” ，它是根据公共许可证发行的。

搜索巨头提供了单独的服务： Yandex.Speller-来自Yandex，关于上面提到的包装器， google-api-spelling-java （分别来自Google）。

Java的免费库： languagetool （根据LGPL许可），与Lucene文本搜索库集成并允许使用语言模型，需要Java版本8； Jazzy （ Aspell的类似物）已获得LGPLv2许可，自2005年以来未进行过更新，并于2013年移植到GitHub。类似于此自动校正器，已经提出了单独的解决方案[ 8 ]； Jortho （Java拼写法）是根据GPL发行的，允许免费将其免费用于非商业目的，商业目的-需额外付费； Jaspell （根据BSD许可，自2005年以来未更新）； 开源Java提示器 -自2013年以来未更新，由SoftCorporation LLC分发并允许商业使用； LuceneSpellChecker是用Java编写并在Apache许可下分发的Lucene自动校正器。

长期以来，Wolf Garbe处理错字，他提出了使用C＃实现的SymSpell算法（根据MIT许可）和LinSpell算法 （根据LGPL）[ 9 ]，其中使用了Damerau-Levenshtein距离作为误差模型。其实现的特殊之处在于，在为输入单词生成可能的错误的阶段，仅使用删除，而不使用所有类型的删除，插入，替换和排列。与Peter Norwig的自动校正器的实现相比，这两种算法都因此而工作更快，而如果Damerau-Levenshtein距离大于2，则速度的增加会显着增加。而且，由于仅使用删除的事实，减少了字典形成时间。两种算法之间的区别在于， LinSpell在内存方面更经济，而搜索速度更慢， SymSpell-反之亦然。在更高版本中， SymSpell修复了拼写错误。不使用语言模型。

在使用自动校正器处理语言模型和校正上下文相关的错字方面，最新且最有前途的工具包括Yandex.Speller ， JamSpell [ 10 ]，DeepPavlov [ 11 ]。最后2个是自由分发的： JamSpell （MIT）， DeepPavlov （在Apache下）。

Yandex.Speller使用CatBoost算法，可以使用多种语言，并且即使考虑到上下文也可以纠正各种错误。发现的唯一解决方案是纠正不正确的布局错误和音译。该解决方案具有多功能性，因此很受欢迎。它的缺点是它是远程服务，有关使用的限制和条件，请参见此处[ 12 ]。该服务只能使用几种语言；您不能自己添加单词并管理更正过程。根据资源[ 3 ]和RuSpellEval竞赛的结果，该自动校正器显示出最高的校正质量。 JamSpell是已知最快的自动校正器 （C ++实现），有现成的其他语言的活页夹 。仅纠正单词本身中的错误，并使用特定的语言。您不能在单字和二元组级别上使用该解决方案。为了获得可接受的质量，需要大量的培训文字。
DeepPavlov有一些良好的做法，但是，将这些解决方案及其后续支持集成到他们自己的产品中可能会造成困难，因为与它们一起使用需要连接虚拟环境并使用早期版本的Python 3.6。 DeepPavlov提供了三种自动校正器的现成实现方式的选择，其中两种应用了Bril-Moore错误模型，而两种语言模型中。它仅纠正拼写错误，并且基于Damerau-Levenshtein距离的带有错误模型的变体可以纠正拼写错误。

我将提到另一种纠正错别字的现代方法，该方法基于单词的矢量表示（单词嵌入）的使用。它的优点是可以用来构建自动更正器，以根据上下文更正单词。关于这种方法的更多细节可以在这里找到[ 13 ]。但是，为了使用它来纠正搜索查询的错字，您将需要积累大量的查询日志。此外，该模型本身在内存消耗方面可能非常宽敞，这将影响到产品集成的复杂性。

瑙门选择

在现成的Java解决方案中，选择了Lucene的自动校正器（在Apache的许可下分发）。允许您纠正单词中的错别字。学习过程很快：例如，在Intel Core i5-8500 3.00GHz处理器，32 Gb RAM，Lucene 8.0.0上，特殊字典数据结构（300万行的索引）的形成需要30秒。在早期版本中，时间可能会长2倍。培训词典的大小为300万行（〜73 Mb txt文件），索引结构为〜235 Mb。对于误差模型，您可以选择Jaro-Winkler，Levenshtein，Damerau-Levenshtein，N-Gram的距离，如果需要，可以添加自己的距离。如有必要，可以连接语言模型[ 14 ]。自2001年以来就已经知道模型，但是没有将它们与公共领域中的著名现代解决方案进行比较。下一步是检查他们的工作。

最终的基于Lucene的解决方案只能纠正单词本身中的错误。通过适当的转换表将失真的键盘布局的校正添加到任何此类解决方案并不难，从而将无关输出的可能性降低到10％（根据拼写统计）。此外，很容易添加单独的融合2个单词的书写和音译。

该解决方案的主要缺点是需要Java知识，缺少详细的用例和详细的文档，这反映在为Data-Science专家开发解决方案的速度下降中。此外，Damerau-Levenshtein距离大于2的错别字不会得到纠正。同样，如果我们从失实陈述统计出发，一个单词中的两个以上错误发生的频率要比5％的情况低。是否有必要使算法复杂化，特别是增加内存消耗，是否合理？它已经取决于客户的情况。如果还有其他资源，那为什么不使用它们呢？

负担得起的自动校正器的关键资源：

开放式错字校正解决方案概述

质量控制

现成的解决方案

瑙门选择

More articles: