এই বিভাগে আমরা দেখব কিভাবে Wagner এবং Fisher অ্যালগরিদম ব্যবহার করে দুটি স্ট্রিং তুলনা করা যায়। এই অ্যালগরিদম ব্যবহার করে, আমরা সেই স্ট্রিংগুলির সাথে মেলে কতগুলি ন্যূনতম পরিবর্তন প্রয়োজন তা খুঁজে পেতে পারি৷
এটি একটি গতিশীল প্রোগ্রামিং পদ্ধতি। এখানে আমরা দুটি স্ট্রিং থেকে Levenshtein দূরত্ব পরিমাপ করি।
Input: Two strings “Support” & “Suppose” Output: Minimum number of required changes: 2
অ্যালগরিদম
ওয়াগনওয়ে_ফিশার(str1, str2)
ইনপুট :দুটি স্ট্রিং str1 এবং str2
আউটপুট :পরিবর্তনের সর্বনিম্ন সংখ্যা
l1 := length of str1, and l2 = length of str2
define a matrix d of order (l1 * l2)
fill first row of d with numbers from 0 to l1 – 1, and fill first column with numbers from 0 to l2- 1
for j in range 1 to l1, do
for i in range 1 to l2, do
if str1[i - 1] = str2[j - 1], then
tracker := 1
else
tracker := 0
temp := minimum of d[i – 1, j] + 1 and d[i, j-1] + 1
d[i, j] = minimum of temp and (d[i – 1, j - 1]+ tracker)
done
done
return d[l2, l1] উদাহরণ কোড
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int d[100][100];
int min(int a, int b) {
return (a < b) ? a : b;
}
int main() {
int i,j,str1_len,str2_len,temp,tracker;
string str1 = "Support";
string str2 = "Suppose";
str1_len = str1.length();
str2_len = str2.length();
for(i = 0; i <= str1_len;i++)
d[0][i] = i;
for(j = 0;j <= str2_len;j++)
d[j][0] = j;
for (j = 1;j <= str1_len; j++) {
for(i = 1;i <= str2_len;i++) {
if(str1[i-1] == str2[j-1]) {
tracker = 0;
} else {
tracker = 1;
}
temp = min((d[i-1][j]+1),(d[i][j-1]+1));
d[i][j] = min(temp,(d[i-1][j-1]+tracker));
}
}
cout << "The Levinstein distance " << d[str2_len][str1_len];
} আউটপুট:
The Levinstein distance 2
