Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में लेवेनश्टाइन डिस्टेंस कंप्यूटिंग एल्गोरिदम


दो स्ट्रिंग्स के बीच लेवेनश्टाइन डिस्टेंस का अर्थ है एक स्ट्रिंग को दूसरी में बदलने के लिए आवश्यक न्यूनतम एडिट्स की संख्या, जिसमें एडिट ऑपरेशन्स यानी इंसर्शन, डिलीशन, या सिंगल कैरेक्टर का सब्स्टीट्यूशन शामिल हैं।

उदाहरण: 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 दृष्टिकोण का मानक कार्यान्वयन है।

  1. - C++ प्रोग्राम: एक्सटेंडेड यूक्लिडियन एल्गोरिदम इम्प्लीमेंट करना

    एक्सटेंडेड यूक्लिडियन एल्गोरिदम दो संख्याओं का GCD निकालने का बस एक और तरीका है। इसमें ax + by = gcd(a, b) की गणना के लिए अतिरिक्त वेरिएबल्स हैं। यह कंप्यूटर प्रोग्राम में उपयोग करने के लिए अधिक कुशल है। एल्गोरिदम Begin वेरिएबल a, b, x और y घोषित करें gcdExtended(int a, int b, int *x, int

  1. - C++ प्रोग्राम: इंटरपोलेशन सर्च एल्गोरिदम लागू करना

    बाइनरी सर्च तकनीक के लिए, सूचियों को समान भागों में विभाजित किया जाता है। इंटरपोलेशन सर्चिंग तकनीक के लिए, प्रक्रिया इंटरपोलेशन फॉर्मूला का उपयोग करके सटीक स्थिति का पता लगाने का प्रयास करेगी। अनुमानित स्थान ढूंढने के बाद, यह उस स्थान का उपयोग करके सूची को अलग कर सकता है। चूंकि यह हर बार सटीक स्थान

  1. - C++ प्रोग्राम: फिशर-येट्स एल्गोरिदम से ऐरे शफलिंग

    फिशर-येट्स एल्गोरिदम फिशर-येट्स एल्गोरिदम ऐरे तत्वों का यादृच्छिक क्रमपरिवर्तन उत्पन्न करता है, यानी यह ऐरे के सभी तत्वों को निष्पक्ष रूप से शफल करता है। सभी क्रमपरिवर्तन समान रूप से संभावित होते हैं। C++ प्रोग्राम उदाहरण #include <iostream> #include <cstdlib> #include <ctime> us