온라인 문자열 일치를 위한 Wagner 및 Fisher 알고리즘을 구현하는 C++ 프로그램

이 섹션에서는 Wagner 및 Fisher 알고리즘을 사용하여 두 문자열을 비교하는 방법을 살펴봅니다. 이 알고리즘을 사용하여 해당 문자열을 일치시키는 데 필요한 최소 변경 수를 찾을 수 있습니다.

이것은 동적 프로그래밍 접근 방식입니다. 여기서 우리는 두 현에서 Levenshtein 거리를 측정합니다.

Input: Two strings “Support” & “Suppose”
Output: Minimum number of required changes: 2

알고리즘

Wagnwe_Fisher(str1, str2)

입력 :두 개의 문자열 str1 및 str2
출력 :최소 변경 횟수

l1 := length of str1, and l2 = length of str2
define a matrix d of order (l1 * l2)
fill first row of d with numbers from 0 to l1 – 1, and fill first column with numbers from 0 to l2- 1
for j in range 1 to l1, do
   for i in range 1 to l2, do
      if str1[i - 1] = str2[j - 1], then
         tracker := 1
      else
         tracker := 0
      temp := minimum of d[i – 1, j] + 1 and d[i, j-1] + 1
      d[i, j] = minimum of temp and (d[i – 1, j - 1]+ tracker)
   done
done
return 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 Levinstein distance " << d[str2_len][str1_len];
}

출력:

The Levinstein distance 2