최소 편집 (Edit Distacne) 문제
개념
String s1, s2 가 주어졌을 때, s1을 s2로 변화시킬 때 필요한 최소 편집 횟수를 구하는 문제이다.
s1에 적용할 수 있는 연산은 총 4가지가 있으며 아래와 같다.
1. COPY : s1의 값을 그대로 유지함. -> edit distance : 0
2. INSERT : s1의 한 위치에 문자를 하나 삽입한다. -> edit distance : 1
3. DELETE : s1의 문자 하나를 삭제한다. -> edit distance : 1
4. SUBSTITUTE : s1의 문자 하나를 다른 문자로 교체한다. -> edit distance : 1
예를 들어, s1 = "strong" s2 ="storm" 일 때의 edit distance는 3이다.
COPY COPY DELETE COPY SUBSTITUTE DELETE 의 연산을 차례로 적용하면, 최소 편집 횟수는 3이고, strong 에서 storm 으로 변화시킬 수 있다.
두 문자열간 의 Edit Distance가 작다면, 두 단어가 비슷하게 생겼다.
크다면, 두 단어가 매우 다르다.
위의 문제는 실생활에서 '추천단어', '오류 차동고치기'로 사용된다.
문제 풀이
Dynamic Programming (동적계획법)을 이용해서 문제를 푼다.
행 사이즈가 s1의 길이 +1, 열 사이즈가 s2의 길이인 2차원 배열을 할당하고, 그 안의 값들을 채워주는 풀이법이다.
그리고 각각의 칸의 값은 다음과 같은 의미를 가진다.
table[0][1]= " "->"s"로 변화시킬 때의 최소 편집 횟수.
table[0][2]=" "->"st"로 변화시킬 때의 최소 편집 횟수.
table[2][2]="st"->"st"로 변화시킬 때의 최소 편집 횟수.
table[5][3]="stron"->"sto"로 변화시킬 때의 최소 편집 횟수.
따라서 table[6][5]에 우리가 원하는 값("strong"->"storm"으로 변화시킬 때의 최소 편집 횟수)이 있게 된다.
Pseudo Code of Edit Distance
1. s1의 마지막 문자와 s2의 마지막 문자가 같다면,
t[ i , j ] = t[ i-1, j-1 ] // 즉, 좌상단(대각선)에 있는 값을 넣는다.
2. s1의 마지막 문자와 s2의 마지막 문자가 다르다면,
t[ i , j ] = 1 + min (좌, 상, 대각선) // 즉, 3개의 값 중, 가장 작은 값에 +1을 해준 값을 넣는다.
내가 이해한 방법
1의 경우, table[r][c]는 table[r-1][c-1]에서 s1의 문자열(s1[r-1])에서 문자가 하나 추가된 것이고, s2도 본래의 문자열(s2[c-1])에서 문자가 하나 추가된 것이다.
그런데 그 추가된 문자가 동일하므로, s1이 s2로 변화시킬 때는 table[r-1][c-1]의 상태에서 아무 작업도 하지 않아도 된다는 뜻이다.
따라서, table[r][c]=table[r-1][c-1]의 값을 가지는 것.
2의 경우, 좌 table[r][c-1], 상 table[r-1][c], 대각선 table[r-1][c-1] 에서 table[r][c]로 이동방법은 (즉, 이전 s1-> 이전 s2 에서 현재 s1->현재s2 이동방법)
insert하거나, delete, substitute의 연산방법이 있다. 그리고 각각의 edit distance는 +1을 증가시키므로,
세 가지 경우의 수 중 가장 작은 값을 고르고 그 값에 +1을 하는 것이다.
위의 방법을 토대로 table의 값을 채우면, 아래 그림과 같아진다.
C언어 구현 코드
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int **createTable(int _num_r, int _num_c) {
int **res_table = (int **)malloc(_num_r*(sizeof(int*)));
for (int i = 0; i < _num_r; i++) {
res_table[i] = (int *)malloc(_num_c*(sizeof(int)));
}
return res_table;
}
int getMinimum(int a, int b, int c) {
if (a <= b && a <= c) return a;
else if (b <= a && b <= c) return b;
else if (c <= a && c <= b) return c;
}
void populateTable(int **_table, char *_s1, char *_s2, int _num_row, int _num_col) {
// 1행 채우기
for (int i = 0; i < _num_col; i++) {
_table[0][i] = i;
}
// 1열 채우기
for (int i = 0; i < _num_row; i++) {
_table[i][0] = i;
}
// 나머지 칸들 채우기
for (int i = 1; i < _num_row; i++) {
for (int j = 1; j < _num_col; j++) {
if (_s1[i-1]==_s2[j-1]) { // 마지막 글자가 같다면,
_table[i][j] = _table[i - 1][j - 1];
}
else {
_table[i][j] = getMinimum(_table[i][j-1], _table[i-1][j], _table[i-1][j-1]) + 1; // 좌, 상, 대각선
}
}
}
}
int main(void) {
// s1(행) -> s2(열)
char* s1 = "strong";
char* s2 = "storm";
int num_row = strlen(s1) + 1; // 처음의 " "(공백)을 포함하여 +1을 해준다. // 7
int num_col = strlen(s2) + 1; // 6
int **table = createTable(num_row, num_col); // 동적 배열을 생성해서 return 해준다.
populateTable(table, s1, s2, num_row, num_col); // table을 채우는 함수.
printf("\n----------------------Edit Distance----------------------\n");
printf("num row : %d \nnum_col : %d\n", num_row, num_col);
for (int i = 0; i < num_row; i++) {
for (int j = 0; j < num_col; j++) {
printf("%d ",table[i][j]);
}
printf("\n");
}
}
실행 결과
