재시민

수업 시간에 Dynamic Progrmaming 실습으로 편집거리테이블 (string edit table) 에 대해 배웠다.

편집거리는 두 문자열의 차이를 측정하기 위한 문자열 측정 단위 이다.

최소 편집거리는 주어진 문자열을 목표 문자열로 변환하기 위해 필요한 최소한의 편집 거리 이다.

X = bbabb -> Y = abaa (X : 주어진 문자열 , Y : 목표 문자열 ) 

- 삽입 (1), 삭제 (1), 변경(0 or 2)

1) 편집 1 -> x 전부 삭제, y 하나씩 삽입 (비용 : 9)

2) 편집 2 -> x1, x2 를 삭제하고 x5를 a로 변경한 뒤 a 삽입 (비용 : 6)

<편집 거리 테이블>

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

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] = min(E[i - 1][j] + 1, min(E[i][j - 1] + 1, E[i - 1][j - 1]));
            else
                E[i][j] = min(E[i - 1][j] + 1, min(E[i][j - 1] + 1, E[i - 1][j - 1] + 2));
        }
    }
    for (int i = 0;i <= aLen;i++) {
        for (int j = 0;j <= bLen;j++) {
            printf("%d\t", E[i][j]);

        }
        printf("\n");

    }
    printf("-----------------------------------\n");
    return E[aLen][bLen];
}
int main(void)
{
    string A, B;
    getline(cin, A);
    getline(cin, B);
    printf("편집거리테이블\n");
    cout << "최소편집 비용 : " << DP(A, B);
}

 알고리즘 설명

E[i][j] = min(E[i-1][j],min(E[i][j-1],E[i-1][j-1] + 2))

E[1][1] 을 구하기 위해서는 주변의 세 가지 요소의 값 중 최솟값을 구한 후, 삽입, 제거, 교환 연산에 의한 비용을 더해주

면된다.

E[0][0], E[1][0], E[0][1] 중 최솟값은 E[0][0] = 0 이다.

그리과,  0 행과 0 열의 숫자가 다르므로 비용은 2 증가 따라서, E[1][1] = 2이다. 

이런식으로 모든 행렬의 값을 구하면 E[모든행의개수][모든열의개수] 의 값은 최소 편집거리가 된다. 

이때, 목표 문자열과 현재 문자열을 바꾸어 계산해도 값은 같으며, 

연산들의 값을 각 각 다르게 주고 문자열들을 바꾸어 계산해도 값은 같다.

왜냐하면, 결국 최솟값의 합연산 결과들이므로 마지막 최소편집거리는 같다.