Chương trình C++ triển khai thuật toán Wagner-Fisher khớp chuỗi trực tuyến

Trong phần này, chúng ta sẽ thấy cách so sánh hai chuỗi sử dụng thuật toán Wagner-Fisher. Sử dụng thuật toán này, chúng ta có thể tìm ra số lượng thay đổi tối thiểu cần thiết để khớp hai chuỗi đó.

Đây là một phương pháp quy hoạch động (dynamic programming). Ở đây chúng ta đo khoảng cách Levenshtein từ hai chuỗi.

Đầu vào: Hai chuỗi "Support" & "Suppose" 
Đầu ra: Số lượng thay đổi tối thiểu: 2

Thuật toán

Wagnwe_Fisher(str1, str2)

Đầu vào: Hai chuỗi str1 và str2
Đầu ra: Số lượng thay đổi tối thiểu

l1 := độ dài str1, và l2 = độ dài str2 
định nghĩa ma trận d cấp (l1 * l2) 
điền hàng đầu của d bằng số từ 0 đến l1 - 1, và cột đầu bằng số từ 0 đến l2 - 1 
với j trong khoảng 1 đến l1, thực hiện 
    với i trong khoảng 1 đến l2, thực hiện 
        nếu str1[i - 1] = str2[j - 1], thì 
            tracker := 1 
        ngược lại 
            tracker := 0 
        temp := min của d[i - 1, j] + 1 và d[i, j-1] + 1 
        d[i, j] = min của temp và (d[i - 1, j - 1] + tracker) 
    kết thúc 
kết thúc 
trả về d[l2, l1]

Mã ví dụ

#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 << "Khoảng cách Levenshtein: " << d[str2_len][str1_len]; 
}

Kết quả:

Khoảng cách Levenshtein: 2