Levenshtein_distance는 두 문자열 간의 거리(edit distance)를 측정하기 위한 평가기준이다.
CP949나 UTF-8 인코딩을 따르는 multibyte string의 경우, 전혀 다른 글자임에도 불구하고 바이트 단위로는 일치할 가능성이 있기 때문에 UCS4로 변환해서 거리를 계산하지 않으면 정확한 거리값을 구하지 못해서 클러스터링의 품질 저하의 원인이 된다. 다음은 성능 최적화가 되어 있지 않은 기본 구현에, UTF-8 문자열을 UCS4로 변환해서 wchar_t 단위로 비교하도록 작성되어 있다.
const int MAX_LINE_LEN 4096;
int get_ucs4_levenshtein_distance(string str1, string str2, double* ratio = NULL)
{
wchar_t wcs1[MAX_LINE_LEN];
wchar_t wcs2[MAX_LINE_LEN];
int ret = mbstowcs(wcs1, str1.c_str(), str1.length());
wcs1[ret] = 0;
ret = mbstowcs(wcs2, str2.c_str(), str2.length());
wcs2[ret] = 0;
uint len1 = wcslen(wcs1);
uint len2 = wcslen(wcs2);
int d[len1 + 1][len2 + 1];
for (uint i = 0; i <= len1; ++i) {
d[i][0] = i;
}
for (uint j = 0; j <= len2; ++j) {
d[0][j] = j;
}
for (uint i = 0; i < len1; ++i) {
for (uint j = 0; j < len2; ++j) {
int cost;
if (wcs1[i] == wcs2[j]) {
cost = 0;
} else {
cost = 1;
}
d[i + 1][j + 1] =
min(min(d[i][j + 1] + 1, d[i + 1][j] + 1), d[i][j] + cost);
}
}
if (ratio != NULL) {
*ratio = 1.0 - double(d[len1][len2]) / double(max(len1, len2));
}
return d[len1][len2];
}
int main()
{
setlocale(LC_CTYPE, "ko_KR.utf8");
cout << get_ucs4_levenshtein_distance("대한민국", "대한A민국") << endl;
double similarity;
cout << get_ucs4_levenshtein_distance("대한민국", "대한A민국", &similarity) << "\t";
cout << similarity << endl;
}
유사도를 구하고 싶을 때는 double 타입 변수의 주소를 세번째 parameter로 지정하면 된다. 이 경우, 두 문자열 중 더 긴 문자열에 대해 더 짧은 문자열이 얼마나 유사한지를 계산한다.
변환함수의 리턴값을 가지고 유니코드 문자열을 terminate시켜야 함
ret = mbstowcs();
wcs[ret] = 0;