编辑距离 · 三角不等式 · 剪枝

BK-tree · 模糊查询如何剪枝

输入时打错一个字，如何从几万个词里快速找出「最相近」的几个候选？朴素做法是拿输入的词与词典里每一个词都算一次编辑距离—— $O(n)$ 次，词典一大就慢。BK-tree 把词典组织成一棵树，利用编辑距离的一条几何性质（三角不等式），查询时剪掉整棵不可能命中的子树，通常只需访问少数几个节点即可得到结果。先理解它依赖的编辑距离以及剪枝成立的依据，再逐词建树观察孩子如何按距离挂载，最后单步查询看一条不等式如何剪掉大半棵树。每节都可修改输入、单步播放。三节：地基：编辑距离与三角不等式 → 建树 → 查询。

本系列约定： 节点画成药丸，里面是词；边上的数字 = 孩子到父亲的编辑距离（建树规则的 key）。查询时节点配色：黄 = 当前访问、绿 = 命中 (d ≤ T)、青 = 访问过但没命中、灰虚线 = 被剪掉的整棵子树。距离一律用 Levenshtein（增/删/改各记 1）。

1 · 地基：编辑距离，与剪枝凭什么成立

foundation · 编辑距离 + 三角不等式

BK-tree 整套机制都建在编辑距离上。先看清这个距离怎么算、再看清它满足的一条几何性质——正是这条性质让查询能「整棵子树地剪」。

1.1 · 编辑距离 (Levenshtein)：一格一格算出来

编辑距离 = 把词 A 改成词 B 所需的最少单字符操作次数，操作有三种：插入一个字符、删除一个字符、替换一个字符（各记 1）。它用一张 DP 表算：table[i][j] =「A 的前 i 个字符」变成「B 的前 j 个字符」的最小代价，每格取三个来源的最小值：

table[i][j] 取三个来源的最小值：

$table[i-1][j] + 1$ ——删除 A 的第 i 个字符
$table[i][j-1] + 1$ ——插入 B 的第 j 个字符
$table[i-1][j-1] + cost$ ——替换（字符相同则 cost=0，否则 1）

右下角那一格就是整词的编辑距离。

1.2 · 它是一个「度量」：满足三角不等式

编辑距离不只是个数字，它是一个度量 (metric)：非负、对称 (d(a,b)=d(b,a))、自身距离为 0，且满足三角不等式：

$d(a, c) \le d(a, b) + d(b, c)$ ——绕道 b 不可能比直达 c 更近。

把它变个形，就是 BK-tree 剪枝的全部依据。设我们正站在树里某个节点 node，手上的查询词是 q，已经算出 d = d(q, node)。对 node 的任意一个孩子 child（边权 e = d(child, node)），把三角不等式两头一夹：

$d(q, child) \ge d(q, node) - d(node, child) = d - e$ （下界）

$d(q, child) \le d(q, node) + d(node, child) = d + e$ （上界）

反过来读：一个真正命中的词（距 q 不超过 T）若藏在某条边权 e 的孩子子树里，那么必然 $|d - e| \le T$ ，即 $e \in [d - T, d + T]$ 。

所以：边权落在 $[d-T, d+T]$ 之外的孩子，整棵子树都不可能有命中点——直接剪掉。

拖动下面的 d（查询词到当前节点的距离）和 T（容忍度），看那个「存活窗口」 $[d-T, d+T]$ 在数轴上怎么移动、怎么撑大；圆点是某节点的几条孩子边权，实心 = 落在窗口内要去查、空心 = 被剪掉。

窗口越窄，剪得越多。 T 越小（容忍越少错）, $[d-T, d+T]$ 越窄，能存活的孩子越少、剪掉的越多、查得越快；T 越大窗口越宽，要走的子树越多。这就是 BK-tree 查询代价随 T 增长的直观来源。

2 · 建树：孩子按「到父亲的距离」挂

algorithm · 逐词建树

BK-tree 的结构规则只有一条，插入就是反复套用它：

第一个词直接当根。之后每插入一个新词 w，从根出发：

其一，算距离 d = d(w, cur)——新词到当前节点的编辑距离。

其二，看这个距离有没有被占：

若 cur 在距离 d 处已有孩子 → 沿那条边下降到那个孩子，把它当新的 cur 继续（距离冲突，往深处推）;
若距离 d 处还空着 → 把 w 挂成 cur 的新孩子，边权 = d，插入完成。

同一个父亲下，每个距离至多一个孩子——这正是 BK-tree 能用「边权 = 距离」来索引、查询时按窗口剪枝的前提。

改词典即从空树开始逐步插入；用「下一步」/「播放」逐帧观察，旁白说清每一步是在算距离、下降还是挂新孩子，代码面板同步高亮当前行。

边权不是字符差，是「到直接父亲」的距离。 注意 boon 最终挂在 boo 下而不是根 book 下——因为它到 book 的距离 (1) 撞上了已存在的 books，于是下降到 books、再下降到 boo，最后落在 boo 的距离 1 处。同一条距离被占用，就把后来者往更深处推，这就是树长高的原因。

3 · 查询：一条不等式剪去大半棵树

algorithm · 单步查询（剪枝主场）

这是 BK-tree 的核心价值所在。要找出词典里所有「距查询词 q 不超过 T」的词——朴素做法逐个比较 $O(n)$ 次，BK-tree 靠三角不等式（见地基：编辑距离与三角不等式）把整棵子树成片剪掉。在每个访问到的节点上：

其一，算距离 d = d(q, node)。

其二，命中判定： 若 $d \le T$ ，当前节点的词就是一个结果，收进候选。

其三，剪枝下降： 由三角不等式，任何命中点到本节点的距离都必落在 $[d-T, d+T]$ 内——所以只递归边权落在这个窗口的孩子，其余孩子的整棵子树直接剪掉，完全不访问。

修改查询词与 T 后即时重算，用「下一步」逐步观察：每访问一个节点，算出 d、画出存活窗口、标出哪些孩子边下降、哪些子树被剪。默认 caqe (T=1)——它只访问 4 个节点即可得到结果。

剪枝的效果。 默认 caqe (T=1) 在根 book 处算出 d=4，窗口 [3,5]——根的两个孩子边权是 1 (books) 和 4 (cake)，只有 4 落在窗口里。于是整棵 books 子树（books / boo / boon / cook 四个词）被整体剪掉，只下降到 cake 一侧，最终只访问 4 个节点就找出 cake 与 cape。词典越大、T 越小，被剪掉的比例越高。