BK ट्री या बर्कहार्ड ट्री (Burkhard tree) एक प्रकार की डेटा संरचना है जिसका उपयोग आमतौर पर लेवेंश्टाइन दूरी (Levenshtein distance) के आधार पर स्पेल चेक करने के लिए किया जाता है। इसका उपयोग स्ट्रिंग मिलान के लिए ऑटोकरेक्ट फीचर बनाने के लिए भी किया जाता है। मान लें कि हमारे पास एक डिक्शनरी में कुछ शब्द हैं और हमें स्पेलिंग त्रुटियों के लिए कुछ अन्य शब्दों की जांच करने की आवश्यकता है। हमें दिए गए शब्द के करीब शब्दों का एक संग्रह चाहिए जिसकी स्पेलिंग जांची जानी है। उदाहरण के लिए, यदि हमारे पास शब्द "uck" है तो सही शब्द (truck, duck, duck, suck) हो सकते हैं। इसलिए स्पेलिंग गलतियों को एक शब्द को हटाकर या एक नया शब्द जोड़कर या एक अक्षर को उपयुक्त अक्षर से बदलकर ठीक किया जा सकता है। डिक्शनरी के साथ स्पेलिंग की जांच करने के लिए संपादन दूरी (edit distance) को पैरामीटर के रूप में उपयोग करना।
अन्य सभी ट्री की तरह, BK ट्री में भी नोड्स और एज होते हैं। नोड्स डिक्शनरी में शब्दों को दर्शाते हैं। एज में कुछ पूर्णांक वजन होते हैं जो एक नोड से दूसरे नोड तक संपादन दूरी के बारे में जानकारी देते हैं।
{ book, books, boo, cake, cape } शब्दों वाले डिक्शनरी पर विचार करें -
BK ट्री
BK ट्री में हर नोड का ठीक एक चाइल्ड नोड होता है जिसकी संपादन दूरी समान होती है। यदि हम नोड्स डालते समय संपादन दूरी में कुछ टकराव (collision) का सामना करते हैं, तो हम सम्मिलन प्रक्रिया को तब तक प्रसारित (propagate) करेंगे जब तक हमें सही चाइल्ड न मिल जाए। प्रत्येक सम्मिलन रूट नोड से शुरू होता है, रूट नोड कोई भी शब्द हो सकता है। अब तक हमने सीखा कि BK ट्री क्या है। अब देखते हैं कि सही निकटतम शब्द कैसे ढूंढें। सबसे पहले, हमें सहनशीलता मान (tolerance value) सेट करने की आवश्यकता है। यह सहनशीलता मान मेरे गलत वर्तनी वाले शब्द और सही शब्द के बीच अधिकतम संपादन दूरी के अलावा कुछ नहीं है।
सहनशीलता सीमा के भीतर योग्य सही शब्द ढूंढने के लिए हम पुनरावृत्ति (iteration) की प्रक्रिया का उपयोग करते हैं। लेकिन इसकी जटिलता अधिक होती है इसलिए अब BK ट्री काम आता है क्योंकि हम जानते हैं कि बाइनरी ट्री में प्रत्येक नोड अपने पैरेंट से संपादन दूरी के आधार पर बनाया जाता है। तो हम सीधे रूट नोड से उस विशिष्ट नोड पर जा सकते हैं जो सहनशीलता सीमा के भीतर स्थित है। यदि 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 << "डिक्शनरी से सही शब्द सुझाव: " << word1 << endl;
for (auto correctWords : match)
cout << correctWords << endl;
match = findCorrectSuggestions(RT,word2);
cout << "डिक्शनरी से सही शब्द सुझाव: " << word2 << endl;
for (auto correctWords : match)
cout << correctWords << endl;
return 0;
}
आउटपुट
डिक्शनरी से सही शब्द सुझाव: ok book boo डिक्शनरी से सही शब्द सुझाव: ke cake
