SymSpellSwift

SymSpell 的 Swift 实现：拼写校正 & 模糊搜索：通过对称删除拼写校正算法，速度提升 100 万倍

描述来自 https://github.com/wolfgarbe/SymSpell/

对称删除拼写校正算法降低了给定 Damerau-Levenshtein 距离的编辑候选生成和字典查找的复杂性。它比标准方法（使用删除 + 转置 + 替换 + 插入）快六个数量级，并且与语言无关。

与其他算法相反，仅需要删除操作，不需要转置 + 替换 + 插入。输入词的转置 + 替换 + 插入被转换为字典词的删除操作。替换和插入的成本很高，并且与语言相关：例如，中文有 70,000 个 Unicode 汉字！

速度来自廉价的仅删除编辑候选生成和预计算。一个平均 5 个字母的单词在最大编辑距离为 3 的范围内，大约有 300 万个可能的拼写错误，但 SymSpell 只需要生成 25 个删除操作即可覆盖所有错误，无论是在预计算时还是在查找时。神奇！

Lookup 提供了非常快速的单字拼写校正。

• Verbosity 参数允许控制返回结果的数量：Top：具有最高词频的最小编辑距离建议。Closest：所有最小编辑距离的建议，建议按词频排序。All：maxEditDistance 内的所有建议，建议按编辑距离排序，然后按词频排序。
• Maximum edit distance 参数控制字典中与建议词之间的最大编辑距离。
• 所需的词频字典可以直接从文本文件加载（LoadDictionary），也可以从大型文本语料库生成（CreateDictionary）。

• 拼写校正，
• 查询校正（10-15% 的查询包含拼写错误的词），
• 聊天机器人，
• OCR 后处理，
• 自动校对。
• 模糊搜索 & 近似字符串匹配

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

lookup() 假定每个输入字符串都是单个词。lookupCompound() 还支持复合词拆分/分解，包括三种情况：

1. 在正确的单词中错误地插入了空格，导致两个不正确的词
2. 在两个正确的单词之间错误地省略了空格，导致一个不正确的组合词
3. 多个带有/不带有拼写错误的输入词

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

2. 自动拼写校正

大型文档集合使手动校正不可行，需要无监督的、完全自动的拼写校正。在传统的单个词的拼写校正中，用户会看到多个拼写校正建议。对于长篇多字文本的自动拼写校正，算法本身必须做出明智的选择。

- 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) 内存消耗 vs. 线性 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、表格列描述或不带空格编写的编程变量中提取关键字。
• 对于密码分析，可能需要从密码中提取术语。
• 对于语音识别，如果口语中单词之间的空格未被正确识别。
• 自动骆驼命名编程变量。
• 自然语言处理之外的应用，例如，将 DNA 序列分割成单词

当前的实现基于原始的 SymSpell，但使用 Swift 最佳实践和现代范例来实现相同的结果，甚至具有更好的性能。

let symSpell = SymSpell(maxDictionaryEditDistance: 2, prefixLength: 3)
if let path = Bundle.main.url(forResource: "frequency_dictionary_en_82_765", withExtension: "txt") {
  try? symSpell.loadDictionary(from: path, termIndex: 0, countIndex: 1, termCount: 82765)
}

let results = symSpell.lookup("intermedaite")

print(results.first?.term)