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

FastFuzzyStringMatcher FastFuzzyStringMatcher是用于快速内存中字符串匹配的BK树实现。 （也可用于 ）。 特征 快速，模糊，字符串匹配。 根据百分比进行搜索并编辑距离。 将数据与字符串关键字相关联，并同时返回两者。 例如，搜索文件名，然后返回关联的文件路径。 动机 尽管哈希映射可用于精确的字符串匹配，而尝试可用于前缀匹配，但目前很少有基于编辑距离或百分比差异的快速匹配解决方案。 当然，您可以搜索集合中的每个字符串，将其编辑距离与要搜索的关键字进行比较，但这往往效率很低。 FastFuzzyStringMatcher构建以使搜索效率更高。 设置 该项目最初是使用Eclipse和Java 8构建的，并且假设您已安装了最新的JDK，则应该干净地构建。 主类可以在src/main/java com.gitub.pekoto.fastfuzzys

详细见blog：https://blog.csdn.net/koibiki/article/details/83052431