BK ট্রি বা বুর্কহার্ড ট্রি হলো একটি ডেটা স্ট্রাকচার যা সাধারণত লেভেনস্টাইন ডিস্ট্যান্স ভিত্তিক স্পেল চেক করতে ব্যবহৃত হয়। এটি স্ট্রিং ম্যাচিং অটোকরেক্ট ফিচারের জন্যও ব্যবহার করা যায়। ধরুন আমাদের একটি ডিকশনারিতে কিছু শব্দ আছে এবং আমরা কিছু অন্য শব্দের স্পেলিং ত্রুটি চেক করতে চাই। আমাদেরকে দেয়া শব্দের নিকটবর্তী শব্দগুলোর একটি সংগ্রহ দরকার। উদাহরণস্বরূপ, যদি আমাদের শব্দ থাকে "uck" তবে সঠিক শব্দ হতে পারে (truck, duck, suck)। অতএব স্পেলিং ত্রুটি একটি শব্দ মুছে বা নতুন শব্দ যোগ করে বা একটি লেটারকে উপযুক্ত লেটার দিয়ে রিপ্লেস করে ঠিক করা যায়। এডিট ডিস্ট্যান্সকে প্যারামিটার হিসেবে ব্যবহার করে ডিকশনারির সাথে スペル চেক করা হয়।
অন্য সব ট্রির মত BK ট্রিও নোড এবং এজ দিয়ে গঠিত। নোডগুলো ডিকশনারির শব্দগুলো রিপ্রেজেন্ট করে। এজে কিছু ইন্টিজার ওয়েইট থাকে যা এডিট ডিস্ট্যান্স সম্পর্কে তথ্য দেয় একটি নোড থেকে অন্যটি পর্যন্ত।
একটি ডিকশনারি বিবেচনা করুন যার শব্দগুলো { book, books, boo, cake, cape} −
BK ট্রি
BK ট্রিতে প্রতিটি নোডের ঠিক একটি চাইল্ড নোড থাকে যার এডিট ডিস্ট্যান্স একই। যদি নোড ইনসার্ট করার সময় এডিট ডিস্ট্যান্সে কলিশন হয়, তবে সঠিক চাইল্ড পাওয়া পর্যন্ত ইনসারশন প্রক্রিয়া প্রোপাগেট করুন। প্রতিটি ইনসারশন রুট নোড থেকে শুরু হয়, রুট নোড যেকোনো শব্দ হতে পারে। 지금까지 আমরা BK ট্রি কী সেটা শিখেছি। এখন দেখি কিভাবে সঠিক নিকটবর্তী শব্দ বের করা যায়। সবচেয়ে প্রথমে টলারেন্স ভ্যালু সেট করতে হবে। এই টলারেন্স ভ্যালু কেবল ম্যাক্সিমাম এডিট ডিস্ট্যান্স আমার ভুল লেখা শব্দ এবং সঠিক শব্দের মধ্যে।
টলারেন্স লিমিটের মধ্যে যোগ্য সঠিক শব্দ বের করার জন্য ইটেরেশন প্রক্রিয়া ব্যবহার করা হয়। কিন্তু এর কমপ্লেক্সিটি বেশি, তাই এখন 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<<"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
