화투의 개발 블로그

편집 거리 알고리즘이란, 두 문자열의 유사도를 판단하는 알고리즘이다.

유사도를 판단하는 기준은, 어떠한 문자열을 삽입,삭제,변경을 몇 번이나 해서 바꿀수 있는지를 계산하여

그 최소값을 구해, 그 값을 유사도 판단의 척도로 다룬다.

간단하게 예를 들어보자. 여기선 LCS와 마찬가지로 2차원 배열을 통해 문자열을 하나 하나씩 비교를 해나간다.

문자열 MICROSOFT와 NCSOFT를 비교한다고 하자. 모든 연속 부분 집합에 대해서 비교를 해야한다.

먼저 두 문자열의 처음 비교 대상은 공집합 두개이다. 둘 다 같은 문자열이기때문에 바꿀 것이 없어 코스트는 0이다.

그 다음은 N과 {}이다 m이 {}이 되려면 하나를 추가 해야한다. 따라서 코스트는 1이다.

이어서 NC와 {}이다. 두개를 추가해야되기 때문에 코스트는 2가된다.

이런 식으로 먼저 테이블을 그리면 다음과 같은 형태를 가진다.

그 다음 M과 N을 비교해보자. 이 둘은 다르다. 따라서 값을 변경해야 한다. 코스트는 1이다.

이어서 M과 NC이다. 둘 다 다르고, 하나를 지우고 하나를 바꿔야한다.  따라서 코스트는 2이다.

M과 NCS를 비교하자. 셋 다 다르고 두개를 지우고 하나를 바꿔야한다. 따라서 코스트는 3이다.

이런식으로 세 번째 줄 까지만 채워보면 밑과 같다.

테이블을 직접 그리다보면 다음과 같은 사실을 깨달을 수 있다.

문자열 M과 문자열 NC를 비교한다고 해보자. 여기서 문자열 M과N은 이미 순차적으로 비교를 한 상태이다. 이어서 문자열 M과 C이 만약 같다고 할 때, 이것에 대한 코스트는 바꿔즐 필요가 없다. 따라서 M과 N을 비교했던 값을 가져오기만 하면 된다.

그리고 만약 M과 C가 다르다고 했을 경우엔, M과 N을 비교했던 값에서 코스트를 하나 증가시켜주면 된다.

이 방법을 좀 더 긴 문자열에 적용해보자.

MICROSOFT와 NCSOFT 마지막 T끼리 비교했을 때, T는 서로 일치하므로 그 전까지 비교했던 MICROSOF와 NCSOF의 편집거리를 가져오면 된다.

MICRO와 NCS를 비교 할 경우, O와 S는 서로 다르므로, MICR과 NC를 비교했을때의 편집거리에다가 1을 증가시키면 된다.

여기서 첫 번째, 두 변수가 일치했을 경우 이전의 편집거리를 가져오면 된다고 했다. 

따라서 A[i] == B[j]일때의 편집거리 D(i,j) = D(i-1,j-1)이다.

그리고 두 문자가 다를 경우, 이전의 편집거리에서 1을 증가시켜야 한다고 했다.

MI와 NCS를 비교한다고 해보자. (위 테이블에서 이 경우 비교하는 대상은 I와 S이다. 이를 기억하고 보자.) 

왼쪽 대각선 위에 있는건 M와 NC를 비교하는 편집거리이다. 위는 M과 NCS를 비교하는 편집 거리이며, 왼쪽은 MI와 NC를 비교하는 편집 거리이다.

1. 여기서 대각선 M과 NC의 편집거리를 가져오는 것은 I와 S를 같은 문자로, 두 문자열이 같다고 보는 것이다. 즉 I를 S로 바꾸면 비교하는 문자가 같으니 M과 NC를 비교한 편집거리를 그대로 가져오고, I를 S로 바꾼 수정을 위한 코스트를 더하는 것이다. (위에서 같을 경우엔 대각선위에 있는 값을 그대로 가져왔었던걸 떠올리면 된다.)

2. 위쪽인 M과 NCS의 편집거리에서 1을 증가시켜 MI,NCS 편집거리에 넣는다는 것은 I를 삭제한다는 것을 뜻한다. 즉 M과 NCS의 편집거리를 그대로 가져오고 I를 삭제한 코스트를 추가한다는 뜻이다.

3. 마지막으로 왼쪽인 MI와 NC의 편집거거에서 1을 증가시켜 값을 MI,NCS 편집거리에 넣는다는 것은.  MI 뒤에 문자를 하나 추가한다는 것이다. 즉 MI뒤에 문자열을 하나 추가시켜 MIS,NCS이므로 MI,NC의 편집거리에다 추가시킨 비용을 더한 값을 넣는 것이다.

<그림으로 좀 더 자세히 이해해 보자>

즉 A[i] != B[j]면, 1,2,3번, 각 수정,삽입,삭제를 한 편집거리 중 최소값을 가져오면 된다. 즉 D(i,j) = min(D(i-1,j)+1,D(i,j-1)+1,D(i-1,j-1)+1)이다.

즉 정리하면 다음과 같다.

1. 비교하고자 하는 문자 A[i]와 B[j]가 같으면, D(i,j) = D(i-1,j-1)이다.

2. 비교하고자 하는 문자 A[i]와 B[j]가 다르면, D(i,j) = min(D(i-1,j)+1,D(i,j-1)+1,D(i-1,j-1)+1)이다.

위 규칙 대로 테이블을 채우면 다음과 같다. 규칙대로 한번 채워보고, 직접 문자열을 비교해서 채워서 두 테이블을 비교해보면 확실하게 알 수 있다.

여기서 맨 마지막 값이 편집거리가 된다.

이를 코드로 옮기면 다음과 같다.

C++ 편집 거리 알고리즘

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

string input1,input2;
int dist[1001][1001];

int levenshtein(string& input1, string& input2){
    for(int i=1; i<=input1.length(); i++)
        dist[i][0] = i;
    for(int j=1; j<=input2.length(); j++)
        dist[0][j] = j;
        
    for(int j=1; j<=input2.length(); j++){
        for(int i=1; i<=input1.length(); i++){
            if(input1[i-1] == input2[j-1]) dist[i][j] = dist[i-1][j-1];
            else dist[i][j] = min(dist[i-1][j-1]+1,min(dist[i][j-1]+1,dist[i-1][j]+1));
        }
    }   
    for(int j=0; j<=input2.length();j++){
        for(int i=0;i<=input1.length();i++)
            printf("%d\t",dist[i][j]);
            printf("\n");
    }
    return dist[input1.length()][input2.length()];
}

int main(){
    cin>>input1>>input2;
    cout<<"편집 거리 : "<<levenshtein(input1,input2)<<endl;
}

코드를 작성하고 보니 LCS 알고리즘이랑 유사점이 많아보인다는 생각이 들었다.

<실행 화면>