안녕하세요, AI추천플랫폼팀의 제이입니다.

카카오톡에서 특정 기능을 지원하기 위해 경량 형태소 분석기가 필요했습니다. 최근에는 딥러닝 기반의 정확도가 높은 형태소 분석 라이브러리가 많이 등장했지만, 모바일 환경에서는 단순히 정확도만으로 선택하기 어렵습니다. 실행 파일의 크기, 메모리 사용량, 그리고 사전 파일의 크기까지 함께 고려해야 하기 때문입니다. 특히 이 요소들은 모바일 애플리케이션의 용량과 성능에 직접적인 영향을 미칩니다.

이러한 제약 조건을 만족하기 위해, 모바일 환경에서 실행되는 경량 형태소 분석기를 직접 개발하게 되었습니다. 이 글에서는 그 과정에서 겪은 개발 이야기와 경험을 공유하려고 합니다. 언어 선택과 알고리즘에 대한 이야기가 주된 내용이기 때문에, 형태소 분석에 대한 배경 지식이 없더라도 가볍게 읽을 수 있도록 작성했습니다.

개발할 형태소 분석기는 모바일 클라이언트에서 직접 실행되는 것을 전제로 했습니다. 따라서 라이브러리 바이너리 크기와 실행 시 사용하는 리소스 용량에 명확한 제한이 있었고, 메모리 사용량 또한 최대한 작아야 했습니다. 서버 환경과 달리 모바일에서는 이러한 제약이 곧 기능의 사용 여부를 결정짓는 중요한 요소가 됩니다.

이러한 제약 조건을 토대로, 형태소 분석 방식은 비교적 전통적인 접근을 선택했습니다. 미리 구축된 사전 데이터를 기반으로 단어의 형태소 확률을 계산하고, 이를 조합해 문장 전체의 형태소 확률을 Viterbi 알고리즘으로 계산하는 방식입니다. 정확도나 복잡함보다는 예측 가능한 성능과 작은 런타임 오버헤드를 우선시한 선택이었습니다. 이후 섹션에서 사전 데이터의 압축과 효율적인 탐색을 위한 자료구조 선택에 대해 다루겠습니다.

Rust vs C++

저는 과거에 C++을 주로 사용했지만, 최근 고성능 서버 사이드 개발에 Rust를 적극적으로 사용하고 있습니다. Rust는 메모리 안전성과 명시적인 오류 처리, 그리고 현대적인 언어 기능 덕분에 생산성과 안정성 모두에서 만족도가 높았습니다. 따라서 형태소 분석기를 개발할 때도 자연스럽게 Rust와 C++ 두 가지 선택지를 놓고 고민하게 되었습니다.

개인적으로는 C++을 과거에 주력으로 사용해 왔고, Rust 역시 실무에서 사용하고 있었기 때문에 두 언어에 대한 숙련도 차이는 크지 않다고 판단했습니다. 선택의 기준은 언어 자체의 우열보다는, 이번 문제의 제약 조건을 얼마나 잘 만족할 수 있는가였습니다.

