C++ 中的 BK 树

2025 年 5 月 15 日 | 阅读 10 分钟

引言

BK 树，或称 Burkhard-Keller 树，是一种专为高效近似字符串匹配而设计的数据结构。它特别适用于拼写检查器、自动完成和 DNA 测序等应用，在这些应用中，查找与给定查询相近的单词或序列至关重要。BK 树 能够快速搜索指定编辑距离内的元素，使其成为处理传统精确匹配算法无法满足的大型数据集的理想选择。

问题陈述

BK 树解决的主要问题是有效地查找数据集中与查询字符串具有给定编辑距离的所有元素。编辑距离，通常是 Levenshtein 距离，衡量将一个字符串转换为另一个字符串所需的最少单字符编辑（插入、删除或替换）次数。这在信息检索、生物信息学和错误纠正等领域至关重要。

历史

BK 树的概念由 **Walter Burkhard** 和 **Robert Keller** 于 1973 年在其题为“某种最佳匹配文件搜索方法”的论文中首次提出。BK 树利用度量空间的性质，特别是三角不等式，来减少查找近似匹配所需的比较次数。

BK 树如何工作？

1. 插入

树以包含第一个元素的根节点开始。
为了插入新元素，请计算其与根的编辑距离。
遍历树：在每个节点，计算与节点值的距离，然后沿着对应于该距离的子节点路径前进。
之后，一旦到达叶节点或适当的子节点不存在，就将新元素插入到合适的位置。

2. 搜索

给定一个查询和一个允许的最大距离，从根节点开始。
在每个节点，计算与查询的距离。
遍历子节点，这些子节点的与节点值的距离落在允许范围内（当前距离减去最大距离到当前距离加上最大距离）。
收集所有在允许范围内的节点。

例如

考虑使用字符串“book”、“back”和“books”构建一个 BK 树。首先插入“book”作为根。然后，插入“back”（与“book”距离为 2），创建一个子节点。接下来，插入“books”（与“book”距离为 1），添加另一个子节点。

搜索与“boon”距离为 1 的字符串

从 **“book”** 开始（距离为 1）。
移动到 **“books”**（距离为 2，不在范围内）。
不存在其他相关子节点，因此结果是“book”。

示例 1

下面是使用 Levenshtein 距离的 C++ BK 树的简单实现

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
#include <algorithm>

class BKTree {
private:
    struct Node {
        std::string word;
        std::unordered_map<int, Node*> children;
        Node(const std::string& w) : word(w) {}
    };

    Node* root;

    int levenshteinDistance(const std::string& s1, const std::string& s2) {
        int m = s1.size();
        int n = s2.size();
        std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1));
        for (int i = 0; i <= m; ++i) dp[i][0] = i;
        for (int j = 0; j <= n; ++j) dp[0][j] = j;

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s1[i - 1] == s2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + std::min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
                }
            }
        }
        return dp[m][n];
    }

    void insert(Node* node, const std::string& word) {
        int distance = levenshteinDistance(node->word, word);
        auto it = node->children.find(distance);
        if (it != node->children.end()) {
            insert(it->second, word);
        } else {
            node->children[distance] = new Node(word);
        }
    }

    void search(Node* node, const std::string& query, int maxDistance, std::vector<std::string>& results) {
        int distance = levenshteinDistance(node->word, query);
        if (distance <= maxDistance) {
            results.push_back(node->word);
        }
        for (auto& [dist, child] : node->children) {
            if (dist >= distance - maxDistance && dist <= distance + maxDistance) {
                search(child, query, maxDistance, results);
            }
        }
    }

public:
    BKTree() : root(nullptr) {}

    void insert(const std::string& word) {
        if (!root) {
            root = new Node(word);
        } else {
            insert(root, word);
        }
    }

    std::vector<std::string> search(const std::string& query, int maxDistance) {
        std::vector<std::string> results;
        if (root) {
            search(root, query, maxDistance, results);
        }
        return results;
    }
};

int main() {
    BKTree tree;
    tree.insert("book");
    tree.insert("back");
    tree.insert("books");

    std::string query = "boon";
    int maxDistance = 1;
    auto results = tree.search(query, maxDistance);

    std::cout << "Words within distance " << maxDistance << " from \"" << query << "\":" << std::endl;
    for (const auto& word : results) {
        std::cout << word << std::endl;
    }

    return 0;
}

输出

Words within distance 1 from "boon":
book

说明

节点结构：在此示例中，每个节点包含一个单词以及一个由当前节点单词与其距离索引的子节点映射。
Levenshtein 距离： levenshteinDistance 函数计算两个字符串之间的编辑距离。
插入函数： insert 函数通过根据编辑距离查找适当的位置来将新单词添加到树中。
搜索函数： search 函数查找查询字符串在指定距离内的所有单词，递归地检查落在距离范围内的节点。
BK 树的结构确保了高效的插入和搜索，并利用度量空间的性质来最大限度地减少不必要的比较。

插入复杂度

