返回

SymSpell 拼写检查算法

常见的拼写检查Trie树,哈希表,布隆过滤器,BK树。其中只有Trie树和BK树能够给出推荐单词。

对称删除拼写校正

预处理

首先对字典进行处理,对每一个词条生成与其编辑距离≤2(只进行删除操作)的字符串,并添加到字典中。这是一个预处理过程,后面的操作都是基于这个全新的字典。

对称删除拼写校正算法通过仅使用删除而不是删除+转置+替换+插入来降低编辑候选生成和字典查找的复杂性。它快6个数量级(编辑距离= 3)和语言无关。

计算复杂度

SymSpell算法复杂度为O(1),独立于字典大小(但取决于词条平均长度和最大编辑距离)。

❤️
Built with Hugo
Theme Stack designed by Jimmy