इस खंड में हम देखेंगे कि वैगनर और फिशर एल्गोरिथम का उपयोग करके दो स्ट्रिंग्स की तुलना कैसे की जाती है। इस एल्गोरिथम का उपयोग करके, हम यह पता लगा सकते हैं कि उन स्ट्रिंग्स से मेल खाने के लिए कितने न्यूनतम परिवर्तन आवश्यक हैं।
यह एक गतिशील प्रोग्रामिंग दृष्टिकोण है। यहां हम दो तारों से लेवेनशेटिन की दूरी को मापते हैं।
Input: Two strings “Support” & “Suppose” Output: Minimum number of required changes: 2
एल्गोरिदम
Wagnwe_Fisher(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