[Kiwi] 지능형 한국어 형태소 분석기 0.4버전 업데이트

속도가 만족할 만큼 나오지 않아서 아쉽길래 한동안 접어두고 있었는데, 갑자기 좋은 아이디어가 떠올라서 업데이트를 해보았습니다. 약간의 알고리즘 수정으로 최소 +50%~200%의 속도 향상을 달성할 수 있었는데, 기록하지 않고 넘어가기에 너무 아까워서 포스팅을 써보았습니다.

0.3버전까지 방법

이전 포스팅에서도 간단히 적었듯이 형태소 분석기의 핵심은 마르코프 연쇄입니다. 각각의 형태소가 등장할 확률 및 한 형태소 다음에 다른 형태소가 등장할 확률을 계산해서, 그 확률이 가장 높은 형태소열을 찾는것이 형태소 분석기의 업무라고 할 수 있습니다. 원활한 이해를 위해 다음 예시를 들어보죠.

먹었다

위 단어를 분석한다고 해봅시다. 어떤 형태소가 들어갈 수 있는지 일단 나열해보자면, 다음과 같을 겁니다.

먹	었	다
먹/VV	었/EP	다/EF
먹/VX		다/EC
먹/NNG		다/MAG

'먹'에 일치될 수 있는 형태소는 크게 3개, '었'은 1개, '다'는 3개가 되겠습니다. 따라서 우리는 다음 6가지의 형태소 조합의 연쇄 확률을 모두 계산해야하지요.

먹/VV + 었/EP + 다/EF

먹/VX + 었/EP + 다/EF

먹/NNG + 었/EP + 다/EF

먹/VV + 었/EP + 다/EC

먹/VX + 었/EP + 다/EC

먹/NNG + 었/EP + 다/EC

먹/VV + 었/EP + 다/MAG

먹/VX + 었/EP + 다/MAG

먹/NNG + 었/EP + 다/MAG

이 경우는 매우 단순한 경우라고 할 수 있습니다. 형태소 조합이 더 복잡한 단어들도 많지요. 단어가 많아질 수록 계산해야할 경우의 수는 기하급수적으로 증가합니다. 그래서 0.3버전까지는 실제로 모든 조합을 다 계산하지 않고 경우가 많아질 경우 단어를 임의로 분해하여 계산한 뒤 합치는 방법을 사용했습니다.

0.4버전의 방법

잘 생각해보면 결국 형태소 조합은 하나의 흐름으로 볼 수 있습니다. 단어를 시작해서 형태소를 고르고 다음 형태소를 고르고... 고르는 작업을 반복해서 단어의 끝까지 도달하는 것이죠. 징검다리를 밟고 강을 건너는 것을 생각해볼 수 있겠습니다. 즉 가장 편하게 강을 건널 수 있는 징검다리를 고르는 작업이라고 보는 겁니다. 우리가 형태소 연쇄의 등장확률을 계산할 때 사용하는 것은 각각의 형태소의 등장확률과 형태소 간의 전이 확률이라고 했습니다. 만약 각각의 형태소를 그래프 상의 정점(node)로 생각한다면 형태소 간 전이 확률은 간선(edge)가 될 수 있겠죠. 즉 한 단어에서 나올 수 있는 형태소 조합은 그래프 형태로 표현이 가능하게 됩니다.

위의 그림처럼 말이죠! 위의 그림에서 파란 원은 각각의 형태소를 나타내고, 주황 원은 시작지점과 끝지점을 나타냅니다. 파란 원 안의 수치는 형태소의 등장확률의 로그값, 녹색 간선의 수치는 형태소 간 전이 확률의 로그값입니다. (물론 값은 설명을 위해 단순히 골랐습니다.)

이렇게 그래프 형태로 바뀌면 형태소 분석기가 해야할 일은 결국 시작지점^ 에서 끝지점$로 이어지는 가장 확률이 높은 경로를 찾는 일이 됩니다. 흔히 하던 최단 경로 찾기 문제가 되어버리는 것이죠. 즉 지나가는 간선과 정점의 숫자들을 더한 값이 가장 큰 경로를 찾으면 되는데, 이는 동적 계획법을 이용해서 중간중간 연산결과를 저장하면 매우 쉽게 풀수 있습니다.

