跳至主要內容

NLP 英文拼写算法，如果提升 100W 倍的性能？

老马啸西风2020年1月20日大约 19 分钟NLPchinesenlpalgorithmsh

拼写纠正系列

NLP 中文拼写检测实现思路

NLP 中文拼写检测纠正算法整理

NLP 英文拼写算法，如果提升 100W 倍的性能？

NLP 中文拼写检测纠正 Paper

java 实现中英文拼写检查和错误纠正？可我只会写 CRUD 啊！

一个提升英文单词拼写检测性能 1000 倍的算法？

单词拼写纠正-03-leetcode edit-distance 72.力扣编辑距离

NLP 开源项目

nlp-hanzi-similar 汉字相似度

word-checker 拼写检测

pinyin 汉字转拼音

opencc4j 繁简体转换

sensitive-word 敏感词

SymSpell 算法

拼写更正和模糊搜索：通过对称删除拼写更正算法快 100 万倍

对称删除拼写校正算法降低了给定 Damerau-Levenshtein 距离的编辑候选生成和字典查找的复杂性。

它比删除 + 转置 + 替换 + 插入的标准方法快六个数量级，并且与语言无关。

与其他算法相反，只需要删除，不需要转置 + 替换 + 插入。输入术语的转置 + 替换 + 插入被转换为字典术语的删除。替换和插入很昂贵并且依赖于语言：例如中文有7万个Unicode汉字！

速度来自廉价的仅删除编辑候选生成和预计算。

一个平均 5 个字母的单词在最大编辑距离 3 内有大约 300 万个可能的拼写错误，但是 SymSpell 只需要生成 25 个删除来覆盖它们，无论是在预计算还是在查找时。 Magic!

单字拼写更正

Lookup 提供了非常快速的单个单词拼写纠正。

Verbosity 参数允许控制返回结果的数量：

顶部：找到的最小编辑距离建议中词频最高的顶部建议。

最近：找到所有编辑距离最小的建议，建议按词频排序。

全部：maxEditDistance 内的所有建议，建议按编辑距离排序，然后按词频排序。

最大编辑距离参数控制应将词典中的哪些编辑距离词视为建议。

所需词频词典既可以直接从文本文件中加载（LoadDictionary），也可以从大型文本语料库中生成（CreateDictionary）。

应用

拼写更正，

查询更正（10-15% 的查询包含拼写错误的术语），

聊天机器人，

OCR后处理，

自动校对。

模糊搜索和近似字符串匹配

复合感知多词拼写纠正

LookupCompound 支持多词输入字符串的复合感知自动拼写校正。

  1. 化合物分裂和分解

Lookup() 将每个输入字符串假定为单个术语。 LookupCompound 还支持复合拆分/分解三种情况：

在正确的单词中错误地插入空格导致两个不正确的术语

错误地省略了两个正确单词之间的空格导致一个错误的组合词

有/没有拼写错误的多个输入词

拆分错误、连接错误、替换错误、换位错误、删除错误和插入错误可以混合在同一个词中。

  1. 自动拼写更正

大型文档集合使手动更正变得不可行，并且需要无人监督的全自动拼写更正。

在单个标记的常规拼写纠正中，向用户呈现多个拼写纠正建议。

对于长多字文本的自动拼写校正，算法本身必须做出有根据的选择。

- whereis th elove hehad dated forImuch of thepast who couqdn'tread in sixthgrade and ins pired him
+ where is the love he had dated for much of the past who couldn't read in sixth grade and inspired him  (9 edits)

- in te dhird qarter oflast jear he hadlearned ofca sekretplan
+ in the third quarter of last year he had learned of a secret plan  (9 edits)

- the bigjest playrs in te strogsommer film slatew ith plety of funn
+ the biggest players in the strong summer film slate with plenty of fun  (9 edits)

- Can yu readthis messa ge despite thehorible sppelingmsitakes
+ can you read this message despite the horrible spelling mistakes  (9 edits)

嘈杂文本的分词

WordSegmentation 通过在适当的位置插入缺失的空格将字符串分成单词。

拼写错误的单词会得到纠正，并且不会阻止分割。

允许并考虑现有空间以进行最佳分割。

