'꼬꼬마 형태소 분석기'는 띄어쓰기 오류에 덜 민감한 한글 형태소 분석기이다. 기본적으로 동적 프로그래밍(Dynamic Programming)을 이용해서 모든 가능한 형태소 분석 후보를 생성하고 적합하다고 판단되는 순서대로 분석 후보들을 정렬한다. 상용 형태소 분석기에 뒤지지 않는 성능을 보이기 위해서 다양한 최적화 방법을 이용한다. 속도를 위해서는 기분석 사전을 이용한 인접 조건 검사 방식을 이용하고, 품질을 위해서는 몇가지 휴리스틱(Heuristic)과 히든 마르코프 모델(HMM: Hidden Markov Model)에 기반한 확률 모델(Probabilistic Model)을 이용한다.
어절을 기본 단위로 하는 형태소 분석 알고리즘에서는 후순위 최장 일치법과 같은 방법을 이용해서 어절의 뒷부분부터 형태소를 분석하는 것으로 성능을 크게 높일 수 있다. 그러나 띄어쓰기 오류가 포함되었을 때에는 어디에서 띄어쓰기가 잘 못 됐는지 확인을 해야하며, 극단적으로 띄어쓰기가 전혀 되어 있지 않아서 매우 긴 어절이 입력이 되는 것과 같은 경우에는 이같은 방법을 이용하기 어렵다. 따라서, 어절의 앞부터 띄어쓰기 오류에 대한 가능성을 고려하면서 모든 가능한 형태소 조합들을 생성해 나가야 한다. 만약 음절을 기준으로 한다면, 각각의 음절을 기준으로 형태소를 생성하는 과정이 된다. 아래 그림과 같이 'abcdefgh'라는 어절이 있다면, 이는 각 어절의 사이 'qrstuvw'를 기준으로 형태소가 구분될지 않될지를 확인하는 과정이 된다.
┌─┬─┬─┬─┬─┬─┬─┬─┐
│a│b│c│d│e│f│g│h│
└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
│q│r│s│t│u│v│w│
└─┴─┴─┴─┴─┴─┴─┘
[그림 1] 형태소 분석 문제
예를 들어 r과 t 위치에서 형태소가 구분된다면, 위의 어절은 ab, cd, efgh라는 세개의 형태소로 이루어진 어절이 된다. 따라서 n개의 음절이 주어졌다면, n-1개의 음절 사이위치가 형태소 구분위치인지 아닌지에 대한 문제가 되며, 그 복잡도는 O(2n-1)이 된다. 일반적으로 한글이 한 어절을 이루는 음절 수가 5개를 넘어가는 경우가 많지 않다고 하면, 24 = 16으로 그리 복잡하지 않지만, 실제로 하나의 음절에서 하나 이상의 가능한 형태소가 나온다는 것을 감안한다며, 더욱 많은 조합이 발생할 수 있다. 또한 띄어쓰기 오류로 인해, 한 어절의 음절이 길어진다면 이는 더욱 복잡한 문제가 된다. 따라서 이를 해결하기 위해 일정량의 메모리를 사용하여, 순차적으로 최적 결과를 갱신하는 동적 프로그래밍을 사용한다.
[그림 2]에서 보이는 바와 같이 어절의 길이를 늘려 가면서 해당 길이에서 가능한 형태소 분석 조합들을 생성하여 메모리에 저장한다. 그리고 길이를 순차적으로 늘려가면서 기존에 저장되어 있는 결과를 이용해서 새로이 생성되는 결과를 만들어 낸다. 예를 들어 길이 5인 어절에 대한 분석을 수행할 때에는 1~4길이에서 나올 수 있는 형태소 분석 조합을 모두 생성되어 있기 때문에, 다음과 같은 조합에 대해서만 생성하면 된다.
mem[0] + new(1,4) -> (0,5) mem[1] + new(2,4) -> (0,5) mem[2] + new(3,4) -> (0,5) mem[3] + new(4,4) -> (0,5) mem[l]은 l+1길이의 어절에 대한 이미 분석된 형태소 조합을 말하고, new(l+1,e)는 추가될 수 있는 형태소를 의미한다. 이같은 과정을 순차적으로 거치고 나면, 길이 5에서 생성될 수 있는 모든 가능한 조합이 mem[4]에 저장되고, 최종적으로 길이 n인 어절이라면, mem[n-1]의 저장 위치에 가능한 조합들이 모두 생성되게 된다.
출처 : [꼬꼬마, 한글 형태소 분석기] http://kkma.snu.ac.kr/documents/index.jsp?doc=algorithm