দুটি স্ট্রিংয়ের লেভেনস্টাইন ডিস্ট্যান্স (Levenshtein distance) বলতে এক স্ট্রিংকে অন্য স্ট্রিংয়ে রূপান্তর করতে ন্যূনতম কতগুলো এডিট (edit) অপারেশন দরকার সেটি বোঝায়। এডিট অপারেশন হলো: ইনসার্শন (insertion), ডিলিশন (deletion), বা একটি ক্যারেক্টার সাবস্টিটিউশন (substitution)।
উদাহরণ: "cat" এবং "mat"-এর লেভেনস্টাইন ডিস্ট্যান্স ১ কারণ:
cat -> mat (c কে m দিয়ে সাবস্টিটিউশন)
নিচে লেভেনস্টাইন ডিস্ট্যান্স কম্পিউট করার C++ প্রোগ্রাম দেওয়া হলো।
এলগরিদম
Begin
স্ট্রিংগুলো ইনপুট নিন এবং তাদের দৈর্ঘ্য বের করুন।
For i = 0 to l1
dist[0][i] = i
For j = 0 to l2
dist[j][0] = j
For j = 1 to l1
For i = 1 to l2
if(s1[i-1] == s2[j-1])
track = 0
else
track = 1
done
t = MIN((dist[i-1][j]+1), (dist[i][j-1]+1))
dist[i][j] = MIN(t, (dist[i-1][j-1]+track))
Done
Done
প্রিন্ট লেভেনস্টাইন ডিস্ট্যান্স: dist[l2][l1]
End
উদাহরণ
#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;
#define MIN(x,y) ((x) < (y) ? (x) : (y)) // দুই মান মধ্যে মিনিমাম
int main() {
int i, j, l1, l2, t, track;
int dist[50][50];
// স্ট্রিং ইনপুট
char s1[] = "tutorials";
char s2[] = "point";
// স্ট্রিং দৈর্ঘ্য
l1 = strlen(s1);
l2 = strlen(s2);
for(i = 0; i <= l1; i++) {
dist[0][i] = i;
}
for(j = 0; j <= l2; j++) {
dist[j][0] = j;
}
for (j = 1; j <= l1; j++) {
for(i = 1; i <= l2; i++) {
if(s1[i-1] == s2[j-1]) {
track = 0;
} else {
track = 1;
}
t = MIN((dist[i-1][j]+1), (dist[i][j-1]+1));
dist[i][j] = MIN(t, (dist[i-1][j-1]+track));
}
}
cout << "The Levenshtein distance is:" << dist[l2][l1];
return 0;
}
আউটপুট
The Levenshtein distance is: 8
