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

Posted by 적분 ∫2tdt=t²+c
2016.12.26 03:25 프로그래밍

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

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

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

해결책

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

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




결과

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

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

비교 쌍한글 분해기존 방법
없어 - ㅇ벗어26
빼고 - 뺴고12
기다료 - 기다려12
소고기 - 소거기12
애이 - 에이12
잇어 - 있어11
그랬는데 - 글샌ㄴ데38

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


한계점과 활용방안

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

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

저작자 표시 비영리 동일 조건 변경 허락
신고
크리에이티브 커먼즈 라이선스
Creative Commons License
이 댓글을 비밀 댓글로

티스토리 툴바