[KIWI] 좋아, 형태소 분석기를 만들어봅시다. - 1

어쩌다 형태소 분석기를 개발하게 되었는지는 이전 글에 친절히 설명했고, 이번 글에서는 처음 개발하며 겪었던 문제를 소개합니다.

제일 처음 구현한 것은 아호코라식(Aho Corasick) 알고리즘이었습니다. Trie를 구성해 문자열 내에 포함되는 패턴을 빠르게 찾아내는 알고리즘이지요. 이름만 들으면 굉장히 어려울 것 같지만 다행히도 슬라이드세어에 한국어로 된 친절한 프레젠테이션이 있어서 https://www.slideshare.net/ssuser81b91b/ahocorasick-algorithm 이걸 보며 쉽게 구현할 수 있었습니다.

(이미지 출처: http://akarui-japan.deviantart.com/art/Kiwi-Icon-100334949)

한글처리 알고리즘 코딩하기

한국어 처리를 위해서 가장 처음에 해야할 일은 음절 글자를 음소단위로 쪼개는 일일 것입니다. (구현 방법에 따라 굳이 자소 단위로 분해하지 않고도 형태소 분석을 수행할 수도 있지만, 저는 Trie를 쓰기 위해서 자소 단위로 쪼개기로 했습니다.) 이는 워낙 흔하게 여기 저기 공유되고 있는 부분이라 특별히 사족을 붙여 설명하지는 않도록 하겠습니다.

string splitJamo(wstring hangul) { static char choTable[] = { 1, 2, 4, 7, 8, 9, 17, 18, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30 }; static char jongTable[] = { 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 26, 27, 28, 29, 30 }; string ret; for (auto c : hangul) { auto t = c - 0xAC00; int jong = t % 28; int jung = (t / 28) % 21; int cho = (t / 28 / 21); ret.push_back(choTable[cho]); ret.push_back(jung + 31); if (jong) ret.push_back(jongTable[jong - 1]); } return move(ret); }

다른 점은 ㄱ~ㅎ, ㅏ~ㅣ 까지의 모든 자소 글자를 1~51까지의 코드에 대응시켰다는 것입니다. 이렇게 표현할 경우 모든 한국어 단어는 1~51 사이의 코드의 연속으로 표현할 수 있게됩니다. (0부터 시작하지 않은 이유는 string을 null-zero문자로 사용할 수도 있게 하기 위함입니다.) 이렇게 되면 Trie 구조에서 자식 노드를 51개 짜리 배열로 사용하면 되니 효율적이라 할 수 있습니다. 만약 더 가짓수가 많았다면 해시맵 등의 구조를 사용해야할테니 메모리나 속도면에서 모두 손해가 되겠죠.

한국어 형태소 매칭을 위해 Trie 구조로 데이터를 담는 구조체 KTrie를 만들었습니다.

struct KTrie { #ifdef _DEBUG static int rootID; int id; #endif // _DEBUG KTrie* next[51] = {nullptr,}; KTrie* fail = nullptr; KTrie* exit = nullptr; int depth; KTrie(int depth = 0); ~KTrie(); void build(const char* str); KTrie* findFail(char i) const; void fillFail(); vector<pair<int, int>> searchAllPatterns(const vector<char>& str) const; };

Trie를 구축하는 것은 어렵지 않습니다. 입력되는 문자열을 가지고 차례대로 자식 노드로 이동해가면서, 자식 노드가 비어있을경우 만들어주면 되거든요.

#ifdef _DEBUG int KTrie::rootID = 0; #endif // _DEBUG KTrie::KTrie(int _depth) : depth(_depth) { #ifdef _DEBUG id = rootID++; #endif // DEBUG } KTrie::~KTrie() { for (auto p : next) { if(p) delete p; } } void KTrie::build(const char * str) { assert(str); assert(str[0] < 52); if (!str[0]) { exit = this; return; } int idx = str[0] - 1; if (!next[idx]) next[idx] = new KTrie(depth + 1); next[idx]->build(str + 1); } KTrie * KTrie::findFail(char i) const { assert(i < 51); if (!fail) // if this is Root { return (KTrie*)this; } else { if (fail->next[i]) // if 'i' node exists { return fail->next[i]; } else // or loop for failure of this { return fail->findFail(i); } } } void KTrie::fillFail() { for (int i = 0; i < 51; i++) { if (!next[i]) continue; next[i]->fail = findFail(i); auto n = this; while (!n->exit && n->fail) { n = n->fail; } exit = n->exit; } for (auto p : next) { if (p) { p->fillFail(); } } } vector<pair<int, int>> KTrie::searchAllPatterns(const vector<char>& str) const { vector<pair<int, int>> found; auto curTrie = this; int n = 0; for (auto c : str) { n++; assert(c < 52); while (!curTrie->next[c - 1]) // if curTrie has no exact node, goto fail { if(curTrie->fail) curTrie = curTrie->fail; else goto continueFor; // root node has no exact node, continue } // from this, curTrie has exact node curTrie = curTrie->next[c - 1]; if (curTrie->exit) // if it has exit node, a pattern has found { found.emplace_back(n - curTrie->exit->depth, n); } continueFor:; } return found; }

패턴 검색하는 함수도 같이 만들어주었습니다. 

처음엔 몰랐던 사항인데, 아호 코라식 알고리즘은 최장 패턴만 매칭해줍니다. 즉 CD, BCD, ABCD 라는 패턴이 있을경우, AABCD라는 문자열에서 패턴을 검색하게 되면 CD, BCD, ABCD를 모두 찾아주는 것이 아니라 ABCD만을 찾아내준다는 것이죠. 이 사실을 모르고 그냥 아무생각없이 코딩만 해놓았을때는, 왜 자꾸 특정 형태소를 못 찾아내는지 몰라서 한참 헤맸던게 기억에 남는군요.

이걸 수정하는건 어렵지 않은데요, 결국 ABCD가 매칭이 된다는 것은, 그것의 부분 패턴인 BCD, CD도 매칭된다는 것이므로 ABCD 패턴이 BCD에 대한 포인터를 들고 있게하고, BCD 패턴이 CD에 대한 포인터를 들고 있게해서, 패턴을 발견할때 서브패턴도 모두 같이 발견하도록 확장하면 됩니다.

형태소 간의 결합과 불규칙 활용은 어떻게 분석할까?

앞서 구현한 아호-코라식 알고리즘을 개량해서 모든 한국어 형태소 패턴을 찾아내도록 함수를 짠다고 해도, 어간과 어미가 결합하는 것이나 결합하면서 불규칙으로 바뀌는 활용을 분석해내는 것은 불가능합니다. 다행히도 대체로 한국어의 형태소 결합은 특정한 규칙을 따라서 이루어집니다. (맞춤법을 맞춰서 쓸 경우만 해당... 변화무쌍한 인터넷 용어들에서는 그런 규칙을 찾기가 어려워요) 예를 들어 오다의 과거형 왔다 의 경우 오 + 았 + 다 로 이루어지는데, 여기서는 ㅗ가 ㅏ와 결합하여 ㅘ가 되는 규칙이 적용이 된것이죠. 

따라서 패턴을 검색할때 ㅘ를 보면 이것이 아마 ㅗ + ㅏ 에서 왔을거라고 추정하고 분해해서 분석을 하도록 코딩해야합니다. 하지만 매번 형태소 분석시 마다 이런 규칙을 역추적하는 것은 굉장히 비효율적인 일이므로, 아예 사전에 결합된 형태를 메모리에 다 저장해두었다가 패턴 검색시에 사용하는게 좋겠죠?

그래서 다음과 같이 한국어 형태소 결합 규칙을 작성하고, 이를 통해 가능한 모든 결합을 찾아 사전에 그 결과를 만들기로 했습니다.

#첫번째 필드와 두번째 필드가 결합하여 세번째 필드의 결과를 만든다

#규칙 위에 붙은 VV, E와 같은 알파벳은 왼쪽과 오른쪽의 형태소 품사 조건을 지정해줌

#형태조건에는 정규식 사용 가능.

#바로 아래 규칙은 하/VV + 아 or ㅏ/E  => 해, 하여 가 된다는 뜻

VV E

ㅎㅏ ㅇ?ㅏ ㅎㅐ,ㅎㅏㅇㅕ

VX E

ㅎㅏ ㅇ?ㅏ ㅎㅐ,ㅎㅏㅇㅕ

XSV E

ㅎㅏ ㅇ?ㅏ ㅎㅐ,ㅎㅏㅇㅕ

XSA E

ㅎㅏ ㅇ?ㅏ ㅎㅐ,ㅎㅏㅇㅕ

V E

ㅎㅏ ㅇ?ㅏ ㅎㅐ,ㅎㅏㅇㅕ

ㅏ ㅇ?ㅏ ㅏ

ㅓ ㅇ?ㅓ ㅓ

ㅗ ㅇ?ㅏ ㅘ

ㅜ ㅇ?ㅓ ㅝ

ㄹㅡ ㅇ?([ㅏㅓㅣ]) ㄹㄹ\1 +Vowel

ㅡ ㅇ?ㅏ ㅏ +Positive

ㅡ ㅇ?ㅓ ㅓ -Positive

ㄹ ([ㄴㅂㅅㄹ]|ㅇㅗ) \1 +Vowel

ㄹ ㅁ$ ㄻ +Vowel

ㄷ ㅇ?([ㅏ-ㅣ]) ㄹㅇ\1 +Vowel

ㄷ ㄹ ㄹㄹ +Vowel

ㅂ ㅇ?ㅏ ㅇㅘ +Vowel

ㅂ ㅇ?ㅓ ㅇㅝ +Vowel

ㅂ ㅇ?ㅡ ㅇㅜ +Vowel

ㅅ ㅇ?([ㅏ-ㅣ]) ㅇ\1 +Vowel

ㅣ ㅇ?[ㅓㅕ] ㅕ

ㅚ ㅇ?ㅓ ㅙ

ㅐ ㅇ?ㅓ ㅐ

ㅔ ㅇ?ㅓ ㅔ

VA E

ㅣㄹㅓㅎ ㅇ?[ㅏㅓ] ㅣㄹㅐ

ㄱㅡㄹㅓㅎ ㅇ?[ㅏㅓ] ㄱㅡㄹㅐ

ㅈㅓㄹㅓㅎ ㅇ?[ㅏㅓ] ㅈㅓㄹㅐ

ㄸㅓㅎ ㅇ?[ㅏㅓ] ㄸㅐ

ㅏㅎ ㅇ?[ㅏㅓ] ㅐ

ㅓㅎ ㅇ?[ㅏㅓ] ㅔ

ㅑㅎ ㅇ?[ㅏㅓ] ㅒ

ㅕㅎ ㅇ?[ㅏㅓ] ㅖ

ㅎ ([ㄴㄹㅁ]|ㅅㅣ) \1

ㅎ   ㅇ?ㅡ   ㅡ

VC E

ㅣ ㅇ?ㅔ ㅖ

ㅣ ㅇ?ㅗ ㅛ

EP E

ㅅㅣ ㅇ?ㅓㅇㅛ ㅅㅔㅇㅛ

E E

ㅣ ㅇ?ㅓ ㅕ

위와 같이 제가 알고있는 한국어 형태소 결합 규칙을 모두 나열했습니다. (사실 여기 나열된 규칙들은 이전에 MorPHP로 한국어 동사 변화 구현할때 미리 해둔것이라서, 그대로 가져와서 재탕하느라 아주 편했습니다.) 그리고 파이썬 코드로 위의 조건에 맞는 모든 형태소를 찾아 실제로 결합시키고 그 결과를 저장하도록 했습니다.

그 결과 파일을 살짝 살펴보자면 다음과 같습니다. (왼쪽: 결합 결과, 오른쪽: 결합한 형태소들)

...

ㄹㅕㄷㅗ ㄹㅣ/EP+ㅇㅓㄷㅗ/EC

ㄹㅕㄷㅜ ㄹㅣ/EP+ㅇㅓㄷㅜ/EC

ㄹㅕㄹㅏㅇㅜ ㄹㅣ/EP+ㅇㅓㄹㅏㅇㅜ/EC

ㄹㅕㅅㅓ ㄹㅣ/EP+ㅇㅓㅅㅓ/EC

ㄹㅕㅇㅑ ㄹㅣ/EP+ㅇㅓㅇㅑ/EC

ㄹㅕㅇㅑㅈㅣ ㄹㅣ/EP+ㅇㅓㅇㅑㅈㅣ/EC

...

하지만 불규칙 활용하는 모든 동사나 형용사를 넣으면 위의 목록이 꽉꽉차서 터져버릴수도 있어요. (당장 ㅂ 불규칙, ㄷ 불규칙, ㅅ 불규칙하는 동사만 세어봐도 몇개인데...) 그래서 위와 같이 불규칙 활용하는 동사의 경우 모든 결합형을 다 기재하는 것이 아니라 공통적으로 변하는 불규칙 형태만 기재하도록 했습니다.

(더웠 : 덥/VA + 었/EP  처럼 전체를 기재하는 것이 아니라, 아래처럼 불규칙하는 ㅂ 받침부터만 기재한거죠.)

ㅇㅘㅆ ㅂ/V+ㅇㅏㅆ/EP +Vowel 7

ㅇㅘㅆㅇㅓㅆ ㅂ/V+ㅇㅏㅆㅇㅓㅆ/EP +Vowel 7

ㅇㅝㅆ ㅂ/V+ㅇㅓㅆ/EP +Vowel 7

ㅇㅝㅆㅇㅓㅆ ㅂ/V+ㅇㅓㅆㅇㅓㅆ/EP +Vowel 7

ㅇㅜㄹㅣ ㅂ/V+ㅇㅡㄹㅣ/EP +Vowel 7

ㅇㅜㅅㅣ ㅂ/V+ㅇㅡㅅㅣ/EP +Vowel 7

제일 오른쪽에 있는 숫자 7은 이 결합형이 연결될 수 있는 종류 번호입니다. 이 형태들은 ㅂ 불규칙 활용하는 동사/형용사에만 연결되어야 맞겠죠. 그러므로 덥/VA는 실제로 더/VA 7(ㅂ이 빠진 이유는 7번 종류의 결합형에 이미 ㅂ 받침이 포함되어 있기 때문)로 모델에 입력되어, 7번을 가진 결합형태하고만 연결되도록 해야합니다.

위에서 설명한것처럼 말뭉치에서 모델을 생성하도록 파이썬 코드를 작성해서 돌림으로써 불규칙 활용과 형태소 결합 문제를 해결했습니다.

실제로 이 모델을 불러와 형태소 분석을 하는 부분은 다음 글에서 계속 설명하도록 할게요.