BK树（Burkhard-Keller Tree）原理与实现

BK树是一种专门用于快速查找与给定字符串相似（例如编辑距离在一定范围内）的字符串的数据结构。它由Burkhard和Keller于1973年提出，主要用于拼写检查、模糊搜索、生物信息学中的DNA序列比对等场景。

1. 核心思想：三角不等式

BK树的核心基于编辑距离（Levenshtein距离） 满足的三角不等式。
编辑距离 ED(A, B) 是指将字符串A转换为字符串B所需的最少单字符编辑操作（插入、删除、替换）次数。

三角不等式表明，对于任意三个字符串A, B, C：
|ED(A, B) - ED(B, C)| <= ED(A, C) <= ED(A, B) + ED(B, C)

BK树巧妙地利用了这个性质来减少在搜索时需要遍历的节点数量。

2. BK树的构建

BK树是一棵树，每个节点存储一个字符串。构建过程如下：

• 步骤1：选择根节点。 从字符串集合中任意选择一个字符串作为根节点。例如，我们有一个集合 {"book", "books", "cake", "boo", "cape", "cart"}，我们选择 "book" 作为根节点。
• 步骤2：插入其他节点。 对于要插入的每个新字符串 S_new，从根节点开始：
  1. 计算新字符串 S_new 与当前节点 S_current 的编辑距离 d = ED(S_new, S_current)。
  2. 检查当前节点是否存在一个子节点，该子节点与 S_current 的编辑距离恰好等于 d。
     • 如果存在：则以这个子节点作为新的当前节点，递归执行步骤2。
     • 如果不存在：就在当前节点下创建一个新的子节点，存储字符串 S_new，并记录它到父节点的距离为 d。

构建过程示例：
以集合 {"book", "books", "cake", "boo", "cape", "cart"} 为例，根节点为 "book"。

1. 插入 "books":

   • ED("book", "books") = 1（插入's'）。
   • 根节点没有距离为1的子节点。创建子节点 "books"，其到根节点的距离为1。

2. 插入 "cake":

   • ED("book", "cake") = 4（全部替换）。
   • 根节点没有距离为4的子节点。创建子节点 "cake"，其到根节点的距离为4。

3. 插入 "boo":

   • ED("book", "boo") = 1（删除'k'）。
   • 根节点已经有一个距离为1的子节点 "books"。现在，我们以 "books" 为当前节点，递归插入 "boo"。
   • ED("books", "boo") = 2（删除'k'和's'）。
   • "books" 节点没有距离为2的子节点。创建子节点 "boo"，其到 "books" 的距离为2。

4. 插入 "cape":

   • ED("book", "cape") = 4。
   • 根节点已经有一个距离为4的子节点 "cake"。以 "cake" 为当前节点，递归插入 "cape"。
   • ED("cake", "cape") = 1（'k'替换为'p'）。
   • "cake" 节点没有距离为1的子节点。创建子节点 "cape"。

5. 插入 "cart":

   • ED("book", "cart") = 4。
   • 根节点有距离为4的子节点 "cake"。以 "cake" 为当前节点，递归插入 "cart"。
   • ED("cake", "cart") = 2（'k'替换为'r'，'e'替换为't'）。
   • "cake" 节点没有距离为2的子节点。创建子节点 "cart"。

最终形成的BK树结构如下图所示（以距离标注边）：

          [book]
         /   |   \
     d=1/    |    \ d=4
       /     |     \
   [books]  ...   [cake]
     /           /     \
 d=2|        d=1/       \ d=2
    |          /         \
  [boo]    [cape]       [cart]

3. BK树的查询（相似字符串搜索）

查询目标是：给定一个查询字符串 Q 和一个最大容忍编辑距离 k，在BK树中找出所有与 Q 的编辑距离小于等于 k 的字符串。

搜索过程也是一个递归过程，从根节点开始：

• 步骤1：计算当前节点距离。 设当前节点为 S_current，计算 d_current = ED(Q, S_current)。