时间复杂度
- 将单词插入 BK 树需要将新单词与树中已有的单词进行比较。在最坏的情况下，每次插入都需要从根到叶节点遍历树。
- 设 d 为单词之间的平均距离，n 为树中的单词数。
- 单次插入的最坏情况时间复杂度为 **O(d⋅n)**，其中 d 是计算两个单词之间编辑距离的时间。
- 对于 Levenshtein 距离，对于两个长度为 m 的单词，d 为 **O(m^2)**，使得整体最坏情况插入时间为 **O(m^2⋅n)**。
空间复杂度
- 每个节点存储一个单词和一个由距离索引的子节点映射。
- 假设每个节点的平均分支因子为 b，则存储树的空间复杂度为 n 个单词的 **O(n)**。
- 距离映射需要额外的空间，但这通常与节点数量成正比，因此为 **O(n)**。

搜索复杂度

时间复杂度
- 搜索涉及遍历编辑距离落在指定范围内的树的部分。
- 设 k 为在指定编辑距离 r 内找到的单词数。
- 搜索时间复杂度取决于树的分支因子和深度。平均而言，它可以近似为 **O(b^r⋅d⋅n)**。
- 对于深度为 log n 的树和分支因子 b，平均搜索时间复杂度为 **O(b^r⋅m^2⋅log n)**（假设 Levenshtein 距离）。

总体复杂度

插入
- 时间：最坏情况为 **O(m^2⋅n)**。
- 空间：存储单词和树结构为 **O(n)**。
搜索
- 时间：平均为 **O(b^r⋅m^2⋅log n)**，其中 b 是分支因子，r 是编辑距离范围，mmm 是单词的长度。

示例 2

让我们举个例子来说明 C++ 中 BK 树的工作原理。

#include "bits/stdc++.h"
using namespace std;

// maximum number of words in wordList[]
#define MAX_WORDS 100

// defines the tolerance value
#define TOLERANCE 2

// defines maximum length of a word
#define MAX_LEN 10

struct TrieNode
{
    // stores the word of the current TrieNode
    string word;

    // links to other TrieNode in the trie
    int next[2*MAX_LEN];

    // constructors
    TrieNode(string x):word(x)
    {
        // initializing next[i] = 0
        for(int i=0; i<2*MAX_LEN; i++)
            next[i] = 0;
    }
    TrieNode() {}
};

// stores the root TrieNode
TrieNode root;

// stores every TrieNode of the trie
TrieNode trie[MAX_WORDS];

// index for current TrieNode of trie
int nodeIndex;

int minimum(int a, int b, int c)
{
    return min(a, min(b, c));
}

// Edit Distance
// Dynamic-Approach O(m*n)
int calculateEditDistance(string& a, string& b)
{
    int m = a.length(), n = b.length();
    int dp[m+1][n+1];

    // filling base cases
    for (int i=0; i<=m; i++)
        dp[i][0] = i;
    for (int j=0; j<=n; j++)
        dp[0][j] = j;

    // populating matrix using dp-approach
    for (int i=1; i<=m; i++)
    {
        for (int j=1; j<=n; j++)
        {
            if (a[i-1] != b[j-1])
            {
                dp[i][j] = minimum( 1 + dp[i-1][j], 
                                    1 + dp[i][j-1], 
                                    1 + dp[i-1][j-1] 
                                  );
            }
            else
                dp[i][j] = dp[i-1][j-1];
        }
    }
    return dp[m][n];
}

// adds current TrieNode to the trie
void addToTrie(TrieNode& rootNode, TrieNode& currentNode)
{
    if (rootNode.word == "")
    {
        // if it is the first TrieNode
        // then make it the root TrieNode
        rootNode = currentNode;
        return;
    }

    // get its calculateEditDistance from the root TrieNode
    int distance = calculateEditDistance(currentNode.word, rootNode.word);

    if (trie[rootNode.next[distance]].word == "")
    {
        /* if no TrieNode exists at this distance from root
        * make it child of root TrieNode*/

        // incrementing the pointer for current TrieNode
        nodeIndex++;

        // adding current TrieNode to the trie
        trie[nodeIndex] = currentNode;

        // currentNode as child of root TrieNode
        rootNode.next[distance] = nodeIndex;
    }
    else
    {
        // recursively find the parent for current TrieNode
        addToTrie(trie[rootNode.next[distance]], currentNode);
    }
}

vector<string> findSimilarWords(TrieNode& rootNode, string& s)
{
    vector<string> result;
    if (rootNode.word == "")
        return result;

    // calculating calculateEditDistance of s from rootNode
    int distance = calculateEditDistance(rootNode.word, s);

    // if distance is less than tolerance value
    // add it to similar words
    if (distance <= TOLERANCE) result.push_back(rootNode.word);

    // iterate over the string having tolerance
    // in range (distance-TOLERANCE , distance+TOLERANCE)
    int start = distance - TOLERANCE;
    if (start < 0)
        start = 1;

    while (start <= distance + TOLERANCE)
    {
        vector<string> temp =
            findSimilarWords(trie[rootNode.next[start]], s);
        for (auto i : temp)
            result.push_back(i);
        start++;
    }
    return result;
}

