บทนำ BK Tree ใน C++

BK tree หรือ Burkhard tree เป็นรูปแบบหนึ่งของโครงสร้างข้อมูลที่มักใช้สำหรับตรวจสอบการสะกดคำ (spell check) โดยอิงจาก Levenshtein distance (ระยะทางการแก้ไข) ยังใช้สำหรับการจับคู่สตริง (string matching) ฟีเจอร์ Autocorrect สามารถนำไปใช้กับโครงสร้างข้อมูลนี้ได้

สมมติว่าเรามีคำบางคำในพจนานุกรม และเราต้องการตรวจสอบคำอื่นๆ สำหรับข้อผิดพลาดในการสะกด เราต้องมีคอลเลกชันของคำที่ใกล้เคียงกับคำที่ต้องการตรวจสอบ เช่น ถ้าเรามีคำ "uck" คำที่ถูกต้องอาจเป็น (truck, duck, suck) ดังนั้นข้อผิดพลาดในการสะกดสามารถแก้ไขได้โดยการลบตัวอักษร เพิ่มตัวอักษรใหม่ หรือแทนที่ตัวอักษรด้วยตัวอักษรที่เหมาะสม โดยใช้ edit distance เป็นพารามิเตอร์ และตรวจสอบการสะกดกับพจนานุกรม

เหมือนต้นไม้ทุกประเภท BK tree ก็ประกอบด้วยโหนด (nodes) และขอบ (edges) โหนดแทนคำในพจนานุกรม ขอบมีน้ำหนักเป็นจำนวนเต็มซึ่งให้ข้อมูลเกี่ยวกับ edit distance จากโหนดหนึ่งไปอีกโหนดหนึ่ง

พิจารณาพจนานุกรมที่มีคำ { book, books, boo, cake, cape } −

BK Tree

ทุกโหนดใน BK Tree มี child node เพียงตัวเดียวที่มี edit distance เท่ากัน หากเราพบการชนกัน (collision) ของ edit distance ขณะแทรกโหนด เราจะแพร่กระจายกระบวนการแทรกจนกว่าจะได้ child ที่ถูกต้อง ทุกการแทรกเริ่มจาก root node ซึ่ง root node สามารถเป็นคำใดก็ได้

ตอนนี้เราได้เรียนรู้ BK Tree แล้ว มาดูวิธีหาคำที่ถูกต้องและใกล้เคียงที่สุด ก่อนอื่นเราต้องกำหนดค่า tolerance (ค่าทนทาน) ซึ่งคือ maximum edit distance ระหว่างคำที่สะกดผิดกับคำที่ถูกต้อง

เพื่อหาคำที่ถูกต้องที่อยู่ภายในขอบเขต tolerance เราใช้กระบวนการ iteration แต่สิ่งนี้มีความซับซ้อนสูง ดังนั้น BK tree จึงเข้ามาช่วย เนื่องจากเรารู้ว่าแต่ละโหนดใน binary tree ถูกสร้างขึ้นจาก edit distance จาก parent ดังนั้นเราสามารถไปยังโหนดเฉพาะที่อยู่ภายใน tolerance limit ได้โดยตรงจาก root node หาก TOL คือ tolerance limit และ edit distance ของโหนดปัจจุบันจากโหนดที่สะกดผิดคือ dist ดังนั้นเราจะวนลูปเฉพาะ child ที่มี edit distance อยู่ในช่วง

[dist - TOL, dist + TOL]

ซึ่งลดความซับซ้อนลงอย่างมาก

ตัวอย่างโปรแกรม

#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;
}

เอาต์พุต

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