SymSpell.WordSegmentation 使用三角矩阵方法而不是传统的动态编程：它使用数组而不是字典进行记忆，循环而不是递归，并逐步优化前缀字符串而不是剩余字符串。

三角矩阵方法比动态规划方法快。 它具有更低的内存消耗、更好的扩展性（恒定 O(1) 内存消耗与线性 O(n)）并且是 GC 友好的。

虽然每个长度为 n 的字符串可以分割成 2^n−1 种可能的组合，

SymSpell.WordSegmentation 有一个线性运行时间 O(n) 来找到最佳组合。

例子：

- thequickbrownfoxjumpsoverthelazydog
+ the quick brown fox jumps over the lazy dog

- itwasabrightcolddayinaprilandtheclockswerestrikingthirteen
+ it was a bright cold day in april and the clocks were striking thirteen

- itwasthebestoftimesitwastheworstoftimesitwastheageofwisdomitwastheageoffoolishness
+ it was the best of times it was the worst of times it was the age of wisdom it was the age of foolishness

应用：

  • 用于索引拼写校正、机器翻译、语言理解、情感分析的 CJK 语言的分词

  • 标准化英语复合名词以进行搜索和索引（例如，ice box = ice-box = icebox；pig sty = pig-sty = pigsty）

  • 如果原始词和拆分词部分都应该被索引，则复合词的分词。

  • 更正因打字错误导致的空格缺失。

  • 更正转换错误：单词之间的空格可能会丢失，例如删除换行符时。

  • 更正 OCR 错误：原始文档或手写文本质量较差可能会导致无法识别所有空格。

  • 传输错误的更正：在通过嘈杂的信道传输期间，空间可能会丢失或引入拼写错误。

  • 从 URL 地址、域名、#hashtags、表列描述或没有空格的编程变量中提取关键字。

  • 对于密码分析，可能需要从密码中提取术语。

  • 对于语音识别，如果在口语中无法正确识别单词之间的空格。

  • 编程变量的自动 CamelCasing。

  • 自然语言处理以外的应用，例如将 DNA 序列分割成单词

Usage SymSpell Library

//create object
int initialCapacity = 82765;
int maxEditDistanceDictionary = 2; //maximum edit distance per dictionary precalculation
var symSpell = new SymSpell(initialCapacity, maxEditDistanceDictionary);
      
//load dictionary
string baseDirectory = AppDomain.CurrentDomain.BaseDirectory;
string dictionaryPath= baseDirectory + "../../../../SymSpell/frequency_dictionary_en_82_765.txt";
int termIndex = 0; //column of the term in the dictionary text file
int countIndex = 1; //column of the term frequency in the dictionary text file
if (!symSpell.LoadDictionary(dictionaryPath, termIndex, countIndex))
{
  Console.WriteLine("File not found!");
  //press any key to exit program
  Console.ReadKey();
  return;
}

//lookup suggestions for single-word input strings
string inputTerm="house";
int maxEditDistanceLookup = 1; //max edit distance per lookup (maxEditDistanceLookup 对称删除拼写校正算法通过仅使用删除而不是删除 + 转置 + 替换 + 插入来降低编辑候选生成和字典查找的复杂性。 它快了六个数量级（编辑距离=3）并且与语言无关。

备注1：在预计算过程中，字典中不同的词可能会导致相同的删除词：delete(sun,1)==delete(sin,1)==sn。

虽然我们只生成一个新的字典条目 (sn)，但在内部我们需要将两个原始术语存储为拼写更正建议 (sun,sin)

备注 2：有四种不同的比较对类型：

dictionary entry==input entry,
delete(dictionary entry,p1)input entry // 预处理
dictionary entrydelete(input entry,p2)
delete(dictionary entry,p1)==delete(input entry,p2)


仅替换和转置需要最后一个比较类型。 

但是我们需要检查建议的字典术语是否真的是输入术语的替换或相邻转置，以防止更高编辑距离的误报（bank==bnak 和bank==bink，但是bank!=kanb 和bank!= xban 和银行！=baxn）。

备注 3：我们使用的是搜索引擎索引本身，而不是专用的拼写字典。 

这有几个好处：

它是动态更新的。 每个新索引的词，其频率超过某个阈值，也会自动用于拼写校正。

由于我们无论如何都需要搜索索引，因此拼写更正几乎不需要额外的成本。

