SymSpell 도입으로 오타 교정 지연시간 80ms에서 0.1ms로 단축

Context

20만 개 이상의 단어를 포함한 Dictionary 환경에서 Levenshtein distance 기반의 Brute Force 검색 방식 적용. 전수 조사를 통한 $O(N)$ 복잡도로 인해 실시간 Search-as-you-type 인터페이스 구현 시 심각한 Latency 발생.

Technical Solution

• Triangle Inequality를 활용한 BK-Tree 구조 도입으로 불필요한 서브트리 탐색을 제외하는 Pruning 전략 수행
• Metric-space Indexing을 통한 탐색 범위 축소로 계산 복잡도 개선
• Runtime 계산 비용 제거를 위해 Edit Distance 2 이내의 모든 삭제 조합을 Pre-compute 하는 Symmetric Delete 방식 채택
• 생성된 모든 변형 단어를 Hash Map에 저장하여 런타임 시 $O(1)$ 수준의 Key-value Lookup으로 전환
• Tree Traversal 비용을 메모리 공간으로 대체하는 Space-Time Trade-off 설계 적용