[Algorithm] Edit Distance

Edit Distance 는 두 문자열을 동일하게 만들려면 얼만큼의 수정이 필요한지를 수치로 나타내는 알고리즘이다.

별로 어려운 건 없다. 핵심은 최소 수정의 값을 가져오는 DP라는 점이다.. 같은 문자가 발견되면 penalty를 없앤다. 자세한 것은 검색을 해보자. 아래는 내가 짠 기본적인 edit distance 코드다.


#include <iostream>
#include <stdio.h>
#define MIN(x,y,z) ((x) < (y)) ? ((z) < (x) ? (z) : (x)) \
: ((z) < (y) ? (z) : (y))

using namespace std;

int arr[100][100];
int strlen(char* str)
{
int cnt = 0;
while (str[cnt++] != '\0');
return cnt - 1;
}
int edit_dis(char* str1, char* str2)
{
int len1 = strlen(str1);
int len2 = strlen(str2);
for (int i = 0; i <= len1; i++) arr[i][0] = i;
for (int i = 0; i <= len2; i++) arr[0][i] = i;
for (int i = 1; i <= len1; i++){
for (int j = 1; j <= len2; j++){
int min = MIN(arr[i][j - 1] + 1, arr[i - 1][j] + 1,
(str1[i - 1] == str2[j - 1] ?
arr[i - 1][j - 1] : arr[i - 1][j - 1] + 1));
arr[i][j] = min;
}
}
return arr[len1][len2];;
}

int main()
{
char str1[100] = "monkey";
char str2[100] = "money";
int dis = edit_dis(str1, str2);
printf("%d\n", dis);
return 0;
}