#1 : 한글처리 알고리즘
-> 한국어 처리를 위해서 가장 처음에 해야할 일은 음절 글자를 음소단위로 쪼개는 일일 것입니다. Trie를 쓰기 위해서 자소 단위로 쪼개기로 함.
-> 유니코드를 사용하여 초성 중성 종성을 분리함.
-> ㄱ 부터 ㅎ, ㅏ 부터ㅣ 까지의 모든 자소 글자를 1~51까지의 코드에 대응시킴.
#2 : 한국어 형태소 매칭을 위한 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;
};#3 : 입력되는 한글데이터로 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) // trie 자료구조에 한글 저장히기
{
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;
}[아호-코라식 알고리즘] 참조 https://m.blog.naver.com/PostView.nhn?blogId=kks227&logNo=220992598966&proxyReferer=https%3A%2F%2Fwww.google.com%2F 참조
#4 : 형태소 간의 결합과 불규칙 활용은 분석은 어떻게 ?
위의 아호-코라식 알고리즘을 이용한다고 해도 어간과 어미의 결합시 일어나는 불규칙 활용을 분석해내는 것은 불가능함. 따라서 대부분의 한국어의 결합의 형태인
규칙 활용을 이용함. (예시, 오다 + 왔다 =>> 오 + 았 + 다 so, ㅗ + ㅏ = ㅘ)
따라서 모든 결합 규칙들을 작성하고 사전에 만들어 놓은 다음에 메모리에 다 저장해두었다가 패턴 검색시에 이용함. (형태소 결합규칙사전 참조)
불규칙 활용하는 모든 동사와 형용사는 해당 사전에 넣지못함. 너무 많기 때문에..
따라서, 모든 결합형을 기재하는 것이 아니라, 공통적으로 변하는 불규칙 형태만 기재하도록 하였음.
게다가
ㅇㅘㅆ ㅂ/V+ㅇㅏㅆ/EP +Vowel 7
라고 사전에 쓰여 있을 때, 이 의미는 더웠 : 덥/VA + 었/EP 처럼 전체를 기록하는 것이 아니라, 불규칙하는 'ㅂ'받침 부터만 기록함.
또한 제일 오른쪽의 숫자 7은 해당 결합형이 연결 될 수 있는 종류 번호임. 따라서 덥/VA는 실제로 더/VA 7 로 모델에 입력되며, 7을 가진
결합 형태하고만 연결되도록 해야함.
조금 더 자세히 알아보면,
디자인하여 -> 디자인 + 하 + 아 로 분리가 됨.
이때 각각의 덩어리들(디자인, 하, 아) 에 대해 일치하는 형태소 목록은 다음과 같음.
디자인 : NNG
하 : VV, XSV, XSA, NNG
아 : EC, EF, IC,.....
'아'는 사실 더 많지만 이정도만 하였을 때, 가능한 모든 경우의 수는 12가지임. 하지만 우리가 아는 '디자인하여' 는 디자인/NNG + 하/XSV + 아/EC
로 분석되는게 맞음. 따라서 이를 해결하기 위해 확률 모델을 도입함.
#5 : 확률 모델
우리가 원하는 정답을 구하기 위하여 우리는 확률 이론을 사용함.
디자인/NNG + 하/XSV + 아/EC 가 등장할 확률 =
(디자인/NNG가 등장할 확률) * (하/XSV가 디자인/NNG 뒤에 등장할 확률) * (아/EC가 하/XSV 뒤에 등장할 확률)
//한 형태소는 바로 앞의 형태소로부터만 영향을 받는다고 가정을 한겁니다. (마르코프 모델)
따라서 학습용 코퍼스에서 해당 확률을 구하여 사용하면 됨.
하지만 학습용 코퍼스에서 (하/XSV가 디자인/NNG 뒤에 등장하는 경우)는 매우 드물게 나옴. 따라서 한 형태소 뒤에 다른 형태소가 나올 확률을
소규모의 학습용 코퍼스에서 구하는 것은 불가능함.
하/XSV가 디자인/NNG 뒤에서 등장할 확률이 XSV가 NNG뒤에서 등장할 확률가 비례할거라 가정하고, XSV가 NNG 뒤에서 등장할 확률로 대체해서 사용하기로 함.
따라서 우리가 원하는 확률은 이렇게 구할 수 있다.
(하/XSV가 디자인/NNG 뒤에서 등장할 확률) => (하/XSV가 등장할 확률) * (XSV가 NNG 뒤에서 등장할 확률)
마찬가지로 아/EC가 하/XSV 뒤에서 등장할 확률도 추론할 수 있다.
그전에 어절을 마치는 확률을 덧붙여서 성능을 좋게하기 위하여, 우리는 어절의 끝에 종결 표식 $ 를 넣는다.
(이유; 한국어 맞춤법 상 어절을 마치는 형태소는 정해져 있기때문. 동사의 경우 먹다, 먹어처럼 어미로 어절이 끝나지, '먹' 만으로 어절이 구성되는 경우는 없다. 따라서 '먹'을 보면 먹/NNG로 해석해야지 먹/VV으로 해석하면 오류. )
즉, 따라서 디자인/NNG + 하/XSV + 아/EC 가 등장할 확률 =
(디자인/NNG가 등장할 확률) * (하/XSV가 등장할 확률) * (아/EC가 등장할 확률) * (XSV가 NNG 뒤에 등장할 확률) * (EC가 XSV 뒤에 등장할 확률) * ($가 EC뒤에 등장할 확률) 로 추정가능하다.
따라서 우리는 모든 12가지의 확률을 계산하고, 그중 확률이 가장 높은 녀석으로 고르면 됨.
하지만 문제가 있음. 어절 내의 형태소의 개수가 늘어날 때마다, 조합 가능한 수는 기하급수적으로 늘어나게 됨. 따라서 모든 확률을 구해서
검사하는데에 너무 시간이 오래걸림.
하지만 대부분의 케이스들의 경우 검사할 필요조차 없는, 결국엔 탈락할 후보들임이 자명하기 때문에, 사전에 제거를 해놓을 필요성이 제기됨.
#6 : 결합 조건 검증
한국어의 조사는 바로 앞 단어의 받침 유무에 따라서 결합여부가 달라짐. '은,이,을' 은 앞에 받침이 있는 경우, '는, 가, 를'은 받침이 없는 경우만 결합 가능함.
비슷하게 어미는 동사의 극성(양성/음성)에 따라서 결합여부가 달라집니다. '었'은 음성인 동사에, '았'은 양성인 동사에 붙음.
이런 결합조건을 가지고 사전에 결합 불가능한 조합을 배제하면 성능을 향상시킬 수 있음.
따라서 이러한 단어가 얼마나 있는지 모르므로, 세종 계획 코퍼스를 분석해서 조사와 어미가 등장하는 양상을 살펴보도록 파이썬 코드를 작성.
앞 단어가 받침이 있는 경우 등장하는 비율과 받침이 없는 경우 등장하는 비율, 양성인 경우 등장하는 비율과 음성인 경우 등장하는 비율을 살펴서 한쪽으로 비율이
치우친 경우 (90%이상인 경우) 그 형태소에 표시를 매겨 모델에 포함시킴.
또한 실제로 분석시, 모든 형태소 조합의 확률을 계산하지 않고, 조건을 만족하는 경우만 고려하기로 하였음
--> 그결과 속도의 향상은 ?? 크게 빨라지지 않음. 대신에 정확도가 올라감.
따라서 알고리즘을 수정할 필요성이 대두됨.
#7 : 알고리즘을 수정하기
수정 1; 분할정복(Divide and Conquer) : 만약 한 어절이 A B C D E F와 같이 6개의 형태로 쪼개질 수 있고 A,B,C,D,E,F 각각에 일치가능한 형태소가 4개씩 있다고 하면
전체 가능한 형태소 조합은 4^6 = 4096가지. 각각의 조합마다 6개의 형태소 등장확률 계산 및 6개의 품사 간 전이확률을
계산해야 하니 12회의 확률 계산이 필요함.
즉 4096 * 12 = 49152회의 연산이 필요합니다. 이 모든 조합을 계산하기에는 시간이 너무 낭비가 심함.
어차피 이 중에서 우리가 알고싶은건 가장 등장확률이 높은 조합 1개만 이므로.
따라서 이를 분할정복(Divide and Conquer)을 이용하여,
A B C D E F를 A B C / D E F 로 두 덩이로 나눈다고 생각.
앞의 덩어리에서 나오는 조합은 4^3 = 64가지, 뒤의 덩어리에서 나오는 조합 역시 4^3 = 64가지.
단 앞의 덩어리는 크기가 3이므로 3번의 형태소 등장확률, 3번의 품사 간 전이확률을 계산하면 되니 64*6번 연산을 하면 됩니다.
뒤의 덩어리 역시 64*6번만의 연산이 필요하구요. 즉 덩어리별 모든 조합의 확률을 계산하는데에는 384회의 연산만이 필요합니다.
그리고 이 두 덩어리를 합치는 경우의 수는 6464 = 4096번이니, 3842 + 4096 = 4864회의 연산이 필요.
다뤄야할 조합을 큰 덩어리에서 작은 덩어리 둘로 나눴더니 해야할 연산이 1/10로 감소함.
수정 2; 가장 확률높은 몇가지끼리만 비교; A B C / D E F 덩어리에서 각 덩어리마다 64가지의 조합이 나오는데, 최종 조합을 계산할때 64*64 경우를 모두 다룰 필요는 없다.
어차피 우리는 가장 확률값이 높은 1개의 조합만 알면 되고, 전체 조합의 순위를 알 필요는 없으므로.
그러니 애초에 A B C에서 가장 확률이 높은 조합 5개 정도, D E F에서 가장 확률이 높은 조합 5개 정도를 뽑아내서, 5*5가지 경우만 봐도 높은 정확도를
기대 할 수 있다.
(사실 이 생각은 약간의 위험성을 안고 있습니다. A B C 또는 D E F에서 낮게 나오는 조합이 A B C D E F로 합쳐졌을때 높게 나올수도 있기 때문이죠.
그런 경우가 많지는 않겠지만 종종 등장할 수 있으므로, 이렇게 상위 조합만 다루는 방식은 속도를 향상시킬수 있지만 약간의 정확도 희생을 감수해야합니다.)
만약 이 방식대로라면 우리가 최종 계산해야할 연산 횟수는 3842 + 4096 이 아니라 3842 + 25 = 793회로 감소한다.
수정 3; 캐싱(Cashing); 현재 모델에서는 분석 결과는 독립적이므로 자주 분석하는 어절의 결과를 메모리에 저장해두면 다음번에 재사용할 수 있습니다.
다행히도 한국어의 어절 분포 역시 지프의 법칙을 따르므로(하지만 그 경향이 어절=단어인 영어에 비해서는 약하다.) 자주 사용하는 어절은 정말 자주 쓰여서
캐싱(Cashing)의 효과를 톡톡히 볼 수 있다. 경우에 따라서는 20~30%의 속도 향상도 가능.
(지프의 법칙이란 ? 수학적 통계를 바탕으로 밝혀진 경험적 법칙으로, 물리 및 사회 과학 분야에서 연구된 많은 종류의 정보들이 지프 분포에 가까운 경향을 보인다는 것을 뜻한다.)
(지프의 법칙 예시] 어떠한 자연어 말뭉치 표현에 나타나는 단어들을 그 사용 빈도가 높은 순서대로 나열하였을 때, 모든 단어의 사용 빈도는 해당 단어의 순위에 반비례한다. 따라서, 1번순위는 2번순위보다 빈도가 2배 높으며, 3번순위보다는 3배 높다.)
