オンライン文字列照合のためのWagnerおよびFisherアルゴリズムを実装するC++プログラム

このセクションでは、WagnerおよびFisherアルゴリズムを使用して2つの文字列を比較する方法を説明します。このアルゴリズムを使用すると、これらの文字列に一致するために必要な最小限の変更の数を見つけることができます。

これは動的計画法のアプローチです。ここでは、2本の弦からのレーベンシュタイン距離を測定します。

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

アルゴリズム

Wagnwe_Fisher（str1、str2）

入力 ：2つの文字列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