BK Tree

用于根据编辑距离(Levenshtein距离)概念执行拼写检查。 BK树也用于近似字符串匹配。基于该数据结构,可以实现许多软件中的各种自动校正特征。 BKTree算法上分两步: 1 构造 在词典里面随便找一个词作为root节点,然后与其他词计算编辑距离n。若已有相同编辑距离n的子节点,就挂在子节点下;若没有,就新建边为n的子节点。如此递归下去。 2 查询 这里重点来了,编辑距离符合三角不等式:任意两条边的和大于第三条边。所以只用从根节点开始,找(d-n) < x < (d+n)的边。这样可以大量减少编辑距离的计算次数,即减少O(D*m*n)中的D。 3 举例 一构造那张图为例,