[Kiwi] 지능형 한국어 형태소 분석기 ver 0.2

최초 릴리즈 이후 약간의 성능 개선을 실시했어요. 조금 설명하자면

* Trie 할당 방법을 바꿔서 연속된 공간에 배치하도록 수정했습니다. 그 결과 자식 노드를 포인터로 지정하는게 아니라 상대 인덱스로 지정할 수 있게 바꿨습니다.

struct KTrie { KTrie* next[51] = {nullptr,}; KTrie* fail = nullptr; ...

처음에는 0.1에서는 위와 같이 선언된 구조체를

struct KTrie { int next[51] = {0,}; KTrie* fail = nullptr; KTrie* getNext(int i) const { return next[i] ? (KTrie*)this + next[i] : nullptr; } ...

이것처럼 고쳤습니다. x64환경에서는 포인터가 8바이트를 차지하기 때문에 next배열은 8*51 = 408 바이트를 차지하게 됩니다. 전체 모델 로드시 약 15만개의 KTrie가 생성되기에, 프로세스 메모리의 대부분 이 녀석이 차지하게 되죠. 포인터 대신에 상대 인덱스를 저장하게 되면 x64 환경에서도 4바이트를 차지하게 되고, 그 결과 KTrie가 사용하는 메모리 양이 절반정도로 줄게 됩니다.

void KTrie::build(const char * str, const KForm * _form, const function<KTrie*()>& alloc) { assert(str); assert(str[0] < 52); if (!str[0]) { if(!exit) exit = _form; return; } int idx = str[0] - 1; if (!getNext(idx)) { next[idx] = alloc() - this; // new KTrie() 대신에 ...

그리고 new 로 KTrie를 생성하는 대신에 별도의 alloc 함수를 통해서 새로운 인스턴스를 생성하고 그것과 this간의 차이를 계산하여 저장합니다. 원래 next[i]이 가리키는 포인터를 얻기 위해서는 next[i]+this를 계산하면 되구요. 다행히도 next[i] == 0 인 경우는 없기 때문에 nullptr인 경우는 next[i]에 0을 넣어두면 딱 됩니다.

trieRoot.reserve(152000 + extraTrieSize); trieRoot.emplace_back(); for (auto& f : forms) { if (f.candidate.empty()) continue; trieRoot[0].build(f.form.c_str(), &f, [this]() { trieRoot.emplace_back(); return &trieRoot.back(); }); } trieRoot[0].fillFail();

trieRoot는 vector<KTrie>입니다. 미리 reserve로 적당한 크기를 생성해놓고, alloc에서는 할당요청이 올때마다 새로운 element를 추가해서 그 주소값을 넘겨줍니다. 이렇게 하면 KTrie의 모든 노드가 한 배열 상에 위치하므로 상대적인 위치 계산이 가능해지는거죠. 그와 동시에 연속적인 메모리에 위치하게 되므로 캐시 적중률을 높혀 성능향상을 조금이나마 더 할수있다는 장점도 있습니다!

그외에도 자잘한 메모리 최적화를 거쳐서 사용메모리 양을 대폭 줄였지만... PMI 분포 맵을 추가하면서 메모리 소모량이 대폭 다시 증가해버렸습니다.

* PMI 분포 맵을 추가하여 모호한 단어를 좀더 정확하게 분석할 수 있게 되었습니다.

1. 하늘을 훨훨 나는 새처럼.

2. 나는 사람입니다.

위 문장에서 '나는'은 같은 형태지만, 1에서는 날다 + -는, 2에서는 나 + 는 이라고 분석해내야하겠죠. 0.1 버전에서는 어절끼리는 독립이라는 가정하에 분석을 진행했기 때문에 1,2번 모두 나+는 ('날다' 보다 '나'가 등장확률이 높더라구요)이라고 분석해버렸습니다. 이를 해결하기 위해서는 주변 문맥을 살펴봐야합니다. 1번의 나는은 훨훨, 하늘과 같은 단어와 함께 쓰였기 때문에 날다 라는 동사라고 알아차릴수 있는거죠. 

이를 위해 분석시 모호성이 드러나는 단어 목록을 뽑아 그 단어들 주변에 등장하는 단어를 뽑아 단어쌍을 구축했습니다. 그리고 PMI(점별 상호정보량)를 계산하여 얼마나 연관성이 있는지를 구했죠. 연관있는 단어일수록 확률치에 가산점을 주어서 분석 결과를 수정하도록 만들었습니다.

PMI	메모리 사용량(MB)	정확도(%)
사용안함	60	82.4
>= 6	80	82.8
>= 5	132	83.6
>= 4	205	84.4
>= 3	294	85.2

PMI 분포맵을 사용안할 경우 약 60MB 정도 메모리를 차지한 반면, 6이상만 사용할 경우 80MB, 3 이상을 사용할 경우 294MB를 차지하게 됩니다. 반면 성능은... 큰 향상은 아니지만 조금씩 오르긴 하네요. 메모리를 덜 사용할 방법이 있나 강구해봐야겠습니다.

업데이트된 0.2버전 Kiwi는 https://github.com/bab2min/Kiwi 에서 확인해볼 수 있고, 온라인 데모는 https://lab.bab2min.pe.kr/kiwi 에서 이용할 수 있습니다.