কম্পিউটার

C++ প্রোগ্রাম Levenshtein দূরত্ব কম্পিউটিং অ্যালগরিদম বাস্তবায়নের জন্য


দুটি স্ট্রিং এর মধ্যে Levenshtein দূরত্ব মানে একটি স্ট্রিংকে অন্যটিতে রূপান্তর করার জন্য ন্যূনতম সংখ্যক সম্পাদনা প্রয়োজন, যেমন সম্পাদনা ক্রিয়াকলাপগুলির সাথে; একটি একক অক্ষরের সন্নিবেশ, মুছে ফেলা বা প্রতিস্থাপন।

উদাহরণস্বরূপ: বিড়াল এবং মাদুরের মধ্যে লেভেনশটাইন দূরত্ব হল 1 −

cat mat(substitution of ‘c’ with ‘m’)

Levenshtein দূরত্ব কম্পিউটিং অ্যালগরিদম বাস্তবায়নের জন্য এখানে একটি C++ প্রোগ্রাম রয়েছে।

অ্যালগরিদম

Begin
   Take the strings as input and also find their length.
   For i = 0 to l1
      dist[0][i] = i
   For j = 0 to l2
      dist[j][0] = j
   For j=1 to l1
      For i=1 to l2
         if(s1[i-1] == s2[j-1])
            track= 0
         else
            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
   Print the Levinstein distance: dist[l2][l1]
End

উদাহরণ

#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;
#define MIN(x,y) ((x) < (y) ? (x) : (y)) //calculate minimum between two values
int main() {
   int i,j,l1,l2,t,track;
   int dist[50][50];
   //take the strings as input
   char s1[] = "tutorials";
   char s2[] = "point";
   //stores the lenght of strings s1 and 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 Levinstein distance is:"<<dist[l2][l1];
   return 0;
}

আউটপুট

The Levinstein distance is:8

  1. স্ট্রিং ম্যাচিংয়ের জন্য বিটাপ অ্যালগরিদম বাস্তবায়নের জন্য C++ প্রোগ্রাম

  2. বর্ধিত ইউক্লিডীয় অ্যালগরিদম বাস্তবায়নের জন্য C++ প্রোগ্রাম

  3. ইন্টারপোলেশন অনুসন্ধান অ্যালগরিদম বাস্তবায়নের জন্য C++ প্রোগ্রাম

  4. অ্যারে শাফলিংয়ের জন্য ফিশার-ইয়েটস অ্যালগরিদম বাস্তবায়নের জন্য C++ প্রোগ্রাম