초경량 클래식 형태소 분석기 개발기

모바일 환경 제약과 언어 선택

• 카카오톡 기능 지원을 위해 모바일 환경에 최적화된 경량 형태소 분석기 개발이 필요했다.
• 실행 파일 크기, 메모리 사용량, 사전 파일 크기 등 엄격한 리소스 제약이 핵심 고려 사항이었다.
• Rust 대비 **C++**이 모바일 클라이언트의 기존 라이브러리 활용으로 바이너리 크기를 200KB 수준으로 줄일 수 있어 최종 선택되었다.
• C++20의 std::span, Concepts 등 현대적인 기능으로 코드 가독성과 안정성을 높였다.

Trie 압축: LOUDS 알고리즘

• 형태소 분석기의 핵심인 사전 데이터의 효율적인 압축을 위해 LOUDS(Level-Order Unary Degree Sequence) 알고리즘을 채택했다.
• LOUDS는 Trie 구조를 비트 시퀀스로 표현하여 정보 이론적 하한에 근접한 압축률을 제공한다.
• 한글에 최적화된 인코딩 방식을 적용하여 사전 데이터 크기를 더욱 줄였고, 약 76만 노드를 9.4MB로 압축했다.

Select 비트 연산 최적화

• LOUDS 기반 Trie 검색의 핵심인 select0 연산이 성능 병목(전체 검색 시간의 약 90%)으로 작용했다.
• 비트 시퀀스를 64비트 청크로 나누고, 각 청크 경계까지의 0의 누적 개수를 미리 기록하여 바이너리 서치로 빠르게 청크를 찾았다.