BK-tree · 编辑距离 + 三角不等式

BK-tree：在词典里查找编辑距离相近的词

本页使用的「距离」是「编辑距离」一页介绍的 Levenshtein 距离。场景：用户把 receive 打成 recieve，我们想在词典里找出与目标编辑距离 ≤ k 的所有词（拼写纠错、模糊搜索、OCR 后处理）。BK-tree(Burkhard–Keller Tree)正为此而生：它把词典组织成一棵树，靠编辑距离 + 三角不等式在查询时剪掉大片不可能的子树。

前提是用一个满足三角不等式的距离函数，本页取 Levenshtein 编辑距离（插入 / 删除 / 替换各算 1）。结构上：每个节点存一个词，边权 = 父子两词的距离，子节点按「与父节点的距离」分桶（同一距离只挂一个孩子，再往下递归）。

1 · 按距离分桶的插入

插入 $w$ ：从 root 出发算 d = distance(w, 当前节点)。当前节点已有距离为 d 的子节点 → 下沉到它继续比；没有 → 在距离 d 处新建子节点挂上。

图 1-1 · BK-tree 的逐词插入，边上标注到父节点的编辑距离。可换词表观察树形如何随插入顺序变化。

2 · 第二步：查询 ≤ k——靠三角不等式剪枝

在节点 v 处算 d = distance(target, v.word)：若 $d \le k$ 就收入结果。再往下时不必遍历所有子节点——由三角不等式 $|d(v, child) - d(target, v)| \le d(target, child)$ ，只有边权落在 $[d-k, d+k]$ 的子树才可能命中，其余整棵剪掉。

图 2-1 · 查询距离不超过

k

的词，被三角不等式剪掉的子树标灰。可调

k

观察剪枝范围的变化。

剪枝的效果：把 target=bool, k=1 跑完：从 root 起 d(bool,book)=1，边权 4 的整条 cake / cape / hat 子树一次性被剪掉——根本不用算它们的距离。命中 book / boon / boot。把 k 调大，可达范围 $[d-k, d+k]$ 变宽，剪掉的就少了。

3 · 复杂度与适用边界

环节	量级
构建	O(N log N) 量级（取决于分布）
查询	最好 ≈ O(log N)，最坏退化到 O(N)
瓶颈	每次比较都要算一遍编辑距离(本身 O(len²))

适合：拼写纠错( $recieve\to receive$ )、模糊搜索 / 补全、OCR·ASR 后处理纠错、相似串去重。取舍：编辑距离计算开销大、数据分布差时退化明显，不适合超大规模。工程上的常见替代 / 搭配：

方案	特点
Trie	精确 / 前缀匹配快，不擅模糊
BK-tree	编辑距离的模糊匹配，小词典（< 10 万）效果好
n-gram + 倒排	大规模（> 100 万）工程上更常用
Levenshtein 自动机	理论更强，但实现复杂

工程实践：限制最大 $k$ （一般 ≤ 2）、缓存 distance 计算、必要时换更合适的距离（如 Damerau–Levenshtein 把「相邻换位」也算 1）。