[C++] 한글 두벌식 자판에서의 편집거리

일반 편집거리 알고리즘은 한글에 부적합하다

두 텍스트가 얼마나 유사한지를 판단하는데 편집거리 알고리즘이 널리 쓰입니다. 주어진 텍스트 A가 B로 바뀌기 위해서는 글자를 몇번 빼고 더하고 바꿔야하는지를 세는 방법인데요, 이미 이를 효율적으로 계산하는 코드들이 인터넷 상에 많지요. 다만 한글에 이를 그대로 적용하는데에는 애로사항이 있습니다. 

로마자 알파벳은 입력하기 위해 사람이 누르는 자판과 실제 입력되는 글자가 같은 반면, 한글은 그렇지 않다는 것이지요. 한글을 입력하는데에는 대게 두벌식 자판을 이용해 자음/모음을 따로 입력하고, 이를 입력기에 합쳐서 글자를 만들어내는 과정을 거치게 됩니다. 따라서 "갔다"와 "갓다"는 실제로 Shift키 하나 차이나는 텍스트임에도 불구하고 실제 입력된 결과물은 전체 글자인 갔과 갓이 차이나는 상황이 발생하게 되지요. 그래서 실제로 갓과 갔은 유사한 글자지만, 일반 편집거리 알고리즘에서는 갓과 갔이나 갓과 굽이나 똑같이 먼 거리로 인식이 되게 됩니다. 

해결책

따라서 편집거리 알고리즘을 한글에 적용하기 위해서는 약간의 편법이 필요합니다.제일 간단한 방법으로는 한글 낱자를 사람이 입력하는 방식대로 자소로 분리하여 표현하고 이에 대해서 편집거리 알고리즘을 적용하는 방법이 있겠지요. 여기서는 두벌식 자판을 사용한다고 가정하고 한글 낱자를 자소로 분해해보았습니다.

두벌식에서 한글을 입력하는데 사용되는 자판는  ㅂㅈㄷㄱㅅㅁㄴㅇㄹㅎㅋㅌㅊㅍ ㅛㅕㅑㅐㅔㅗㅓㅏㅣㅠㅜㅡ + 시프트키 입니다. 한글 문자가 들어오면 위에 해당하는 키 입력으로 바꾸어서 분해를 해주고, 이 결과를 편집거리 알고리즘에 넣는 코드를 짜보았습니다.

