BK树数据结构学习

BK树是一种基于树的数据结构，用来快速查找基于编辑距离的相似字符串匹配，比如拼写纠错或模糊查找。许多软件中的自动拼写纠错就是基于这个数据结构来实现的。

BK树中的每一个节点都是词典中的一个单词，而树中的边权重则表明叶子结点到根节点之间的编辑距离。例如从节点u到节点v的边上权重为w，那么w就是把u转化为v的编辑距离。

例如对于词典{"help", "hell", "hello"}，其对应的BK树如下：

BK树中的每个节点与子节点的编辑距离值都是唯一的，在插入节点的过程中如果编辑距离与当前节点和子节点之间的编辑距离相同，则考虑插入到下一个节点上。BK树每次插入均从根结点开始，根节点可以是词典中的任意一个单词。

例如向上述词典插入新单词shell时插入过程如下：

• 比较shell与根节点help的编辑距离，得到2
• 发现根节点已经存在编辑距离为2的子节点hello，因此尝试将shell插入到子节点hello上
• 比较shell与hello的编辑距离，因为hello没有编辑距离为2的子节点，因此插入

得到下图：

对于一个给定的TOL（tolerance value）作为编辑距离的上限，我们使用BK树来查找与给定节点N编辑距离小于等于TOL的过程如下：

计算给定节点N与根节点的编辑距离D，接着继续搜索与根节点编辑距离在[D - TOL, D + TOL]之间的子节点。重复这个过程知道找到所有满足条件的节点。

代码如下：

#include <vector>
#include <iostream>
#include <algorithm>

#define LEN 10
#define MAXN 1000
using namespace std;


struct Node {
    string word;
    // next[i]中保存的值为与word编辑距离为i的词在tree中的下标
    int next[2 * LEN];

    Node(string x): word(x) {
        for(int i=0; i<2*LEN; ++i) {
            next[i] = 0;
        }
    }

    Node():word() {}
};


Node RT;
int dp[2 * LEN][2 * LEN];
Node tree[MAXN];

int ptr = 0;

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

int editDistance(string &a, string &b) {
    // 动态规划获取最短编辑距离
    int a_len = a.length();
    int b_len = b.length();

    memset(dp, 0, sizeof(dp));
    for(int i=0; i<=a_len; ++i)
        dp[i][0] = i;
    for(int j=0; j<=b_len; ++j)
        dp[0][j] = j;

    for(int i=1; i<=a_len; ++i) {
        for(int j=1; j<=b_len; ++j) {
            if(a[i-1] != b[j-1]) {
                dp[i][j] = min(1 + dp[i-1][j],      // deletion
                               1 + dp[i][j-1],      // insertion
                               1 + dp[i-1][j-1]);   // replacement
            } else {
                dp[i][j] = dp[i-1][j-1];
            }
        }
    }
    return dp[a_len][b_len];
}

void add(Node &root, Node &cur) {
    if(root.word.length() == 0) {
        root = cur;
        return ;
    }

    int distance = editDistance(cur.word, root.word);

    if(tree[root.next[distance]].word.length() == 0) {
        // 若与root编辑距离为distance的位置没有节点，则将该节点标记为叶子结点
        ++ptr;
        tree[ptr] = cur;
        root.next[distance] = ptr;
    } else {
        add(tree[root.next[distance]], cur);
    }
}

vector<string> getSimilarWords(Node &root, string &s, int TOL) {
    vector<string> ret;

    if(root.word == "")
        return ret;

    int distance = editDistance(root.word, s);

    if(distance <= TOL)
        ret.push_back(root.word);

    int start = distance - TOL;
    if(start < 0)
        start = 1;

    while(start < distance + TOL) {
        vector<string> tmp = getSimilarWords(tree[root.next[start]], s, TOL);
        for(auto i : tmp) {
            ret.push_back(i);
        }
        ++start;
    }
    return ret;
}

int main() {
    string dictionary[] = {"hello", "help", "shel", "smell", "fell",
                           "felt", "oops", "pop", "oouch", "halt"};

    ptr = 0;
    int sz = sizeof(dictionary) / sizeof(string);

    for(int i=0; i<sz; ++i) {
        Node temp = Node(dictionary[i]);
        add(RT, temp);
    }

    string w1 = "ops";
    string w2 = "helt";
    vector<string> match = getSimilarWords(RT, w1, 2);
    cout << "similar words in dictionary for: " << w1 << ":" << endl;
    for(auto x : match) {
        cout << "- " << x << endl;
    }

    match = getSimilarWords(RT, w2, 2);
    cout << "similar words in dictionary for: " << w2 << ":" << endl;
    for(auto x : match) {
        cout << "* " << x << endl;
    }

    return 0;
}

BK树的应用：

一般提到BK树，了解这个数据结构的人都会想到单词纠错。而最近看到一遍博文讲述了如何使用BK树实现海量图片的去重（找到与给定图片编辑距离在上限范围内的所有图片并删除），其实仔细想一想对BK树应用的正确理解应该是基于相似度搜索结果，而不应该简单粗暴地理解为单词纠错（其实也是模糊查询）这种典型的应用场景，这样的认知有时候可能会限制我们在实际场景中对脑海中知识的变现。