Algorithm] 동적계획법 - 편집 거리(Edit Distance)

 

문서 편집 시 삽입, 삭제, 대체 연산이 사용되며

이 때 어떤 특정 문자열 S를 다른 문자열 S`으로 변환시키 과정에서 필요한

최소 편집 연산 횟수를 편집 거리(Edit Distance)라고 한다.

 

stable이라는 문자열을 strike로 바꾼다고 할 때를 생각해보자.

여러 가지 방법이 존재한다.

첫 번째 방법은 s, t, e는 그대로 두고 ‘abl’을 삭제하고 ‘rik’를 삽입하는 방식으로,

3회의 삭제 연산과 3회의 삽입 연산으로 총 6회의 편집 연산이 실행되었다.

두 번째 방법은, s, t, e를 그대로 사용하고 ‘abl’을 ‘rik’로 바꾸기만 하면 stable을 strike로 바꿀 수 있고,

3번의 대체가 발생했기 때문에 이 때 총 3회의 편집 연산 실행되었다.

 

두 문자열을 바꾸는 데 필요한 편집 거리를 구하는 최적의 경우,

즉 편집 거리를 구하려면 어떻게 해야 하는지 생각을 해봐야 한다.

이를 동적계획법으로 풀어보려면, 어떤 경우를 부분 문제로 구성할 것이고

그 부분문제에 대한 최적해를 보장하는 방법에 대해서 생각을 해봐야 한다.

 

일단 여기서 문자열 A를 ‘stable’로, 문자열 B를 ‘strike’이라고 정의내리고

이들 문자열의 문자 하나하나를 각각 a1, a2, b1, b2 등으로 정의한 상태로 문제를 접근해보자.

 

A = stable, B = strike

E : 편집 거리

 

E[n,m]는 A문자열의 시작부분에서 n개의 문자를, B문자열의 시작부분에서 m개의 문자로 변환시키는

최소 편집 연산 횟수, 편집 거리에 대한 정보를 다룬다.

예를 들어 E[4,3]은, stab를 str로 변환시키는데 필요한 편집 거리를 담고 있고,

E[6,6]은 이 문제의 답, 즉, stable를 strike로 변환시키는데 필요한 편집 거리를 담고 있다.

동적계획법의 과정을 점화식으로 표현하는 것도 좋고, 테이블로 표현하는 것도 가능하다.

특히 2차원 테이블이 작성되는 경우에는 점화식을 바탕으로 테이블을 작성해두면

어떻게 알고리즘을 작성할 것인지 청사진을 그릴 수 있기 때문에 용이하기 때문에,

테이블을 작성하면서 방향에 대해서 생각해보도록 하자.

일단 위 문자열을 바탕으로 한 E[4,3]에 대한 답을 구하는 테이블은 아래와 같다.

 

	0	s	t	r
0	0	1	2	3
s	1	0	1	2
t	2	1	0	1
a	3	2	1	1
i	4	3	2	1

 

테이블에서 0은 빈 문자열(공백)이다.

동적 계획법 테이블을 작성해본 사람이라면 E[n,m]를 구하는 과정에서

E[n-1,m], E[n,m-1], E[n-1,m-1]을 바탕으로 해를 구해나가는 방법이라는 걸 알고 있을 것이다.

일종의 공식처럼 편집거리를 구하는 방식에 대해서 생각을 해볼 수 있는데, 세 가지 경우가 있다.

 

E[n-1,m-1] => E[n,m] ; A문자열의 n번째 문자를 B문자열의 m번째 문자로 바꾸기

E[n-1,m] => E[n,m] ; A문자열의 n번째 문자 삭제

E[n,m-1] => E[n,m] ; B문자열의 m번째 문자 삽입

 

E[n,m] = E[n-1,m]+1

E[n,m] = E[n,m-1]+1

E[n,m] = E[n-1,m-1] + a

 

세 가지의 해가 나올 수가 있다. 여기서 a는 A문자열의 n번째 문자와 B문자열의 m번째 문자가 같은 경우에는 0, 그렇지 않으면 1이다.

결국 E[n,m]의 최적해를 구하는 식은 아래와 같다.

 

E[n,m] = min(E[n,m-1]+1, E[n-1,m]+1, E[n-1,m-1]+a)

일단 의사코드로 알고리즘을 구현을 해보고, 알고리즘을 바탕으로 진행되는 테이블 작성 과정을 살펴보자.

입력 문자열 A와 B의 길이를 각각 a, b라고 하고, 이 알고리즘의 출력을 E[a,b]라고 하자.

 

for (n=0 to a)

    E[n,0] = n;

for (m=0 to b)

    E[0,m] = m;

for (n=1 to a)

    for (m=1 to b)

        E[n,m]=min{E[n,m-1]+1, E[n-1,m]+1, E[n-1,m-1]+a};

return E[a,b];

 

 

이제 테이블을 직접 작성해보면서 문자열 편집 거리 구하는 문제를 풀어보도록 하자.

테이블의 E[j,0], E[0,k]에 대해서 모두 초기화가 이루어진 상태에서

E[j,k]를 구해나가면서 최종적인 해인 E[n,m]을 구하는 과정에 대해서 살펴볼 수 있다.

	0	s	t	r	i	k	e
0	0	1	2	3	4	5	6
s	1
t	2
a	3
b	4
l	5
e	6

	0	s	t	r	i	k	e
0	0	1	2	3	4	5	6
s	1	2
t	2
a	3
b	4
l	5
e	6

	0	s	t	r	i	k	e
0	0	1	2	3	4	5	6
s	1	2
t	2
a	3
b	4
l	5
e	6

	0	s	t	r	i	k	e
0	0	1	2	3	4	5	6
s	1	0
t	2
a	3
b	4
l	5
e	6

 

이런식으로 지속적으로 편집거리를 구해나가면,

 

	0	s	t	r	i	k	e
0	0	1	2	3	4	5	6
s	1	0	1	2	3	4	5
t	2	1	0	1	2	3	4
a	3	2	1	1	2	3	4
b	4	3	2	2	2	3	4
l	5	4	3	3	3	3	4
e	6	5	4	4	4	4	3

 

E[6,6] = 3으로 편집 거리 3을 구할 수 있다.

 

동적계획법을 이용한 편집 거리를 구하는 경우 시간 복잡도는 O(mn)이다.

여기서 m과 n은 각 문자열의 길이를 나타낸다.

테이블을 보면 mXn 형태의 테이블이고 이 테이블을 구성하는 과정에서

최솟값을 찾는 것은 O(1)이라는 걸 생각해보면 쉽게 구할 수 있다.

 

편집거리 문제는 이런 문자열 편집, 철자 오류 검색, 자연어 번역 등에도 사용하지만,

유전 및 의료 공학에서 유전자 유사도를 판별하는데 사용하는 등 광범위하게 응용되기도 한다.

 

소스코드로 작성하며 이렇다.

string을 이용해 입력 받고 이것을 char 배열로 변환하는 과정이 있어서 조금 지저분한데,

지저분한 걸 없애고 싶으면 char로 다루면 깔끔해진다.

#include <iostream>
#include <string>
using namespace std;
int MinValue(int a, int b, int c)
{
    int min;
    if (a < b)
        min = a;
    else
        min = b;
    if (min < c)
        return min;
    else
        return c;
}
int DP(string A, string B)
{
    int aLen = A.size();
    int bLen = B.size();
    int** E;
    char *aChar, *bChar;
    aChar = (char*)A.c_str();
    bChar = (char*)B.c_str();
    E = new int*[aLen + 1];
    for (int i = 0; i <= aLen; i++)
    {
        E[i] = new int[bLen + 1];
    }
    for (int i = 0; i <= aLen; i++)
    {
        E[i][0] = i;
    }
    for (int i = 0; i <= bLen; i++)
    {
        E[0][i] = i;
    }
    for (int i = 1; i <= aLen; i++)
    {
        for (int j = 1; j <= bLen; j++)
        {
            if (aChar[i - 1] == bChar[j - 1])
                E[i][j] = E[i - 1][j - 1];
            else
                E[i][j] = 1 + MinValue(E[i - 1][j], E[i][j - 1], E[i - 1][j - 1]);
        }
    }
    return E[aLen][bLen];
}
int main(void)
{
    string A, B;
    getline(cin, A);
    getline(cin, B);
    cout << DP(A, B);
}