Chương trình C ++ để triển khai thuật toán tính toán khoảng cách Levenshtein

Khoảng cách Levenshtein giữa hai chuỗi có nghĩa là số lần chỉnh sửa tối thiểu cần thiết để chuyển một chuỗi này thành chuỗi kia, với các thao tác chỉnh sửa, tức là; chèn, xóa hoặc thay thế một ký tự.

Ví dụ: Levenshtein Khoảng cách giữa mèo và chiếu là 1 -

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

Đây là Chương trình C ++ để triển khai thuật toán tính toán Khoảng cách Levenshtein.

Thuật toán

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

Ví dụ

#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;
}

Đầu ra

The Levinstein distance is:8