반응형
수업 시간에 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)
| a | b | a | a | ||
| 0 | 1 | 2 | 3 | 4 | |
| b | 1 | 2 | 1 | 2 | 3 |
| b | 2 | 3 | 2 | 3 | 4 |
| a | 3 | 2 | 3 | 2 | 3 |
| b | 4 | 3 | 2 | 3 | 4 |
| b | 5 | 4 | 3 | 4 | 5 |
<편집 거리 테이블>
#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))
| a | b | ||
| 0:E[0][0] | 1:E[0][1] | 2 | |
| b | 1:E[1][0] | E[1][1] | |
| b | 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[모든행의개수][모든열의개수] 의 값은 최소 편집거리가 된다.
이때, 목표 문자열과 현재 문자열을 바꾸어 계산해도 값은 같으며,
연산들의 값을 각 각 다르게 주고 문자열들을 바꾸어 계산해도 값은 같다.
왜냐하면, 결국 최솟값의 합연산 결과들이므로 마지막 최소편집거리는 같다.
반응형
'Lecture > Algorithm' 카테고리의 다른 글
| [정렬] 버블정렬 ( Bubble Sort ) (0) | 2021.05.09 |
|---|---|
| [정렬] 선택정렬( Selection sort ) (0) | 2021.05.08 |
| [백준 1708번] 컨벡스헐 (0) | 2021.05.03 |
| [기하] 단순 폐쇄 경로 찾기 (0) | 2021.04.30 |
| [기하] 두 선분 교차 (Intersection) (0) | 2021.04.30 |
