나의 큰 O는 log x야

그새를 못 참고 업데이트했습니다. 이번 업데이트에서는 정확도 개선은 없었지만, 알고리즘 최적화와 메모리 관리 향상을 통한 성능 향상이 주요 내용입니다. 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

어쩌다 형태소 분석기를 개발하게 되었는지는 이전 글에 친절히 설명했고, 이번 글에서는 처음 개발하며 겪었던 문제를 소개합니다. 제일 처음 구현한 것은 아호코라식(Aho Corasick) 알고리즘이었습니다. Trie를 구성해 문자열 내에 포함되는 패턴을 빠르게 찾아내는 알고리즘이지요. 이름만 들으면 굉장히 어려울 것 같지만 다행히도 슬라이드세어에 한국어로 된 친절한 프레젠테이션이 있어서 https://www.slideshare.net/ssuser81b91b/ahocorasick-algorithm 이걸 보며 쉽게 구현할 수 있었습니다. (이미지 출처: http://akarui-japan.deviantart.com/art/Kiwi-Icon-100334949) 한글처리 알고리즘 코딩하기한국어 처리를 위해서 가장..

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

2월 말부터 갑자기 시작한 일이 있는데, 한국어 형태소 분석기를 직접 만들어 보는 일이었습니다. 처음에는 과연 할 수 있을까 싶기도 해서 블로그에 기록을 안 남기고 조용히 진행하고 있었습니다. 근데 기록을 남기지 않으니 시간이 갈 수록 헤매게 되는거 같아서 어느 정도 틀이 잡힌 시점에서 차곡차곡 기록을 남겨가며 프로젝트를 진행하기로 결심했습니다. (이미지 출처: http://akarui-japan.deviantart.com/art/Kiwi-Icon-100334949) 뜬금없이 왜 형태소 분석기를..?형태소 분석기를 만드는 삽질을 하게 된 이유를 구구절절히 풀자면 길어질거 같아서 짧게 정리하도록 할게요. 시작은 작년 초에 만들었던 KorpuSQL(http://bab2min.tistory.com/473) 이..

프로그래밍/NLP 2017. 3. 26. 21:55

C++ 컨퍼런스라는게 있는줄도 몰랐는데, 2014년부터 모던 C++ 애호가(?)들을 위한 컨퍼런스가 매년 개최되고 있었더군요. 한동안 C++로부터 관심이 멀어져있었는데, 컨퍼런스 내용을 보니 C++사랑이 듬뿍듬뿍 솟아오르는 것 같은 느낌입니다. 컨퍼런스 홈페이지는 https://cppcon.org/ 이고, 컨퍼런스 자료들은 모두 GitHub에 친절하게 올라가 있더라구요. 16년도 컨퍼런스 프레젠테이션들을 조금 살펴봤는데, 모던 C++의 발전 방향과 활용, 유용한 테크닉 등 여러 방면에 대해 다루고 있어서, C++를 공부하는 사람이라면 정말 많은 것을 배워갈 수 있을 거 같네요. 시간이 없어 다 읽어보지는 못했지만, 틈틈히 읽어보려고 합니다. 끝.

프로그래밍 2017. 2. 5. 15:38

일반 편집거리 알고리즘은 한글에 부적합하다두 텍스트가 얼마나 유사한지를 판단하는데 편집거리 알고리즘이 널리 쓰입니다. 주어진 텍스트 A가 B로 바뀌기 위해서는 글자를 몇번 빼고 더하고 바꿔야하는지를 세는 방법인데요, 이미 이를 효율적으로 계산하는 코드들이 인터넷 상에 많지요. 다만 한글에 이를 그대로 적용하는데에는 애로사항이 있습니다. 로마자 알파벳은 입력하기 위해 사람이 누르는 자판과 실제 입력되는 글자가 같은 반면, 한글은 그렇지 않다는 것이지요. 한글을 입력하는데에는 대게 두벌식 자판을 이용해 자음/모음을 따로 입력하고, 이를 입력기에 합쳐서 글자를 만들어내는 과정을 거치게 됩니다. 따라서 "갔다"와 "갓다"는 실제로 Shift키 하나 차이나는 텍스트임에도 불구하고 실제 입력된 결과물은 전체 글자인..

프로그래밍 2016. 12. 26. 03:25