편집 거리(Edit Distance) 알고리즘

다음 문제를 생각해보자.

 

문자열 a와 b가 있다. 여기서 각 문자열의 임의 위치를 삭제하거나 다른 문자로 교체, 그리고 임의의 문자를 삽입하는 행위의 비용을 1이라고 할 때 a와 b를 같은 문자열로 만드는 최소 비용을 구하라.

 

예를 들어 "abc"와 "abd"가 있을 때 세 번째 글자를 동일하게 만들면 되므로 편집 거리는 1이다.

 

"ABCD"와 "ABd"는 'D'를 삭제하고 'C'를 'd'로 바꾸면 되므로 편집 거리는 2이다. 혹은 "ABd"에서 'd'를 'C'로 바꾸고 'D'를 추가해도 된다.

 

이 문제는 2차원 dp로 풀 수 있음이 널리 알려져 있다.

 

어떻게 dp로 풀 수 있는지 같이 살펴보도록 하자.

 

우선 단어를 하나 이해해야 한다.

 

align: 보통 맞추다 혹은 정렬(sort가 아님을 유의)이라고 번역되는데 문자열에서는 임의의 문자를 삭제하거나 추가하여 두 문자열의 길이를 동일하게 만든다는 의미로 이해하면 된다.

 

우리는 3가지 경우에 대해 각기 계산하면서 최소 비용을 찾을 것이다.

 

1. a를 b에 align 하는 경우 (a[i]에 새로운 문자를 삽입하거나 기존의 a[i]를 삭제함)

2. b를 a에 align 하는 경우 (b[i]에 새로운 문자를 삽입하거나 기존의 b[i]를 삭제함)

3. a[i]와 b[i]를 동일하게 하는 경우 (a[i] := b[i] or b[i] := a[i])

 

최소 비용을 계산하기 위해 다음 테이블을 정의하자.

 

dp[i][j] := 문자열 a에서 길이 i 만큼의 prefix와 문자열 b에서 길이 j 만큼의 prefix를 같게 만드는 최소 편집 거리

 

"ABCD"와 "ABd"에 대해 다음 테이블이 생성된다.

처음에는 dp[0][0]은 두 문자열이 없는 상태이므로 0이고 dp[i][0]과 dp[0][j]에 해당하는 값을 채울 것이다.

 

이때는 a를 b에 align 하거나 b를 a에 align 하는 동작만 할 수 있으므로 공백과 prefix의 길이 차이만큼 테이블이 채워진다.

이를 C/C++ 코드로 나타내면 다음과 같다.

for (int i = 0; i < a.size(); i++)
{
    dp[i + 1][0] = i + 1;
}

for (int j = 0; j < b.size(); j++)
{
    dp[0][j + 1] = j + 1;
}

 

나머지 테이블은 다음 경우에서 최솟값을 찾는다.

 

$a[i] = b[i]$ 이면 수정할 필요가 없으므로 dp[i - 1][j - 1]를 그대로 가져온다.

 

$a[i] \neq b[i]$ 이면 dp[i - 1][j]에서 align 하는 비용 1을 추가하거나 dp[i][j - 1]에서 align 하는 비용 1을 추가한다. (문자를 교체하는 동작은 i - 1 또는 j - 1에서 문자 하나를 추가하는 것과 같다.)

 

수식으로 정리하면 다음과 같다.

 

$dp[i][j] = \begin{cases} dp[i - 1][j - 1] \quad if \; a[i] = b[i] \\ min(dp[i - 1][j] + 1, dp[i][j - 1] + 1) \; else \end{cases}$

 

위 점화식을 통해 테이블을 채우면 다음과 같은 결과를 볼 수 있다. 빨간색 화살표를 통해 어떻게 최소 편집 거리를 구하는지 추적할 수 있다.

위 점화식을 푸는 과정을 코드로 쓰면 2차원 바텀업 dp로 편집 거리를 구할 수 있게 된다.

for (int i = 0; i < a.size(); i++)
{
  dp[i + 1][0] = i + 1;
}
for (int j = 0; j < b.size(); j++)
{
 dp[0][j + 1] = j + 1;
}

for (int i = 1; i <= a.size(); i++)
{
  for (int j = 1; j <= b.size(); j++)
  {
    if (a[i - 1] == b[j - 1])
    {
      dp[i][j] = dp[i - 1][j - 1];
    }
    else
    {
      dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
      dp[i][j] = min(dp[i - 1][j - 1] + 1, dp[i][j]);
    }
  }
}

 

실제로 문제를 풀어보자.

 

https://www.acmicpc.net/problem/15483

15483번: 최소 편집

방금 배운 동적 계획법을 그대로 적용하면 된다.

 

편집 거리는 이제 너무 고전적인 dp 문제이고 지엽적이기 때문에 대회나 코딩 테스트에서 나올 확률은 매우 낮을 것으로 사료된다.

 

하지만 편집 거리를 공부함으로써 dp 문제를 해결하는 안목을 기를 수 있기 때문에 공부할 가치는 충분할 것이다.