इस सेक्शन में हम देखेंगे कि वैगनर-फिशर एल्गोरिदम का उपयोग करके दो स्ट्रिंग्स की तुलना कैसे करें। इस एल्गोरिदम का उपयोग करके, हम पता लगा सकते हैं कि उन स्ट्रिंग्स को मैच करने के लिए न्यूनतम कितने परिवर्तनों की आवश्यकता है।
यह एक डायनामिक प्रोग्रामिंग दृष्टिकोण है। यहां हम दो स्ट्रिंग्स से लेवेनश्टाइन दूरी मापते हैं।
इनपुट: दो स्ट्रिंग्स "Support" & "Suppose" आउटपुट: आवश्यक न्यूनतम परिवर्तनों की संख्या: 2
एल्गोरिदम
Wagner_Fisher(str1, str2)
इनपुट: दो स्ट्रिंग्स str1 और str2
आउटपुट: न्यूनतम परिवर्तनों की संख्या
l1 := str1 की लंबाई, और l2 = str2 की लंबाई
(l1 * l2) ऑर्डर का मैट्रिक्स d परिभाषित करें
d की पहली पंक्ति को 0 से l1-1 तक नंबर्स से भरें, और पहली कॉलम को 0 से l2-1 तक नंबर्स से भरें
j को 1 से l1 की रेंज में, करें
i को 1 से l2 की रेंज में, करें
यदि str1[i-1] = str2[j-1], तो
tracker := 0
अन्यथा
tracker := 1
temp := d[i-1, j] + 1 और d[i, j-1] + 1 का न्यूनतम
d[i, j] = temp और (d[i-1, j-1] + tracker) का न्यूनतम
किया
किया
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 Levenshtein distance " << d[str2_len][str1_len];
}
आउटपुट:
The Levenshtein distance 2