বিকে ট্রি বা বুরখার্ড ট্রি হল ডেটা স্ট্রাকচারের একটি রূপ যা সাধারণত লেভেনশটাইন দূরত্বের উপর ভিত্তি করে বানান পরীক্ষা করতে ব্যবহৃত হয়। এটি স্ট্রিং ম্যাচিং এর জন্যও ব্যবহার করা হয় স্বয়ংক্রিয় সংশোধন বৈশিষ্ট্যটি এই ডেটা কাঠামো তৈরি করতে ব্যবহার করা যেতে পারে। ধরা যাক আমাদের একটি অভিধানে কিছু শব্দ আছে এবং আমাদের বানান ত্রুটির জন্য অন্য কিছু শব্দ পরীক্ষা করতে হবে। আমাদের প্রদত্ত শব্দের কাছাকাছি শব্দের একটি সংগ্রহ থাকা দরকার যার বানান পরীক্ষা করতে হবে। উদাহরণস্বরূপ, যদি আমাদের কাছে "uck" শব্দ থাকে তবে সঠিক শব্দটি হতে পারে (ট্রাক, হাঁস, হাঁস, চুষা)। তাই বানান ভুল সংশোধন করা যেতে পারে একটি শব্দ মুছে দিয়ে বা একটি উপযুক্ত অক্ষর দ্বারা একটি অক্ষর প্রতিস্থাপন করে একটি নতুন শব্দ যোগ করে। একটি প্যারামিটার হিসাবে সম্পাদনা দূরত্ব ব্যবহার করা এবং অভিধানের সাথে বানান পরীক্ষা করা।
অন্য সব গাছের মতো, বিকে ট্রিতেও নোড এবং প্রান্ত রয়েছে নোডগুলি একটি অভিধানে শব্দগুলিকে উপস্থাপন করে প্রান্তটিতে কিছু পূর্ণসংখ্যা ওজন রয়েছে যা আমাদের একটি নোড থেকে অন্য নোডের দূরত্ব সম্পাদনা সম্পর্কে তথ্য দেয়৷
{বুক, বই, বু, কেক, কেপ} −
শব্দ সহ একটি অভিধান বিবেচনা করুন
বিকে ট্রি
BK Tree-এর প্রতিটি নোটে একই সম্পাদনা দূরত্ব সহ একটি চাইল্ড নোড রয়েছে। যদি আমরা নোড সন্নিবেশ করার সময় সম্পাদনা দূরত্বে কিছু সংঘর্ষের সম্মুখীন হই, আমরা সঠিক সন্তান না পাওয়া পর্যন্ত সন্নিবেশ প্রক্রিয়াটি প্রচার করব। প্রতিটি সন্নিবেশ রুট নোড দিয়ে শুরু হয় রুট নোড যেকোনো শব্দ হতে পারে। এখন পর্যন্ত আমরা Bk Tree কি তা জেনেছি। এখন দেখা যাক কিভাবে সঠিক নিকটতম শব্দ খুঁজে বের করা যায়। প্রথমত, আমাদের সহনশীলতার মান নির্ধারণ করতে হবে এই সহনশীলতার মান আমার ভুল বানান এবং সঠিক শব্দের মধ্যে সর্বাধিক সম্পাদনা দূরত্ব ছাড়া কিছুই নয়৷
সহনশীলতা সীমার মধ্যে যোগ্য সঠিক শব্দ খুঁজে পেতে আমরা পুনরাবৃত্তি প্রক্রিয়া ব্যবহার করি। কিন্তু এটির একটি উচ্চতর জটিলতা রয়েছে তাই এখন 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
