Giới thiệu BK Tree trong C++

BK-tree (cây Burkhard) là cấu trúc dữ liệu thường dùng để kiểm tra chính tả dựa trên khoảng cách Levenshtein. Cũng dùng cho tự động sửa (autocorrect) và khớp chuỗi. Giả sử có từ điển một số từ, cần kiểm tra từ khác có lỗi chính tả. Cần tập các từ gần với từ cần kiểm tra. Ví dụ từ "uck", từ đúng có thể là (truck, duck, suck). Lỗi chính tả sửa bằng cách xóa, thêm, thay thế ký tự. Dùng khoảng cách chỉnh sửa làm tham số kiểm tra với từ điển.

Giống các cây khác, BK-tree gồm nút và cạnh. Nút đại diện từ trong từ điển. Cạnh chứa trọng số nguyên cho biết khoảng cách chỉnh sửa từ nút này sang nút khác.

Ví dụ từ điển {book, books, boo, cake, cape}:

BK Tree

Mỗi nút BK-tree có đúng một nút con với cùng khoảng cách chỉnh sửa. Nếu gặp va chạm khoảng cách khi chèn, lan truyền chèn cho đến khi tìm được nút con phù hợp. Mọi chèn bắt đầu từ gốc, gốc có thể là từ bất kỳ.

Để tìm từ đúng gần nhất, đặt giá trị dung sai (tolerance) – khoảng cách chỉnh sửa tối đa giữa từ sai và từ đúng. Duyệt cây: từ gốc, tính khoảng cách dist đến từ cần kiểm tra. Chỉ duyệt các nhánh con có khoảng cách trong khoảng [dist - TOL, dist + TOL], giảm độ phức tạp đáng kể.

Ví dụ

Chương trình minh họa:

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

#define MAXN 100
#define TOL 2
#define LEN 10

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

Node RT;
Node tree[MAXN];
int ptr;

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

int editDistance(string& a, string& b) {
    int m = a.length(), n = b.length();
    int dp[m+1][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 (a[i-1] != b[j-1])
                dp[i][j] = min(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];
}

void insertValue(Node& root, Node& curr) {
    if (root.word == "") {
        root = curr;
        return;
    }
    int dist = editDistance(curr.word, root.word);
    if (tree[root.next[dist]].word == "") {
        ptr++;
        tree[ptr] = curr;
        root.next[dist] = ptr;
    } else {
        insertValue(tree[root.next[dist]], curr);
    }
}

vector<string> findCorrectSuggestions(Node& root, string& s) {
    vector<string> corrections;
    if (root.word == "")
        return corrections;
    int dist = editDistance(root.word, s);
    if (dist <= TOL)
        corrections.push_back(root.word);
    int start = dist - TOL;
    if (start < 0)
        start = 1;
    while (start < dist + TOL) {
        vector<string> temp = findCorrectSuggestions(tree[root.next[start]], s);
        for (auto i : temp)
            corrections.push_back(i);
        start++;
    }
    return corrections;
}

int main() {
    string dictionary[] = {"book","cake","cart","books", "boo"};
    ptr = 0;
    int size = sizeof(dictionary)/sizeof(string);
    for(int i=0; i<size; i++) {
        Node tmp = Node(dictionary[i]);
        insertValue(RT, tmp);
    }
    string word1 = "ok";
    string word2 = "ke";
    vector<string> match = findCorrectSuggestions(RT, word1);
    cout << "Correct words suggestions from dictionary for: " << word1 << endl;
    for (auto correctWords : match)
        cout << correctWords << endl;
    match = findCorrectSuggestions(RT, word2);
    cout << "Correct words suggestions from dictionary for: " << word2 << endl;
    for (auto correctWords : match)
        cout << correctWords << endl;
    return 0;
}

Đầu ra

Correct words suggestions from dictionary for: ok
book
boo
Correct words suggestions from dictionary for: ke
cake