โปรแกรม C++ ใช้ Wagner-Fisher Algorithm หาระยะทาง Levenshtein

ในส่วนนี้เราจะดูวิธีเปรียบเทียบสตริงสองตัวด้วยอัลกอริทึม Wagner และ Fisher โดยใช้อัลกอริทึมนี้ เราสามารถหาจำนวนการเปลี่ยนแปลงขั้นต่ำที่ต้องการเพื่อให้สตริงทั้งสองตรงกันได้

นี่คือแนวทาง Dynamic Programming ที่นี่เราวัดระยะทาง Levenshtein จากสตริงสองตัว

Input: สตริงสองตัว "Support" & "Suppose"
Output: จำนวนการเปลี่ยนแปลงขั้นต่ำ: 2

อัลกอริทึม

Wagnwe_Fisher(str1, str2)

Input: สตริงสองตัว str1 และ str2
Output: จำนวนการเปลี่ยนแปลงขั้นต่ำ

l1 := ความยาวของ str1, และ l2 = ความยาวของ str2
กำหนดเมทริกซ์ d ขนาด (l1 * l2)
เติมแถวแรกของ d ด้วยตัวเลข 0 ถึง l1 - 1 และเติมคอลัมน์แรกด้วย 0 ถึง l2 - 1
for j in range 1 ถึง l1 ทำ
    for i in range 1 ถึง l2 ทำ
        ถ้า str1[i - 1] = str2[j - 1] แล้ว
            tracker := 1
        ไม่เช่นนั้น
            tracker := 0
        temp := ค่าต่ำสุดของ d[i - 1, j] + 1 และ d[i, j-1] + 1
        d[i, j] = ค่าต่ำสุดของ temp และ (d[i - 1, j - 1] + tracker)
    จบ for i
จบ for j
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