Cây BK hay cây Burkhard là một dạng cấu trúc dữ liệu thường được sử dụng để thực hiện kiểm tra chính tả dựa trên khoảng cách Levenshtein. Nó cũng được sử dụng để kết hợp chuỗi Tính năng tự động sửa có thể được sử dụng để tạo cấu trúc dữ liệu này. Giả sử chúng ta có một số từ trong từ điển và chúng ta cần kiểm tra một số từ khác để tìm lỗi chính tả. Chúng ta cần có một tập hợp các từ gần với từ đã cho mà chúng ta cần kiểm tra chính tả. Ví dụ, nếu chúng ta có từ "uck" Từ đúng có thể là (xe tải, vịt, vịt, hút). Do đó có thể sửa lỗi chính tả bằng cách xóa một từ hoặc thêm một từ mới thay thế một chữ cái bằng một chữ cái thích hợp. Sử dụng khoảng cách chỉnh sửa làm tham số và kiểm tra cách viết bằng từ điển.
Giống như tất cả các cây khác, cây BK cũng bao gồm các nút và cạnh Các nút đại diện cho các từ trong từ điển. Cạnh chứa một số trọng số nguyên cung cấp cho chúng ta thông tin về khoảng cách chỉnh sửa từ nút này đến nút khác.
Xem xét từ điển với các từ {book, books, boo, cake, cape} -
Cây BK
Mỗi nốt trong BK Tree có đúng một nút con với cùng khoảng cách chỉnh sửa. Nếu chúng ta gặp một số va chạm trong khoảng cách chỉnh sửa trong khi chèn các nút, chúng ta sẽ truyền quá trình chèn cho đến khi chúng ta có được con phù hợp. Mỗi lần chèn đều bắt đầu với nút gốc, nút gốc có thể là bất kỳ từ nào. Cho đến bây giờ chúng ta đã học được Cây Bk là gì. Bây giờ chúng ta hãy xem làm thế nào để tìm đúng từ gần nhất. Trước hết, chúng ta cần đặt giá trị dung sai giá trị dung sai này không là gì ngoài khoảng cách chỉnh sửa tối đa giữa từ sai chính tả của tôi và từ đúng.
Để tìm từ đúng đủ điều kiện trong giới hạn dung sai, chúng tôi sử dụng quá trình lặp lại. Nhưng điều này có độ phức tạp cao hơn nên bây giờ cây BK đi vào hoạt động vì chúng ta biết rằng mỗi nút trong cây nhị phân được xây dựng dựa trên khoảng cách chỉnh sửa của nó từ nút cha. Vì vậy, chúng ta có thể đi trực tiếp từ nút gốc đến nút cụ thể nằm trong giới hạn dung sai. Nếu TOL là giới hạn dung sai và khoảng cách chỉnh sửa của nút hiện tại từ nút sai chính tả là dist. Vì vậy, bây giờ, chúng tôi sẽ chỉ lặp lại những phần tử con có khoảng cách chỉnh sửa trong phạm vi.
[dist - TOL, dist + TOL], điều này làm giảm độ phức tạp ở mức độ lớn hơn.
Ví dụ
Chương trình minh họa hoạt động -
#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