#include <string> #include <algorithm> #include <numeric> #include <functional> using namespace std; /* 이 함수는 https://en.wikipedia.org/wiki/Levenshtein_distance 에서 가져왔습니다. */ int levenshtein_distance(const std::string &s1, const std::string &s2) { int s1len = s1.size(); int s2len = s2.size(); auto column_start = (decltype(s1len))1; auto column = new decltype(s1len)[s1len + 1]; iota(column + column_start, column + s1len + 1, column_start); for (auto x = column_start; x <= s2len; x++) { column[0] = x; auto last_diagonal = x - column_start; for (auto y = column_start; y <= s1len; y++) { auto old_diagonal = column[y]; auto possibilities = { column[y] + 1, column[y - 1] + 1, last_diagonal + (s1[y - 1] == s2[x - 1] ? 0 : 1) }; column[y] = std::min(possibilities); last_diagonal = old_diagonal; } } auto result = column[s1len]; delete[] column; return result; } /* 한글 키 입력에 해당하는 상수들. 문자입력에 쓰이지 않는 부분을 해당 문자를 다른 곳에서 쓰지 않는다는 가정하에 임의로 사용했습니다. 탭 문자와 줄 바꿈 문자가 여기 들어가 있으니, 만약 비교 대상인 텍스트에 해당 문자를 사용해야한다면 값을 바꾸시길 추천합니다. */ // 자음 #define H_G "\x01" #define H_N "\x02" #define H_D "\x03" #define H_R "\x04" #define H_M "\x05" #define H_B "\x06" #define H_S "\x07" #define H_0 "\x08" #define H_J "\x09" #define H_C "\x0A" #define H_K "\x0B" #define H_T "\x0C" #define H_P "\x0D" #define H_H "\x0E" // 모음 #define H_A "\x10" #define H_AE "\x11" #define H_YA "\x12" #define H_EO "\x13" #define H_E "\x14" #define H_YEO "\x15" #define H_O "\x16" #define H_YO "\x17" #define H_U "\x18" #define H_YU "\x19" #define H_EU "\x1A" #define H_I "\x1B" // 시프트 #define H_SH "\x1F" /* 한글을 분해해주는 함수. 입력문자열은 utf-8이라고 가정합니다. */ string disassembleKo2(const string& s) { static const char* mtbl1[] = { H_G, H_G H_SH, H_N, H_D, H_D H_SH, H_R, H_M, H_B, H_B H_SH, H_S, H_S H_SH, H_0, H_J, H_J H_SH, H_C, H_K, H_T, H_P, H_H }; static const char* mtbl2[] = { H_A, H_AE, H_YA, H_AE H_SH, H_EO, H_E, H_YEO, H_E H_SH, H_O, H_O H_A, H_O H_AE, H_O H_I, H_YO, H_U, H_U H_EO, H_U H_E, H_U H_I, H_YU, H_EU, H_EU H_I, H_I }; static const char* mtbl3[] = { "", H_G, H_G H_SH, H_G H_S, H_N, H_N H_J, H_N H_H, H_D, H_R, H_R H_G, H_R H_M, H_R H_B, H_R H_S, H_R H_T, H_R H_P, H_R H_H, H_M, H_B, H_B H_S, H_S, H_S H_SH, H_0, H_J, H_C, H_K, H_T, H_P, H_H }; static const char* mtbl4[] = {H_G, H_G H_SH, H_G H_S, H_N, H_N H_J, H_N H_H, H_D, H_D H_SH, H_R, H_R H_G, H_R H_M, H_R H_B, H_R H_S, H_R H_T, H_R H_P, H_R H_H, H_M, H_B, H_B H_SH, H_B H_S, H_S, H_S H_SH, H_0, H_J, H_J H_SH, H_C, H_K, H_T, H_P, H_H }; string ret; for (size_t i = 0; i < s.size(); i++) { if (s[i] & 0xE0 != 0xE0) { // utf-8에서 3바이트가 아닌 문자는 건너뜀 ret.push_back(s[i]); continue; } if (i + 2 >= s.size()) break; int chr = (s[i] & 0x0F) << 12; chr |= (s[i + 1] & 0x3F) << 6; chr |= (s[i + 2] & 0x3F); // 완성형 한글 낱자 if (chr >= 0xAC00 && chr < 0xD7B0) { chr -= 0xAC00; int p1 = chr / (28 * 21), p2 = (chr % (28 * 21)) / 28, p3 = chr % 28; ret.append(mtbl1[p1]); ret.append(mtbl2[p2]); if(p3) ret.append(mtbl3[p3]); } // 조합형 자소 else if (chr >= 0x1100 && chr < 0x1200) { if (chr < 0x1100 + 19) ret.append(mtbl1[chr - 0x1100]); else if (chr < 0x1161); else if (chr < 0x1161 + 21) ret.append(mtbl2[chr - 0x1161]); else if (chr <= 0x11A8); else if (chr < 0x11A8 + 28) ret.append(mtbl2[chr - 0x11A8]); } // 일반 자모 else if (chr >= 0x3131 && chr < 0x319F) { if (chr < 0x3131 + 30) ret.append(mtbl4[chr - 0x3131]); else if (chr < 0x314F + 21) ret.append(mtbl2[chr - 0x314F]); } // 한글이 아닌 경우 else { ret.insert(ret.end(), &s[i], &s[i] + 3); } i += 2; } return ret; } /* 입력 문자열에 매핑함수를 적용하여 편집거리를 구해주는 함수 */ int levenshtein_distance_map(const std::string & s1, const std::string & s2, const function<string(const string&)>& mapFunc) { string r1 = mapFunc(s1), r2 = mapFunc(s2); return levenshtein_distance(r1, r2); }

결과

기존 편집거리 알고리즘과 한글 분해를 적용한 알고리즘의 차이를 봅시다.

UTF-8 인코딩인지라 기존 알고리즘에서는 한글 1글자 차이는 거리 3의 차이가 나게됩니다만, 모음만 다른 경우는 2, 받침만 다른 경우는 1의 차이가 납니다. 하지만 낱자를 분해한 뒤 적용한 알고리즘에서는 실제로 두벌식 자판에서 입력할때의 키의 차이만큼의 거리가 나왔죠.

비교 쌍	한글 분해	기존 방법
없어 - ㅇ벗어	2	6
빼고 - 뺴고	1	2
기다료 - 기다려	1	2
소고기 - 소거기	1	2
애이 - 에이	1	2
잇어 - 있어	1	1
그랬는데 - 글샌ㄴ데	3	8

실제 실행결과는 http://ideone.com/b0ppIN 에서 확인해볼수 있습니다.

한계점과 활용방안

이 방법의 치명적인 단점은 두벌식 자판이 아닌 다른 자판에서 발생하는 오타에 대해서는 오히려 더 큰 거리를 낼수 있다는 거죠. 결국 한글 기반으로 오타 정정 디비를 구축하기 위해서는 사용자가 어떤 자판을 활용하는지를 알아야한다는 문제점이 생깁니다. 그런데 거꾸로 생각해보자면 사용자가 주로 내는 오타의 양상을 모아놓고 해당 문자를 특정 입력 방법(두벌식, 세벌식, 천지인, 단모음 등등)으로 분해한 후 편집거리를 적용했을때 그 편집거리가 최소가 된다면 사용자는 그 자판을 사용하고 있겠구나 하고 추정이 가능하다는 말이 됩니다. 즉 사용자판을 알 경우 한글 오타를 정정하는데 더 정확한 기법을 사용할 수 있고, 오타를 알 경우 유저가 사용하는 자판을 추정할 수 있다는 결론이 나옵니다. 

이번 포스팅에서는 눈도 아프고 피곤해서 두벌식 자판만 분해하는 코드를 작성했지만, 유사한 방법으로 다른 분해 함수도 작성해놓으면 상황에 따라 맞춰쓸 수 있을거 같아요.  귀찮아서 언제 그렇게 될지는 모르겠지만 나중에 할 일로 미뤄놓아야지..!