介绍
拼写纠错功能常常出现在比较高级的文本编辑应用中,例如大家熟知的word,高级一点的IDE例如Jet Brains系列,在一些在线翻译上,也有自动校正拼写的功能,例如谷歌翻译。
原理
拼写纠正的实现方式有多种,这里使用的是一种名为BK树的数据结构,也叫作Burkhard-Keller树,是由Burkhard,Keller这两人提出来的,不过网上能找到的相关资料并不多,参见ACM文档https://dl.acm.org/citation.cfm?id=362003.362025。
最短编辑距离
在介绍BK树思想之前,要介绍一个概念——莱文斯坦距离,又称Levenshtein距离,是编辑距离的一种。指两个字串之间,由一个转成另一个所需的最少编辑操作次数。允许的编辑操作包括
- 将一个字符替换成另一个字符。
- 插入一个字符。
- 删除一个字符。
每经过一种操作编辑距离+1,当然也能够根据实际需求设定不同的权值。例如从 cute 到 cat,需要将u替换为a,删除e,因此它的的最短编辑距离为2。
定义dist(a, b)为字符串a到b的编辑距离,有如下数学性质
- dist(a, b) = 0 <==> a = b // 相同的字符串编辑距离当然为0
- dist(a, b) = dist(b, a) // a到b的编辑距离与b到a的编辑距离是一样的,因为添加-删除,替换-替换是互逆的操作
- dist(a, temp) + dist(temp, b) >= dist(a, b) // 这点很重要,这是一条三角不等式,对于三角形从a顶点到b顶点的距离必然小于a到c再从c到b的距离。
推论
在模糊匹配值,我们需要设定一个容错值,而这个值用最短编辑距离来衡量,例如我们设定容错值是1,字典中有 [cat, cute, candy],给出字符串cate,能够匹配到[cat, cute],因为这两个字符串与cate的编辑距离都小于等于1 ,而dist("cate