当索引拼写错误的术语时（即未在索引中标记为正确），我们会即时进行拼写更正，并为正确的术语索引页面。

备注 4：我们以类似的方式实现了查询建议/完成。 

这是首先防止拼写错误的好方法。 

每个新索引的单词，其频率超过某个阈值，都被存储为对其所有前缀的建议（如果它们尚不存在，则会在索引中创建）。 

由于我们提供了即时搜索功能，因此查找建议也几乎不需要额外费用。 多个术语按存储在索引中的结果数排序。

## 推理

SymSpell 算法利用了两个术语之间的编辑距离对称的事实：

我们可以生成与查询词条编辑距离  4 时近似字符串匹配速度快十亿倍

但该算法的真正潜力在于编辑距离 > 3 和拼写检查之外。

许多数量级的更快算法为近似字符串匹配开辟了新的应用领域，并为大数据和实时提供了足够的扩展。

我们的算法可以在非常大的数据库中与长字符串或特征向量、巨大字母表、大编辑距离、具有许多并发处理和实时要求的快速近似字符串和模式匹配。

## 应用领域

- 搜索引擎中的拼写更正，具有许多并行请求

- 大型语料库中的自动拼写校正

- 基因组数据分析，

- 匹配的 DNA 序列

- 浏览器指纹分析

- 实时图像识别（按图像搜索、自动驾驶汽车、医学）

- 人脸识别

- 虹膜识别

- 语音识别

- 语音识别

- 特征识别

- 指纹识别

- 签名识别

- 抄袭检测（在音乐中/在文本中）

- 光学字符识别

- 音频指纹

- 欺诈识别

- 地址重复数据删除

- 拼写错误的名字识别

- 基于光谱的化学和生物材料鉴定

- 文件修改

- 垃圾邮件检测

- 相似性搜索，

- 相似度匹配

- 近似字符串匹配，

- 模糊字符串匹配，

- 模糊字符串比较，

- 模糊字符串搜索，

- 模式匹配，

- 数据清洗

- 还有很多

## 编辑距离度量

虽然我们将 Damerau-Levenshtein 距离用于其他应用程序的拼写校正，但只需修改相应的函数，就可以轻松地将其与 Levenshtein 距离或类似的其他编辑距离进行交换。

在我们的算法中，编辑距离计算的速度对整体查找速度的影响很小。 

这就是为什么我们只使用基本实现而不是更复杂的变体。

## 基准

由于除拼写检查之外的近似字符串匹配的所有应用程序，我们将基准扩展到具有更高编辑距离的查找。 

这就是对称删除算法真正闪耀并超越其他解决方案的地方。 

使用以前的拼写检查算法，所需的时间随着编辑距离的增加而激增。

## 速度增益

速度优势随着编辑距离呈指数增长：

对于编辑距离=1，速度快了 1 个数量级，

对于编辑距离=2，速度快了 4 个数量级，

对于编辑距离=3，它的速度提高了 6 个数量级。

对于编辑距离=4，速度快了 8 个数量级。

## 计算复杂度

我们的算法是恒定时间（O(1) 时间），即独立于字典大小（但取决于平均术语长度和最大编辑距离），因为我们的索引基于哈希表，其平均搜索时间复杂度为 O(1)。

# 拓展阅读

https://github.com/MighTguY/customized-symspell (Version 6.6)
https://github.com/rxp90/jsymspell (Version 6.6)
https://github.com/Lundez/JavaSymSpell (Version 6.4)
https://github.com/rxp90/jsymspell
https://github.com/gpranav88/symspell
https://github.com/searchhub/preDict
https://github.com/jpsingarayar/SpellBlaze


# 中文拼写检测

https://github.com/wolfgarbe/SymSpell

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

https://github.com/jpsingarayar/SpellBlaze

# 参考资料

https://wolfgarbe.medium.com/1000x-faster-spelling-correction-algorithm-2012-8701fcd87a5f

[Fast approximate string matching with large edit distances in Big Data (2015)](https://wolfgarbe.medium.com/fast-approximate-string-matching-with-large-edit-distances-in-big-data-2015-9174a0968c0b)

贡献者

binbin.hou
我是老马，期待与你的下次重逢
Copyright © 2025 老马啸西风