3 GB에서 10 MB로: 유한 상태 트랜스듀서(Finite State Transducers)를 이용한 접두사 검색 최적화

타이핑 중 검색(search-as-you-type) 사전 구축 시 주요 기술적 과제는 효율적인 접두사 검색입니다. 대부분의 개발자에게 가장 먼저 떠오르는 해결책은 공통 접두사를 공유하여 빠른 조회를 가능하게 하는 트라이(trie, 접두사 트리)입니다. 하지만 데이터셋이 커질수록—특히 교착어의 복잡한 형태론을 다룰 때는—최적화된 트라이조차도 감당하기 힘들 정도로 커질 수 있습니다.

최근 핀란드어-영어 사전인 Taskusanakirja (tsk) 프로젝트에서 저자는 정확히 이러한 확장성의 벽에 부딪혔습니다. 관리 가능한 수준의 Go 구현체로 시작했던 프로젝트는 수백만 개의 굴절된 단어 형태를 처리하기 위해 결국 3 GB 크기의 SQLite 데이터베이스가 필요하게 되었습니다. 해결책은 무엇이었을까요? Rust로의 마이그레이션과 유한 상태 트랜스듀서(Finite State Transducer, FST)의 구현이었습니다.

도전 과제: 교착어의 복잡성

핀란드어는 매우 강력한 교착어입니다. 즉, 기본 어근에 여러 개의 접미사를 붙여 단어를 만듭니다. 하나의 기본 단어는 100개 이상의 가능한 어미를 가질 수 있습니다. 이러한 복잡성은 접미사가 추가됨에 따라 어근 자체가 변하거나 변형되는 "consonant gradation" 및 "vowel harmony"로 인해 더욱 심화됩니다.

언어를 배우는 학생에게 특정 굴절 형태를 검색하여 그 어근을 찾는 능력은 필수적입니다. 하지만 이는 엄청난 데이터 폭발을 야기합니다:

트라이의 확장성 한계: 트라이는 약 50 MB의 RAM에서 400,000개의 항목을 효율적으로 저장할 수 있지만, 기가바이트 단위의 메모리를 소비하지 않고는 4,000만~6,000만 개의 항목으로 확장할 수 없습니다.
"Bad Easy" 해결책: 프로젝트를 계속 진행하기 위해 저자는 처음에 Full Text Search (FTS) 기능이 있는 SQLite 데이터베이스를 구현했습니다. 기능적으로는 성능이 좋았지만, 최종 사용자가 3 GB를 다운로드해야 한다는 문제가 있었습니다. 이는 가벼운 "주머니 속 사전"이라는 목표와는 거리가 멀었습니다.

해결책: 유한 상태 트랜스듀서 (FST)

메모리 위기를 해결하기 위해 저자는 Andrew Gallant (BurntSushi)의 작업에서 영감을 얻은 Rust의 fst crate를 사용했습니다.

트라이가 접두사만 공유한다면, 유한 상태 트랜스듀서(특히 최소 비순환 결정론적 유한 상태 오토마타)는 접두사와 접미사를 모두 공유합니다.

왜 FST가 핀란드어에 효과적인가

핀란드어와 같은 언어에서는 수천 개의 서로 다른 단어가 종종 동일한 몇 가지 인기 있는 굴절 패턴(예: -ssa-mme-kin과 같은 어미)을 공유합니다. 표준 트라이에서는 해당 접미사의 모든 인스턴스가 별도의 경로로 저장됩니다. 반면 FST에서는 구조적으로 동일한 모든 서브트리는 병합됩니다.

이러한 "접미사 공유"는 메모리 효율성을 극대화합니다. FST를 사용하여 굴절과 격변화를 어근의 원래 정의로 매핑함으로써, 저자는 데이터 크기를 3 GB (SQLite)에서 단 10 MB로 줄였습니다. 이는 300배 감소한 수치입니다.

엔지니어링 교훈: "Naive"한 시작의 가치

이 최적화 여정에서 얻은 가장 핵심적인 교훈 중 하나는 "문제를 두 번 푸는" 철학입니다. 저자는 처음부터 완벽한 아키텍처를 연구하며 몇 주를 보내는 것보다, "bad easy"한 해결책(예: SQLite DB)으로 시작하는 것이 종종 더 낫다고 주장합니다.

"SQLite 데이터베이스는 작동했습니다! 어떻게 작동하는지 이해했습니다... 문제를 두 번 푸는 것은 괜찮다고 생각합니다."

이 접근 방식은 다음과 같은 여러 장점을 제공합니다:

즉각적인 검증: 기능이 가능하다는 것과 유용하다는 것을 증명할 수 있습니다.
참조 구현체: 단순한(naive) 버전은 고도로 최적화된 버전을 검증하기 위한 기준(gold standard) 역할을 합니다.
위험 감소: "분석 마비(analysis paralysis)"를 피하고 프로젝트가 실제로 출시될 수 있도록 보장합니다.

더 넓은 응용 분야

이 문맥에서의 FST의 성공은 핀란드어에만 국한되지 않습니다. 커뮤니티 논의에서 언급되었듯이, 터키어나 일본어와 같이 단어 형성이 어근-접미사 층위 구조를 따르는 다른 교착어에도 유사한 기술이 매우 유용하게 적용될 수 있습니다.

또한, 설명된 데이터 구조는 수십 년 동안 정확히 이와 같은 유형의 사전 압축 문제를 해결하기 위해 다양한 형태로 재발견된 Directed Acyclic Word Graph (DAWG)와 밀접하게 관련되어 있습니다.

전환 과정 요약

지표	초기 Go/Trie	중간 단계 SQLite	최종 Rust/FST
저장 공간/RAM	~60 MB (제한된 세트)	3 GB	10 MB
검색 유형	접두사	전체 텍스트 검색	접두사/퍼지/접미사
이식성	높음	중간 (외부 DB)	매우 높음 (정적 바이너리)