• 步骤2：收集结果。 如果 d_current <= k，那么当前节点字符串 S_current 就是一个满足条件的结果，将其加入结果集。

• 步骤3：递归搜索子节点。 根据三角不等式，我们只需要搜索那些有可能包含编辑距离 <=k 的字符串的子树。

  • 我们需要搜索的子树是那些到当前节点 S_current 的距离 d 满足以下条件的：
    d 的范围应该在 [d_current - k, d_current + k] 之间。

  为什么？
  根据三角不等式：对于当前节点的任意一个子节点 S_child，有 ED(S_current, S_child) = d（这是构建时确定的）。
  |ED(Q, S_current) - ED(S_current, S_child)| <= ED(Q, S_child)
  即 |d_current - d| <= ED(Q, S_child)
  我们希望 ED(Q, S_child) <= k。
  那么，一个必要条件是 |d_current - d| <= k。
  将其展开：-k <= d_current - d <= k -> d_current - k <= d <= d_current + k。

  所以，我们只需要递归地搜索那些 d 在 [d_current - k, d_current + k] 范围内的子节点。

查询过程示例：
在刚才建的树中，查询 Q = "car", k = 1（即查找与 "car" 编辑距离为0或1的单词）。

1. 从根节点 "book" 开始:

   • d_current = ED("car", "book") = 4。
   • 4 > 1，所以 "book" 不加入结果集。
   • 需要搜索的子树距离范围：[4-1, 4+1] = [3, 5]。
   • 查看根节点的子节点距离：有距离为1和4的。
   • 距离为1不在 [3,5] 范围内，跳过整个以 "books" 为根的子树（这大大减少了搜索量！）。
   • 距离为4在 [3,5] 范围内，所以递归搜索以 "cake" 为根的子树。

2. 进入节点 "cake":

   • d_current = ED("car", "cake") = 2。
   • 2 > 1，所以 "cake" 不加入结果集。
   • 需要搜索的子树距离范围：[2-1, 2+1] = [1, 3]。
   • 查看 "cake" 的子节点距离：有距离为1的 "cape" 和距离为2的 "cart"。
   • 距离1在 [1,3] 内，递归搜索 "cape"。
   • 距离2在 [1,3] 内，递归搜索 "cart"。

3. 进入节点 "cape":

   • d_current = ED("car", "cape") = 2（替换'p'为'r'，删除'e'？ 等等，正确计算：c-a-p-e -> c-a-r，替换'p'为'r'，删除'e'，距离为2）。
   • 2 > 1，所以 "cape" 不加入结果集。
   • 它没有子节点，返回。

4. 进入节点 "cart":

   • d_current = ED("car", "cart") = 1（插入't'）。
   • 1 <= 1，所以 "cart" 加入结果集。
   • 需要搜索的子树距离范围：[1-1, 1+1] = [0, 2]。
   • 它没有子节点，返回。

最终结果：["cart"]。 可以看到，我们成功地跳过了包含 "books" 和 "boo" 的整个分支，极大地提高了搜索效率。

4. 实现要点与复杂度分析

• 数据结构：每个节点通常包含三个部分：存储的字符串、一个记录到父节点距离的字段（在查询时非必须，但构建时有用）、一个字典（以距离为键，以子节点指针为值）。
• 时间复杂度：
  • 构建：最坏情况为 O(n²)（如果树退化成链），但平均情况下，如果字符串分布良好，高度接近 O(log n)，构建时间为 O(n log n)。
  • 查询：查询效率远高于暴力遍历所有字符串（O(n*L)，L为字符串平均长度）。其复杂度取决于容忍距离 k 和树的结构，通常远小于 O(n)。
• 优势：适用于大规模词典的模糊匹配，利用树结构和三角不等式剪枝，避免不必要的编辑距离计算。
• 劣势：查询性能与树的平衡性有关，而树的平衡性依赖于插入顺序和字符串集本身的特性。