BK tree หรือ Burkhard tree เป็นโครงสร้างข้อมูลที่มักใช้ตรวจสอบการสะกดตามระยะทาง Levenshtein นอกจากนี้ยังใช้สำหรับสตริงที่ตรงกับคุณลักษณะการแก้ไขอัตโนมัติที่สามารถใช้สร้างโครงสร้างข้อมูลนี้ได้ สมมติว่าเรามีคำบางคำในพจนานุกรมและเราจำเป็นต้องตรวจสอบคำอื่นๆ เพื่อหาข้อผิดพลาดในการสะกดคำ เราจำเป็นต้องมีการรวบรวมคำที่ใกล้เคียงกับคำที่กำหนดซึ่งมีการตรวจสอบการสะกดคำ ตัวอย่างเช่น ถ้าเรามีคำว่า "uck" คำที่ถูกต้องอาจเป็นได้ (รถบรรทุก เป็ด เป็ด ห่วย) ดังนั้นการสะกดผิดสามารถแก้ไขได้โดยการลบคำหรือเพิ่มคำใหม่แทนที่ตัวอักษรด้วยตัวอักษรที่เหมาะสม ใช้ระยะแก้ไขเป็นพารามิเตอร์และตรวจสอบการสะกดด้วยพจนานุกรม
เช่นเดียวกับต้นไม้อื่น ๆ ต้นไม้ BK ยังประกอบด้วยโหนดและขอบด้วย โหนดเป็นตัวแทนของคำในพจนานุกรม ขอบมีน้ำหนักจำนวนเต็มบางตัวที่ให้ข้อมูลเกี่ยวกับการแก้ไขระยะทางจากโหนดหนึ่งไปยังอีกโหนดหนึ่ง
พิจารณาพจนานุกรมที่มีคำศัพท์ { book, books, boo, cake, cape} −
บีเคทรี
โน้ตทุกตัวใน BK Tree มีโหนดย่อยหนึ่งโหนดที่มีระยะการแก้ไขเท่ากัน หากเราพบการชนกันในระยะแก้ไขขณะแทรกโหนด เราจะเผยแพร่กระบวนการแทรกจนกว่าเราจะได้ลูกที่ถูกต้อง การแทรกทุกครั้งเริ่มต้นด้วยโหนดรูท โหนดรูทสามารถเป็นคำใดก็ได้ จนถึงตอนนี้เราได้เรียนรู้ว่า Bk Tree คืออะไร ทีนี้มาดูวิธีค้นหาคำที่ใกล้ที่สุดที่ถูกต้องกัน ก่อนอื่น เราต้องตั้งค่าความคลาดเคลื่อน ค่าความคลาดเคลื่อนนี้เป็นเพียงระยะการแก้ไขสูงสุดระหว่างคำที่สะกดผิดและคำที่ถูกต้อง
ในการค้นหาคำที่ถูกต้องที่มีสิทธิ์ภายในขีดจำกัดความอดทน เราใช้กระบวนการวนซ้ำ แต่สิ่งนี้มีความซับซ้อนสูงกว่า ดังนั้นตอนนี้ BK tree เริ่มดำเนินการ เนื่องจากเรารู้ว่าแต่ละโหนดในไบนารีทรีถูกสร้างขึ้นตามระยะการแก้ไขจากพาเรนต์ ดังนั้นเราจึงสามารถเปลี่ยนจากโหนดรูทไปยังโหนดเฉพาะที่อยู่ภายในขีดจำกัดความคลาดเคลื่อนได้โดยตรง ถ้า TOL เป็นขีดจำกัดความคลาดเคลื่อนและแก้ไขระยะทางของโหนดปัจจุบันจากโหนดที่สะกดผิดคือ dist ตอนนี้เราจะทำซ้ำเฉพาะเด็กที่มีระยะการแก้ไขอยู่ในช่วง
[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
