दो स्ट्रिंग्स के बीच लेवेनश्टाइन डिस्टेंस का अर्थ है एक स्ट्रिंग को दूसरी में बदलने के लिए आवश्यक न्यूनतम एडिट्स की संख्या, जिसमें एडिट ऑपरेशन्स यानी इंसर्शन, डिलीशन, या सिंगल कैरेक्टर का सब्स्टीट्यूशन शामिल हैं।
उदाहरण: cat और mat के बीच लेवेनश्टाइन डिस्टेंस 1 है:
cat → mat ('c' का 'm' से सब्स्टीट्यूशन)
यहां लेवेनश्टाइन डिस्टेंस कंप्यूटिंग एल्गोरिदम को कार्यान्वित करने के लिए एक C++ प्रोग्राम है।
एल्गोरिदम
Begin
स्ट्रिंग्स को इनपुट के रूप में लें और उनकी लंबाई भी खोजें।
For i = 0 से l1 तक
dist[0][i] = i
For j = 0 से l2 तक
dist[j][0] = j
For j=1 से l1 तक
For i=1 से l2 तक
यदि s1[i-1] == s2[j-1]
track = 0
अन्यथा
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";
// स्ट्रिंग्स s1 और s2 की लंबाई स्टोर करें
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
लेवेनश्टाइन डिस्टेंस (एडिट डिस्टेंस) दो स्ट्रिंग्स के बीच अंतर मापता है। यह डायनामिक प्रोग्रामिंग का उपयोग करता है O(n*m) समय और स्थान में। अनुप्रयोगों में स्पेल चेकर्स, डीएनए अनुक्रम संरेखण, प्लेजियरिज्म डिटेक्शन और फजी स्ट्रिंग मैचिंग शामिल हैं। वैगनर-फिशर एल्गोरिदम इस DP दृष्टिकोण का मानक कार्यान्वयन है।