나의 큰 O는 log x야

헷갈리는 사이시옷사이시옷은 참으로 묘한 녀석입니다. 이름은 분명 사이"시옷"인데 ㅅ소리가 전혀 나지 않거든요. 사이시옷의 역할은 두 개의 명사가 합쳐져서 복합 명사가 되는 과정에서 뒤의 명사가 된소리화(ㄲ/ㄸ/ㅃ/ㅆ/ㅉ)되거나 ㄴ소리가 첨가되는 현상을 반영하기 위해서 명사 사이에 ㅅ을 적기로 약속한 것이기 때문입니다. 그래서 적기는 ㅅ으로 적더라도 실제로는 ㅅ 소리가 절대 나지 않습니다. ('숫자'는 [숫자]로 소리나는 것이 아니라 [수짜]로 소리나고, '깻잎'은 [깨십]으로 소리나는 것이 아니라 [깬닙]으로 소리납니다.)사실 발음보다 더 골이 아픈 문제는 사이시옷을 언제 써야하는지, 언제 쓰지 말아야하는지를 구분하는게 참 어렵다는 겁니다. 잘 모르는 복합명사를 받아적을 일이 생겨서, 그 명사에 사이시옷..

프로그래밍/NLP 2024. 11. 4. 02:20

최근 Kiwi 형태소 분석기 0.6 버전 업데이트를 실시했습니다. 사실 엄청 바뀐건 없고, 이전 버전에서 사용하던 최적화를 좀더 한 단계 끌어올리는 작업을 수행했습니다. 0.4버전에서 도입한 그래프 기반 경로 탐색 알고리즘의 경우, 이상하게도 끝쪽에서 앞쪽으로 분석을 진행했습니다. 당시에 왜 이렇게 설계했는지 모르겠는데, 개발하고 보니, 역방향으로 추적을 진행하더라구요. 사실 경로 탐색을 진행하는게 순방향인지 역방향인지 자체는 성능에 영향을 미치지 않습니다만, n-gram 언어모델을 캐싱하는데에는 순방향이 훨씬 유리합니다. 0.5버전에서 Kneser-Ney smoothing을 적용한 n-gram 언어 모델을 바탕으로 형태소가 출현할 확률을 계산하도록 알고리즘을 교체하였는데요, 이게 약 2만 여개의 형태소..

프로그래밍/NLP 2018. 12. 9. 23:23

웹 버전 말고 윈도우즈용 GUI 버전의 Kiwi 형태소 분석기를 구하시는 분들이 의외로 많으셔서, 간단하게나마 GUI를 입힌 버전을 만들어보았습니다. (2022-03-20일자 업데이트) https://github.com/bab2min/kiwi-gui/releases/에서 최신 버전의 kiwigui_win_v0.**.*.zip (별표는 버전 넘버) 파일을 다운 받으시는걸 권장합니다. 입력된 한국어 문장을 형태소 분석하여 출력해주는 것이 모든 기능입니다. KiwiGui가 받아들이는 인코딩은 CP949(ANSI), UTF-8, UTF-16 BE, UTF-16 LE 입니다. 출력 파일은 항상 UTF-8로 나옵니다. 기본 분석기 창. 분석할 텍스트를 입력하거나 텍스트 파일을 열어서 분석을 진행할 수 있습니다. 일..

프로그래밍/NLP 2017. 10. 31. 23:00

속도가 만족할 만큼 나오지 않아서 아쉽길래 한동안 접어두고 있었는데, 갑자기 좋은 아이디어가 떠올라서 업데이트를 해보았습니다. 약간의 알고리즘 수정으로 최소 +50%~200%의 속도 향상을 달성할 수 있었는데, 기록하지 않고 넘어가기에 너무 아까워서 포스팅을 써보았습니다. 0.3버전까지 방법이전 포스팅에서도 간단히 적었듯이 형태소 분석기의 핵심은 마르코프 연쇄입니다. 각각의 형태소가 등장할 확률 및 한 형태소 다음에 다른 형태소가 등장할 확률을 계산해서, 그 확률이 가장 높은 형태소열을 찾는것이 형태소 분석기의 업무라고 할 수 있습니다. 원활한 이해를 위해 다음 예시를 들어보죠. 먹었다 위 단어를 분석한다고 해봅시다. 어떤 형태소가 들어갈 수 있는지 일단 나열해보자면, 다음과 같을 겁니다. 먹었다 먹/V..

프로그래밍/NLP 2017. 9. 11. 02:59

그새를 못 참고 업데이트했습니다. 이번 업데이트에서는 정확도 개선은 없었지만, 알고리즘 최적화와 메모리 관리 향상을 통한 성능 향상이 주요 내용입니다. 0.3 버전 업데이트 내역속도가 0.2 버전 대비 약 86%향상되었습니다. 1.알고리즘 최적화실행 속도를 높이기 위해서는 실행 시간의 대부분을 차지하는 함수를 튜닝하는게 좋습니다. 다행히도 마솔루야, 거룩하신 MS께서 내리신 Visual Studio에서 성능 분석에 아주아주 좋은 기능을 제공하더라구요. 이 기능을 활용하여 실행시간의 대부분을 소모하는 함수를 찾아 들어가보니 코드 순서를 바꾸고 불필요한 할당을 제거할 수 있는 부분이 있어서 라인 몇줄을 옮기고 지웠습니다. 별거 아닌 것 같은 작업이었지만 이를 통해 10%이상의 성능 향상을 얻을 수 있었죠. ..

프로그래밍/NLP 2017. 5. 5. 21:02

최초 릴리즈 이후 약간의 성능 개선을 실시했어요. 조금 설명하자면 * 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..

프로그래밍/NLP 2017. 4. 29. 14:03

(이미지 출처: http://akarui-japan.deviantart.com/art/Kiwi-Icon-100334949) 속도를 향상시키기한 어절이 A B C D E F와 같이 6개의 형태로 쪼개질 수 있고 A,B,C,D,E,F 각각에 일치가능한 형태소가 4개씩 있다고 하면 전체 가능한 형태소 조합은 4^6 = 4096가지입니다. 각각의 조합마다 6개의 형태소 등장확률 계산 및 6개의 품사 간 전이확률을 계산해야 하니 12회의 확률 계산이 필요하네요. 즉 4096 * 12 = 49152회의 연산이 필요합니다. 이 모든 조합을 계산하기에는 시간이 너무 아깝습니다. 어차피 이 중에서 우리가 알고싶은건 가장 등장확률이 높은 조합 1개인걸요. 만약에 A B C D E F를 A B C / D E F 로 두 덩이..

프로그래밍/NLP 2017. 3. 26. 22:01

(이미지 출처: http://akarui-japan.deviantart.com/art/Kiwi-Icon-100334949) 하나의 단어를 형태소로 쪼개다보면 일치하는 패턴이 여러개 등장하는 경우가 많습니다. 예를 들어 '디자인하여' 라는 어절을 쪼개보면디자인하여 => 디자인 + 하 + 아가 되는데, 각각의 덩어리에 일치하는 형태소 목록은 다음과 같아요. 디자인 하 아 디자인/NNG 하/VV 아/EC 하/XSV 아/EF 하/XSA 아/IC 하/NNG ... '하'와 '아'의 경우 일치하는 녀석들이 더 많지만 여기서는 설명의 단순화를 위해 위와 같다고 하겠습니다.이 경우 조합 가능한 모든 경우의 수는 12가지가 되겠죠. 하지만 디자인하여는 디자인/NNG + 하/XSV + 아/EC로 분석되는게 맞습니다. 그러..

프로그래밍/NLP 2017. 3. 26. 22:01