C++로 구현하는 Wagner-Fisher 알고리즘: 두 문자열의 최소 편집 거리 계산하기

이 글에서는 Wagner-Fisher 알고리즘을 사용하여 두 개의 문자열을 비교하는 방법을 알아봅니다. 이 알고리즘을 활용하면 두 문자열이 서로 일치하도록 만들기 위해 필요한 최소 변경 횟수(문자 삽입, 삭제, 치환)를 구할 수 있습니다.

Wagner-Fisher 알고리즘은 동적 계획법(Dynamic Programming)에 기반한 접근 방식으로, 두 문자열 사이의 레벤슈타인 거리(Levenshtein Distance), 즉 한 문자열을 다른 문자열로 변환하는 데 필요한 최소 편집 연산 횟수를 측정합니다.

입력: 두 문자열 "Support"와 "Suppose"
출력: 필요한 최소 변경 횟수: 2

알고리즘

Wagner_Fisher(str1, str2)

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

l1 := str1의 길이, l2 := str2의 길이
(l2+1) × (l1+1) 크기의 행렬 d를 정의한다.
d의 첫 번째 행을 0부터 l1까지의 값으로 채우고,
첫 번째 열을 0부터 l2까지의 값으로 채운다.
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 := 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)
    done
done
return d[l2, l1]

여기서 tracker는 현재 비교하는 두 문자가 같으면 0(추가 비용 없음), 다르면 1(치환 비용 발생)의 값을 가집니다. 점화식은 문자 삭제(d[i-1][j]+1), 문자 삽입(d[i][j-1]+1), 치환 또는 일치(d[i-1][j-1]+tracker)의 세 가지 경우 중 최솟값을 선택하여 테이블을 채워 나갑니다.

예제 코드

#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 Levenshtein distance " << d[str2_len][str1_len];
}

실행 결과

The Levenshtein distance 2

"Support"를 "Suppose"로 변환하려면 여섯 번째 문자 'r'을 's'로 치환하고, 일곱 번째 문자 't'를 'e'로 치환하면 됩니다. 따라서 최소 편집 거리는 2가 됩니다. 이처럼 Wagner-Fisher 알고리즘은 오타 교정, 검색어 자동 완성, DNA 서열 분석 등 문자열 유사도가 필요한 다양한 분야에서 활용됩니다.