주목할 제약은 라이브러리의 바이너리 크기였습니다. 모바일 환경에서 사용되는 이 형태소 분석기는 라이브러리 용량에 비교적 엄격한 제한이 있었고, KB 단위의 크기 차이도 고려 대상이 되었습니다. Rust로 간단한 Hello, World! 수준의 라이브러리를 빌드해 보아도, 제가 사용한 타깃 빌드 환경에서는 기본 설정만으로도 바이너리 크기가 MB 단위로 생성되는 경우가 많았습니다. 간단한 구현에서 LTO(Link Time Optimization)나 strip 같은 최적화를 적용해도 경험적으로는 대략 2~3MB 정도의 크기가 나왔습니다. 표준 라이브러리를 제외한 no_std 환경(#![no_std])으로 빌드하면 바이너리 크기를 크게 줄일 수 있지만, 이 프로젝트의 범위에서는 개발 생산성이 크게 떨어진다는 단점이 있었습니다. 문자열 처리나 오류 처리, 파일 입출력 등 기본적인 기능까지 직접 다루어야 했기 때문입니다. 제약 조건을 만족하는 형태소 분석기를 빠르고 안정적으로 만드는 것이 목적이기 때문에 이 선택은 적절하지 않다고 보았습니다.

혹시 러스트 바이너리 크기를 줄이는 것에 고민하고 있다면, 이 저장소를 참고해보시길 권장합니다. 다양한 최적화 기법과 설정을 통해 러스트 바이너리 크기를 최소화하는 방법이 잘 정리되어 있습니다.

반면 C++의 경우에도 표준 라이브러리의 코드 크기는 무시할 수 없지만, 이번 프로젝트의 모바일 클라이언트 환경에서는 다른 라이브러리들로 인해 이미 libstdc++ 혹은 libc++가 포함되어 있었습니다. 그 결과, 라이브러리 자체에는 핵심 로직만 포함해 표준 라이브러리를 링크하는 방식으로 바이너리 크기를 크게 줄일 수 있었습니다.

이러한 이유로 최종적으로는 C++을 선택해 형태소 분석기를 구현했습니다. 결과적으로 최종 산출물의 라이브러리 크기는 약 200KB 수준으로, 초기 목표로 했던 용량 조건을 안정적으로 만족할 수 있었습니다.

C++20

짤막하게 C++ 언어 버전에 대해서도 이야기해보겠습니다.

이번 프로젝트에서는 C++ 언어 버전으로 C++20을 선택했습니다. C++20에서 추가된 여러 기능들이 코드의 표현력과 안전성을 높여줄 수 있을 것으로 기대했기 때문입니다. 한편으로는 타깃 플랫폼에서 C++20 기능을 충분히 지원하는지에 대한 우려도 있었습니다.

필요로 하는 기능들의 지원 여부는 플랫폼별로 확인했습니다. iOS의 경우 C++ language support 문서에서 지원 현황을 확인할 수 있는데, 이번 프로젝트에서 사용하려던 대부분의 기능들이 이미 지원되고 있었고, 요구되는 툴체인 버전도 비교적 낮은 편이어서 실제 적용에 큰 제약은 없다고 판단했습니다.

기존 C++17 이전 코드에서는 복사 비용을 줄이고 명확한 표현을 위해 gsl::span을 자주 사용했고, 템플릿 제약을 표현하기 위해 std::enable_if와 SFINAE 패턴을 반복적으로 사용하고 있었습니다. C++20으로 전환하면서 이러한 부분을 표준 std::span과 Concepts로 자연스럽게 대체할 수 있었고, 그 결과 코드의 의도가 훨씬 명확해졌습니다. 가독성과 유지보수성 측면에서도 긍정적인 변화였습니다.

이 외에도 [[likely]]와 같은 분기 힌트 어트리뷰트, Designated Initializers, std::ranges 등 C++20의 여러 기능들이 최적화와 코드 가독성, 안정성을 높이는 데 도움이 되었습니다.

Trie 압축: LOUDS 선택

구현한 형태소 분석기는 단어별 형태소와 그 확률을 기록한 사전 데이터에서 단어를 검색하고, 형태소 간 전이 확률을 함께 고려해 문장 전체에서 가장 확률이 높은 형태소 조합을 계산합니다. 이 과정에서 사전 데이터는 형태소 분석기의 핵심이자, 동시에 전체 리소스의 대부분을 차지하는 요소였습니다. 따라서 전체 시스템의 성능과 용량을 좌우하는 관건은 사전 데이터를 얼마나 효율적으로 압축할 수 있는가였습니다.

사전 데이터는 일반적으로 Trie 자료구조로 구현합니다. 문자열의 접두어를 공유할 수 있어 중복을 줄일 수 있고, 단어 검색에도 적합하기 때문입니다. Trie 구현은 여러가지 방법이 있습니다. 포인터 기반 Trie부터 Double-Array Trie, 다양한 압축 Trie까지 여러 선택지가 있고, 각 구현은 메모리 사용량과 접근 성능에서 서로 다른 특성을 가집니다.

여러 구현을 검토한 끝에, 이번 프로젝트에서는 LOUDS(Level-Order Unary Degree Sequence) 알고리즘을 사용해 Trie를 표현하기로 했습니다. LOUDS는 Trie의 구조를 포인터 대신 비트 시퀀스로 표현하는 자료구조 기법으로, 정적으로 구축된 사전에 특히 잘 맞는 표현 방식입니다.

예를 들어 아래와 같은 트리를 생각해봅시다.

이 트리를 위에서 아래로 왼쪽에서 오른쪽으로 순서대로 번호를 매기면 다음과 같습니다.

       (0)
       /  \
     (1)   (2)
    /  \     \
   (3)  (4)   (5)
          \
          (6)

이런 트리 형태를 비트 시퀀스로 표현합니다. 노드의 순서대로 자식의 수만큼 1을 적고, 자식이 더 이상 없음을 나타내기 위해 0을 적습니다. 예를 들어 루트 노드(0번)는 자식이 2개이므로 “110”을 적고, 1번 노드는 자식이 2개이므로 “110”을 적고, 2번 노드는 자식이 1개이므로 “10”을 적습니다. 3, 5, 6번 노드는 자식이 없기 때문에 “0”을 적습니다. 이런 식으로 모든 노드를 순서대로 표현하면 다음과 같은 비트 시퀀스가 됩니다.

110110100100

또한 각 노드에 해당하는 문자와 다른 정보를 별도의 배열에 저장합니다. 예를 들어 문자와 단어 여부, 형태소를 저장한다고 하면, 노드 순서대로 다음과 같이 배열을 구성할 수 있습니다. (JSON 형식으로 표현했습니다.)

[
  {"문자": "", "단어 여부": false},
  {"문자": "카", "단어 여부": false},
  {"문자": "커", "단어 여부": false},
  {"문자": "페", "단어 여부": true, "형태소": "명사"},
  {"문자": "카오", "단어 여부": true, "형태소": "명사"},
  {"문자": "피", "단어 여부": true, "형태소": "명사"},
  {"문자": "톡", "단어 여부": true, "형태소": "명사"}
]

이렇게 비트 시퀀스와 노드 정보를 별도로 저장하면, 포인터 없이도 트리 구조를 표현할 수 있습니다. 단어를 검색할 때는 비트 시퀀스를 탐색하면서 자식 노드의 위치를 계산하고, 해당 노드의 문자가 일치하는지 확인하는 방식으로 진행합니다.

예를 들어 “카카오”를 검색한다고 하면, 먼저 루트에서 자식의 개수를 비트 시퀀스에서 읽어옵니다.

루트 노드는 처음으로 0이 나올 때까지 1의 개수를 세어 자식이 2개임을 알 수 있습니다. 1이 출현하는 위치는 0번과 1번이므로, 자식 노드의 인덱스는 1번과 2번이 됩니다.
1번 노드의 문자가 “카”와 일치하므로, 다시 1번 노드에서 자식의 개수를 읽어옵니다.
1번 노드의 자식 노드 인덱스는 2번째로 0이 나올 때까지 1을 세어 계산할 수 있습니다. 이 때 1이 출현하는 위치는 2번과 3번이므로, 자식 노드의 인덱스는 3번과 4번이 됩니다.
4번 노드의 문자가 나머지 “카오”와 일치하고 명사 형태소 정보도 확인할 수 있으므로, “카카오”가 사전에 명사로 등록되어 있음을 알 수 있습니다.

LOUDS는 트리 구조를 표현하는 데 있어 정보 이론적 하한에 근접한 압축률을 제공합니다. 포인터 기반 Trie와 비교했을 때 메모리 사용량이 크게 줄어들어 모바일 환경에서 요구하는 제약 조건을 만족시키기에 적합했습니다.

또한 한글을 2바이트로 인코딩하고 영어는 2바이트 중 뒤 1바이트만 사용하는 방식, 중국어, 일본어와 같은 다른 언어는 플래그로 구분해 Trie 검색을 생략하는 등, 한글에 최적화된 인코딩 방식을 적용해 사전 데이터 중 한글 부분의 크기를 더욱 줄일 수 있었습니다. 외부 인터페이스는 UTF-8이지만 사전 내부 표현은 경량화를 위해 별도의 인코딩 방식을 사용한 것입니다. 인코딩 변환이 매우 간단하고 빠르기 때문에 런타임 오버헤드도 거의 발생하지 않았습니다.

결과적으로 LOUDS 기반의 사전은 약 76만 노드를 약 9.4MB로 압축할 수 있었습니다. Trie 압축 알고리즘 간의 정량적인 비교를 진행하지는 못해 아쉬움이 남지만, 사전 압축의 효과를 가늠하기 위해 동일한 데이터 일부를 다른 방식으로도 저장해 보았습니다.

예를 들어 약 20만 노드 규모의 단어, 형태소, 확률로 구성된 사전 데이터를 CSV 파일로 저장했을 때는 약 3.60MB였지만, 이를 사전 구조로 압축했을 경우에는 약 2.33MB 수준까지 줄일 수 있었습니다. 한글 인코딩 최적화와 LOUDS 기반 Trie를 통해 사전 데이터의 크기를 크게 줄일 수 있었고, 그 결과 모바일 환경에서 요구하는 제약 조건을 안정적으로 만족할 수 있었습니다.

Select 비트 연산 최적화

앞에서 설명한 LOUDS 기반 Trie에서 사전 검색은 비트 시퀀스에 대한 연산을 매우 빈번하게 수행합니다. 특히 N번째 0의 위치를 찾는 연산이 핵심인데, 이 연산을 select0 이라고 부르겠습니다. 예를 들어 사전을 검색할 때 K번째 노드의 자식 노드 인덱스를 계산하려면 select0(K) 연산을 사용해 K번째 0의 위치를 찾아야 합니다.

문제는 이 연산이 수행되는 비트 시퀀스의 길이였습니다. 사전 구축 시 트리가 매우 크기 때문에 비트 시퀀스도 매우 길어집니다. 예를 들어 약 20만 개의 노드를 저장하는 사전의 경우, LOUDS 표현을 위해 대략 40만 비트의 비트 시퀀스가 필요합니다.

LOUDS는 트리 구조를 약 (2 * 노드 수) 비트로 표현합니다.

이 긴 비트 배열에서 매번 선형 탐색으로 0의 위치를 계산하는 방식은 성능 병목으로 이어질 수밖에 없었습니다.

실제로 사전 검색 경로를 기준으로 플레임 그래프(Flame Graph)를 그려보면, 전체 사전 검색 시간의 약 90%가 select0 연산에 소비되고 있음을 확인할 수 있었습니다. LOUDS의 구조적 장점으로 인해 사전 용량은 크게 줄었지만, select0 연산의 비효율성으로 인해 전체 형태소 분석 속도가 크게 저하되는 상황이었습니다.

참고로 LOUDS는 구조적으로 1이 매우 많이 등장하는 비트 시퀀스를 만듭니다. 이 때문에 반복되는 1을 Run-length 인코딩(RLE)으로 압축해 용량을 더 줄일 수도 있습니다. 하지만 RLE 압축은 select0 연산을 더욱 복잡하게 만들기 때문에, 이번 프로젝트에서는 RLE 압축을 적용하지 않았지만, 용량 최적화가 더 필요하다면 고려해볼 만한 방법입니다.

최적화를 위해 비트 시퀀스를 64비트 단위의 청크(chunk) 로 나누어 uint64_t의 배열에 저장했습니다. 동시에 각 청크 경계(64, 128, 192, …)까지 등장한 0의 누적 개수를 별도의 배열에 미리 기록했습니다.

std::vector bit_sequence; // 64비트 단위 청크 배열
std::vector zero_prefix_counts; // 각 청크 경계까지의 0의 누적 개수

이렇게 하면 select0(k) 연산을 수행할 때, zero_prefix_counts 배열 내에서 바이너리 서치(Binary Search)를 사용해 k번째 0이 속한 청크를 빠르게 찾을 수 있습니다. 예를 들어 k번째 0이 zero_prefix_counts[i-1] < k && k <= zero_prefix_counts[i]를 만족한다면, k번째 0은 i번째 청크 내에 존재합니다. 이렇게 청크를 찾으면, 해당 청크 내에서 select0(k - zero_prefix_counts[i-1]) 연산을 수행해 정확한 비트 위치를 계산할 수 있습니다.

청크, 즉 uint64_t 단위 내에서 select0 연산은 “Counting bits set, in parallel” 기법을 활용했습니다. 비트 연산과 비트 쉬프트를 조합해 64비트를 8개의 8비트 부분으로 나누고, 각 8비트 부분에 1의 개수를 비트가 아닌 정수로 저장한 후, 몇 번째 8비트 부분에 k번째 0이 속하는지 계산하는 방식입니다. (목적은 다르지만 std::popcount에서도 사용하는 기법이기도 합니다.)

inline uint64_t CountingBitSetInParallel(uint64_t x) {
  static constexpr uint64_t kMask1 = 0x5555555555555555ULL;  // 01010101...
  static constexpr uint64_t kMask2 = 0x3333333333333333ULL;  // 00110011...
  static constexpr uint64_t kMask4 = 0x0f0f0f0f0f0f0f0fULL;  // 00001111...

  x = x - ((x >> 1) & kMask1);
  x = (x & kMask2) + ((x >> 2) & kMask2);
  return (x + (x >> 4)) & kMask4;
}

그럼 나머지 8비트 부분에서는 비트를 하나씩 밀어가며 0의 개수를 세어 k번째 0의 정확한 위치를 찾습니다.

정리하면, select0(k) 연산은

미리 계산된 0의 누적 개수를 사용해 k번째 0이 속한 청크를 빠르게 찾고
해당 청크에서 8비트 단위 묶음별 1의 개수를 비트 연산으로 계산해 묶음을 찾고
8비트 묶음 내에서 비트를 순차 탐색하는 방식으로 구현되었습니다. 이렇게 하면 전체 비트 시퀀스를 선형 탐색하는 것보다 훨씬 빠르게 select0 연산을 수행할 수 있습니다.

최적화를 적용한 결과, 평균 길이가 45.05 바이트인 짧은 문장 처리 속도는 0.023ms에서 0.019ms로 감소했습니다. select0이 매우 자주 호출되는 핫 코드(Hot Code)이기 때문에, 이 최적화만으로도 전체 형태소 분석 시간이 약 17% 정도 단축되는 효과가 있었습니다.

마무리

형태소 분석기에서 사용하는 알고리즘 자체는 이미 잘 알려진, 비교적 클래식한 접근입니다. 그럼에도 불구하고 이번 작업이 흥미로웠던 이유는, 모바일 환경이라는 제약 안에서 같은 알고리즘을 어떻게 더 작게 만들고, 어떻게 더 빠르게 만들 것인가를 고민해야 했기 때문입니다.

문제 상황과 목적은 단순했습니다. 같은 알고리즘인데 용량은 더 작게, 같은 구조인데 실행은 더 빠르게 만드는 것이 목표였습니다. 하지만 이 단순한 목표를 만족시키기 위해 언어 선택부터 자료구조 표현, 비트 단위 최적화까지 여러 선택을 반복해야 했고, 그 과정 자체가 재미있는 엔지니어링 문제였습니다.

이런 이유로 이 글이 형태소 분석 자체에 익숙하지 않은 독자에게도 비교적 부담 없이 읽힐 수 있기를 기대합니다. 알고리즘의 복잡함보다는, 제약 조건이 있는 환경에서의 설계와 구현 고민에 초점을 맞췄기 때문입니다.

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