즉, 매번 모든 경로를 탐색할 필요없이 부분 부분 저장해두었단 부분 최단 경로를 재활용하는 것이죠.

예를 위해 끝부분부터 거꾸로 올라가 보겠습니다. 먼저 다/EF - $의 최단 경로는 당연히 다/EF - $ (-0.3)입니다. 마찬가지로 해서 다음 표를 채울 수 있겠죠

시작	끝	경로	확률값
다/EF	$	다/EF - $	-0.3
다/EC	$	다/EC - $	-0.9
다/MAG	$	다/MAG - $	-0.7

그 다음은 었/EP - $의 최단 경로를 찾는 일입니다. 이미 다/EF, 다/EC, 다/MAG에서 끝으로 이어지는 최단 경로를 전부 찾아두었으니 이 값을 재활용하면 됩니다. 당연히 다/EF - $가 -0.3으로 제일 크므로, 었/EP - $의 최단 경로는 었/EP-다/EF-$ (-0.6)이 됩니다.

시작	끝	경로	확률값
었/EP	$	었/EP - 다/EF - $	-0.6

이제 먹/VV, 먹/VX, 먹/NNG에서 끝으로 이어지는 최단 경로를 계산해봅시다. 이미 었/EP - $의 최단 경로를 알고있으니 이 역시 간단합니다.

시작	끝	경로	확률값
먹/VV	$	먹/VV - 었/EP - 다/EF - $	-0.9
먹/VX	$	먹/VX - 었/EP - 다/EF - $	-1.0
먹/NNG	$	먹/NNG - 었/EP - 다/EF - $	-2.0

이제 시작점 ^에서 끝점$까지의 최단경로를 쉽게 구할 수 있겠죠. ^ - 먹/VV - 었/EP - 다/EF - $ (-0.9)가 됩니다. 이렇게 계산할 경우 3*1*3으로 9가지 경우(각각의 경우는 5번의 덧셈을 계산)를 일일히 계산하는 대신 3+1+3으로 7번(각각의 경우는 2번의 덧셈)의 노드에 대해서 계산함으로써 가장 확률이 높은 형태소 연쇄를 찾아낼 수 있습니다.

지금 소개한 알고리즘이 바로 비터비(Viterbi) 알고리즘입니다. 정확히는 비터비 알고리즘의 단순화된 버전이라고 할 수 있겠죠. 비터비 알고리즘은 루프가 있는 상황에서도 잘 수행되지만, 위의 방법을 루프가 있는 그래프에 적용하려면 약간 수정을 해야할 것입니다.

실제로 얼마나 빨라졌나?

그래서 한 번 버전별 속도를 비교해봤습니다.

시간(ms)	v0.2	v0.3	v0.4	v0.3 → v0.4 향상
텍스트A	11680	5656	1952	190%
텍스트B	8864	4865	3133	55%
텍스트C	7670	4294	2730	57%
텍스트D	15808	9073	6062	50%
텍스트E	21126	11055	3466	219%
총합	65148	34943	17343	101%
속도(MB/s)	0.077	0.143	0.288

평균적으로 2배 정도의 속도 향상이 있었다고 볼 수 있겠습니다. 만약 텍스트에 띄어쓰기 없이 더 긴 단어들이 많다면 속도차이가 더 많이 나겠죠. 그래도 매 버전마다 2배정도씩 속도 향상이 있었네요. 더 속도를 향상시킬 만한 방법이 또 떠오르면 좋겠네요. 

최신 버전의 한국어 형태소 분석기 Kiwi는 https://github.com/bab2min/Kiwi 에서 소스코드 및 바이너리를 다운 받을 수 있고, https://lab.bab2min.pe.kr/kiwi 에서 데모를 실행해볼 수 있습니다.