// driver program to run above functions
int main(int argc, char const *argv[])
{
    // word list
    string wordList[] = {"hell", "help", "shell", "smell",
                         "fell", "felt", "oops", "pop", "oouch", "halt"
                        };
    nodeIndex = 0;
    int listSize = sizeof(wordList)/sizeof(string);

    // adding wordList[] words on to trie
    for(int i=0; i<listSize; i++)
    {
        TrieNode temp = TrieNode(wordList[i]);
        addToTrie(root, temp);
    }

    string word1 = "ops";
    string word2 = "helt";
    vector<string> matches = findSimilarWords(root, word1);
    cout << "Similar words in dictionary for: " << word1 << ":\n";
    for (auto x : matches)
        cout << x << endl;

    matches = findSimilarWords(root, word2);
    cout << "Correct words in dictionary for " << word2 << ":\n";
    for (auto x : matches)
        cout << x << endl;

    return 0;
}

输出

similar words in dictionary for : ops:
oops
pop
Correct words in dictionary for helt:
hell
help
shell
fell
felt
halt

说明

库和宏
- #include "bits/stdc++.h": 它包含 C++ 竞赛编程中常用的一组标准库。
- #define MAXN 100: 它定义了字典中单词的最大数量。
- #define TOL 2: 它定义了容差值，指定了给定单词与字典中单词之间的最大允许编辑距离，以便将它们视为相似。
- #define LEN 10: 它定义了单词的最大长度。
数据结构
- struct Node: 它代表 trie 中的一个节点。它存储与节点关联的单词（string word）以及一个名为 next 的数组，用于存储 trie 中子节点的索引。
- Node RT: 它代表 trie 的根节点。
- Node tree[MAXN]: 一个用于存储 trie 所有节点的数组。
- int ptr: 一个指针，用于跟踪 trie 中的当前节点。
函数
- int min(int a, int b, int c): 它返回三个整数中的最小值。
- int editDistance(string& a, string& b): 它使用动态规划计算两个字符串之间的编辑距离。
- void add(Node& root, Node& curr): 它将一个节点添加到 trie 中。它计算当前单词与根单词之间的编辑距离，并相应地添加当前节点。
- vector <string> getSimilarWords(Node& root, string& s): 它检索与给定字符串相似的单词，范围在 TOL 指定的容差范围内。它递归地探索 trie 以查找相似的单词。
- main(): 主驱动函数。它使用一些示例单词初始化 trie，并为两个测试用例计算和打印相似的单词。

时间复杂度

很明显，时间复杂度主要取决于容差限制。我们将容差限制考虑为 2。现在，粗略估计，BK 树的深度将为 log n，其中 n 是字典的大小。因此，时间复杂度将为 **O(L1*L2*log n)**，其中 L1 是字典中单词的平均长度，L2 是拼写错误的长度。通常，L1 和 L2 会很小。

辅助空间

上述实现的**空间复杂度为 O(L1*L2)**，其中 L1 是字典中的单词数，L2 是单词的最大长度。

结论

总之，BK 树，以其发明者 Burkhard 和 Keller 命名，是一种优雅而高效的数据结构，旨在解决近似字符串匹配问题。它在需要检索指定编辑距离内的字符串的应用中表现出色，例如拼写检查、自动完成和生物信息学。

要点回顾

高效近似匹配： BK 树允许快速搜索与查询具有指定编辑距离的单词，使其适用于传统精确匹配不足的大型数据集。
Levenshtein 距离： BK 树常用于 Levenshtein 距离，它衡量将一个字符串转换为另一个字符串所需的最少单字符编辑次数。树结构利用此度量来有效地组织和搜索数据。

插入和搜索

插入涉及遍历树，根据新单词与其现有单词的距离找到正确的位置。
搜索利用三角不等式来限制比较次数，从而确保在给定编辑距离内高效地检索单词。

复杂度

时间复杂度：插入和搜索操作通常很高效，时间复杂度受平均单词长度和树结构的影响。
空间复杂度： BK 树需要与单词数量成比例的空间，并为管理子节点和距离映射提供额外的开销。

下一主题C++ 中的不区分大小写搜索

C++ 中的 BK 树

引言

问题陈述

历史

BK 树如何工作？

例如

示例 1

示例 2

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中的 BK 树

引言

问题陈述

历史

BK 树如何工作？

例如

示例 1

示例 2

结论

相关帖子

C++ 中的模拟退火算法

C++ 中的星形数

C++ 零法则

C++ std::chi_squared_distribution

C++ 中 N 位数阶梯数

C++ 类中的辅助函数

C++ 不同子序列

C++ 中的获取-释放语义

C++ 中的 std::memory_order 枚举

C++ Smarandache-Wellin 序列

订阅 Tpoint Tech

联系信息