算法简介
BK树（Burkhard-Keller Tree）是一种基于度量空间的高效相似度搜索树，专门用于解决”近似字符串匹配”问题，如拼写纠错、模糊搜索等场景。与暴力枚举所有候选词并计算编辑距离的方法不同，BK树利用三角不等式进行剪枝，将查询复杂度从线性降低到对数级别，在词典规模较大时优势尤为明显。
核心思想
BK树的核心建立在编辑距离（Levenshtein Distance）和度量空间三角不等式之上：
- 编辑距离：将一个字符串转换为另一个字符串所需的最少单字符编辑操作（插入、删除、替换）次数
- 度量空间：编辑距离满足度量空间的三条公理——非负性、对称性和三角不等式
- 三角不等式：对于任意三个字符串 $a, b, c$，有 $d(a, c) \leq d(a, b) + d(b, c)$
剪枝原理：如果查询串 $q$ 与BK树中节点 $n$ 的编辑距离为 $d$，容忍阈值为 $T$，那么任何与 $n$ 编辑距离大于 $d + T$ 的子树都不可能包含匹配结果，可以直接跳过。
Java实现
import java.util.*;
/**
* BK树（Burkhard-Keller Tree）实现
* 基于编辑距离的度量空间搜索树
*
* @author AlgorithmDaily
*/
public class BKTree {
/**
* BK树节点
*/
private static class Node {
String word;
// 子节点映射：键为到子节点的编辑距离，值为子节点
Map<Integer, Node> children;
Node(String word) {
this.word = word;
this.children = new HashMap<>();
}
}
private Node root;
private int size;
public BKTree() {
this.root = null;
this.size = 0;
}
/**
* 计算两个字符串的编辑距离（Levenshtein Distance）
* 使用动态规划，时间复杂度O(m*n)
*
* @param s1 第一个字符串
* @param s2 第二个字符串
* @return 编辑距离
*/
public static int levenshteinDistance(String s1, String s2) {
int m = s1.length();
int n = s2.length();
// 使用滚动数组优化空间
int[] prev = new int[n + 1];
int[] curr = new int[n + 1];
// 初始化第一行
for (int j = 0; j <= n; j++) {
prev[j] = j;
}
for (int i = 1; i <= m; i++) {
curr[0] = i;
for (int j = 1; j <= n; j++) {
int cost = (s1.charAt(i - 1) == s2.charAt(j - 1)) ? 0 : 1;
// 取删除、插入、替换三种操作的最小值
curr[j] = Math.min(Math.min(
prev[j] + 1, // 删除
curr[j - 1] + 1 // 插入
), prev[j - 1] + cost); // 替换
}
// 交换数组
int[] temp = prev;
prev = curr;
curr = temp;
}
return prev[n];
}
/**
* 向BK树中添加一个单词
* @param word 待添加的单词
*/
public void add(String word) {
if (word == null || word.isEmpty()) return;
if (root == null) {
root = new Node(word);
size++;
return;
}
Node current = root;
while (true) {
int distance = levenshteinDistance(word, current.word);
// 如果已存在该词，不重复添加
if (distance == 0) return;
Node child = current.children.get(distance);
if (child == null) {
current.children.put(distance, new Node(word));
size++;
return;
}
current = child;
}
}
/**
* 批量添加单词
*/
public void addAll(Collection<String> words) {
for (String word : words) {
add(word);
}
}
/**
* 搜索与查询串编辑距离不超过maxDistance的所有单词
* 利用三角不等式进行剪枝
*
* @param query 查询串
* @param maxDistance 最大容忍编辑距离
* @return 匹配的单词列表（按编辑距离排序）
*/
public List<MatchResult> search(String query, int maxDistance) {
List<MatchResult> results = new ArrayList<>();
if (root == null || query == null) return results;
// 使用栈进行深度优先搜索
Deque<Node> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
int distance = levenshteinDistance(query, node.word);
// 如果当前节点在容忍范围内，加入结果
if (distance <= maxDistance) {
results.add(new MatchResult(node.word, distance));
}
// 利用三角不等式剪枝：
// 如果 |distance - childDistance| > maxDistance，则子树中不可能有匹配
// 即只需要搜索编辑距离在 [distance - maxDistance, distance + maxDistance] 范围内的子节点
int lowerBound = Math.max(1, distance - maxDistance);
int upperBound = distance + maxDistance;
for (Map.Entry<Integer, Node> entry : node.children.entrySet()) {
int childDist = entry.getKey();
if (childDist >= lowerBound && childDist <= upperBound) {
stack.push(entry.getValue());
}
}
}
// 按编辑距离排序
results.sort(Comparator.comparingInt(m -> m.distance));
return results;
}
/**
* 搜索与查询串最相似的N个单词
*/
public List<MatchResult> searchBestMatches(String query, int n) {
// 先尝试小范围搜索，逐步扩大
for (int maxDist = 1; maxDist <= Math.max(query.length(), 5); maxDist++) {
List<MatchResult> results = search(query, maxDist);
if (results.size() >= n) {
return results.subList(0, n);
}
}
return search(query, Integer.MAX_VALUE);
}
/**
* 匹配结果封装
*/
public static class MatchResult {
public final String word;
public final int distance;
public MatchResult(String word, int distance) {
this.word = word;
this.distance = distance;
}
@Override
public String toString() {
return word + "(" + distance + ")";
}
}
public int size() {
return size;
}
/**
* 主程序：演示BK树拼写纠错
*/
public static void main(String[] args) {
BKTree bkTree = new BKTree();
// 构建词典
String[] dictionary = {
"apple", "apples", "apply", "application", "applicable",
"banana", "bandana", "band", "banner", "bank",
"cat", "cut", "cute", "cater", "catch",
"dog", "dig", "dug", "dodge", "doing",
"elephant", "elegant", "element", "elevator", "eleven",
"fish", "fishing", "dish", "wish", "finish",
"great", "grape", "grate", "gratitude", "grateful",
"hello", "help", "helpful", "helm", "health",
"internet", "internal", "interval", "interest", "interface",
"java", "javascript", "javelin", "jaw", "jar",
"kite", "kit", "kitchen", "kitten", "knit",
"language", "languish", "languid", "languor", "linguist",
"mouse", "mousse", "moose", "mood", "move",
"name", "naming", "namesake", "namely", "nation",
"orange", "origin", "original", "originate", "organ",
"people", "peoples", "pebble", "pedal", "pepper",
"queen", "query", "quest", "question", "queue",
"rabbit", "rabid", "rabbits", "race", "rack",
"search", "searches", "searched", "searching", "season",
"tree", "trie", "tried", "trial", "triangle",
"unique", "unit", "unite", "united", "unity",
"video", "view", "viewer", "viewing", "vivid",
"water", "waiter", "waiting", "watcher", "wedding",
"xenon", "xerox", "xylophone",
"yellow", "yell", "yelling", "yelled",
"zebra", "zero", "zest", "zoning"
};
System.out.println("=== 构建BK树词典 ===");
long start = System.currentTimeMillis();
bkTree.addAll(Arrays.asList(dictionary));
long buildTime = System.currentTimeMillis() - start;
System.out.println("词典大小: " + bkTree.size() + " 词");
System.out.println("构建时间: " + buildTime + "ms");
// 拼写纠错测试
String[] misspelled = {"aple", "bananna", "cater", "dug", "elefant",
"fsh", "grat", "helo", "intenet", "javscript",
"kichen", "languge", "mose", "nme", "orrange",
"peple", "qury", "rabit", "serch", "trie",
"unque", "vidio", "watr", "yelow", "zbra"};
System.out.println("\n=== 拼写纠错测试（编辑距离≤2） ===");
for (String query : misspelled) {
List<MatchResult> matches = bkTree.search(query, 2);
System.out.printf("'%s' -> %s%n", query,
matches.isEmpty() ? "无匹配" : matches.subList(0, Math.min(3, matches.size())));
}
// 性能对比：BK树 vs 暴力搜索
System.out.println("\n=== 性能对比 ===");
String testQuery = "aple";
int iterations = 1000;
start = System.currentTimeMillis();
for (int i = 0; i < iterations; i++) {
bkTree.search(testQuery, 2);
}
long bkTime = System.currentTimeMillis() - start;
start = System.currentTimeMillis();
for (int i = 0; i < iterations; i++) {
for (String word : dictionary) {
levenshteinDistance(testQuery, word);
}
}
long bruteTime = System.currentTimeMillis() - start;
System.out.println("BK树搜索 " + iterations + " 次: " + bkTime + "ms");
System.out.println("暴力搜索 " + iterations + " 次: " + bruteTime + "ms");
System.out.printf("加速比: %.2fx%n", (double) bruteTime / bkTime);
}
}
复杂度分析
- 建树时间复杂度：$O(n^2 \cdot L^2)$，其中 $n$ 是词典大小，$L$ 是平均单词长度。每插入一个词需要与路径上的节点计算编辑距离。
- 搜索时间复杂度：平均情况下为 $O(\log n \cdot L^2)$，最坏情况下为 $O(n \cdot L^2)$。三角不等式剪枝在词典分布均匀时能大幅减少搜索空间。
- 空间复杂度：$O(n)$，每个词对应一个节点。
算法特点与适用场景
优点：
– 利用度量空间性质实现高效剪枝，查询远快于暴力搜索
– 支持任意度量距离函数，不限于编辑距离
– 动态插入方便，无需重建整个索引
缺点：
– 树的平衡性取决于插入顺序，最坏情况下退化为链表
– 编辑距离计算本身有一定开销
– 对超长文本效率较低
适用场景：搜索引擎拼写建议、IDE代码补全、DNA序列比对、指纹/声纹模糊匹配、多语言近似字符串检索等。
