Hacker News 2026.04.17 35

맞춤법 검사기는 어떻게 빠를까? Trie로 푸는 Levenshtein 거리 이야기

오타 하나 쳤는데, 어떻게 그걸 알고 제안해줄까

구글 검색창에 오타를 쳐도 "혹시 이걸 찾으셨나요?" 하고 정확한 단어를 제시해 주는 기능, 한 번쯤 고맙다고 느껴보셨을 거예요. VS Code에서 변수명을 잘못 써도 빨간 줄 그어주고, 비슷한 이름을 추천해 주는 것도 마찬가지죠. 이 기능들이 뒤에서 굴리는 개념 중에 가장 유명한 게 바로 Levenshtein distance(레벤슈타인 거리) 예요.

이게 뭐냐면, 두 문자열이 얼마나 다른지를 숫자로 표현하는 방법이에요. 한 글자씩 바꾸거나, 지우거나, 넣어서 한쪽을 다른 쪽으로 만들려면 최소 몇 번 작업해야 하는지를 세는 거죠. 예를 들어 kitten을 sitting으로 바꾸려면 k→s, e→i, 그리고 g를 마지막에 추가해서 총 3번 편집하면 되니까 거리가 3이에요. 스펠링 체커는 사용자가 입력한 단어와 사전의 단어들 중 거리가 가장 가까운 것을 골라 추천하는 원리로 동작해요.

기본 방식의 한계

전통적인 Levenshtein 계산은 동적 계획법(DP) 으로 풀어요. 두 문자열의 길이를 m, n이라고 하면 m × n 크기의 표를 채우면서 최소 편집 횟수를 찾아가는 방식이에요. 단어 하나 비교하는 건 금방이지만, 문제는 사전이에요. 영어 사전만 해도 표제어가 수십만 개인데, 사용자가 단어 하나 입력할 때마다 사전 전체를 돌면서 일일이 거리를 계산하면 버벅대기 딱 좋아요.

Steve Hanov가 2011년에 공유한 이 글이 재밌는 건, Trie(트라이) 자료구조 를 이용해서 이 문제를 놀랄 만큼 깔끔하게 풀어낸다는 점이에요. Trie가 뭐냐면, 단어들을 접두사 기준으로 트리에 묶어 저장하는 구조예요. cat, car, card가 있으면 c-a 부분은 공유하고, 거기서 t, r, r-d로 갈라지는 식이죠. 한국어의 가나다 사전을 트리로 만든다고 상상하면 돼요.

Trie + DP 조합의 매력

핵심 아이디어는 이거예요. DP 표를 채울 때 각 사전 단어마다 처음부터 새로 계산하는 대신, Trie를 따라 내려가면서 한 행(row)씩만 추가로 계산 하는 거예요. cat까지 계산한 DP 행이 있다면, car를 계산할 때 c-a까지의 행은 이미 있으니 재사용하고, r에 해당하는 행만 새로 만들면 되는 거죠.

구현도 의외로 단순해요. Trie를 재귀적으로 DFS 순회하면서 각 노드에서 현재 행을 계산하고, 그 행의 최솟값이 허용 거리(예: 2)를 넘어가면 그 서브트리 전체를 가지치기(pruning) 해서 탐색을 중단해요. "여기까지 이미 편집 거리가 3인데 우리는 2 이하를 찾고 있으니 이 아래로는 더 볼 필요 없다"라는 식이에요. 이 덕분에 사전이 아무리 커져도 실제로 방문하는 노드 수는 훨씬 적어져요. 원 글에서는 수십만 단어 사전에서 밀리초 단위로 후보를 뽑아내는 성능을 보여줘요.

업계에서 실제로 쓰이는 곳들

비슷한 아이디어는 실제 제품에 널리 박혀 있어요. Lucene/Elasticsearch의 fuzzy 쿼리 는 Levenshtein Automaton이라는 더 정교한 구조를 쓰지만 출발점은 같고, SQLite의 FTS나 PostgreSQL의 pg_trgm 확장도 비슷한 근사 검색을 지원해요. 최근엔 BK-tree, SymSpell 같이 Trie 대신 다른 인덱싱으로 더 빠른 처리를 노리는 알고리즘도 나와 있는데, Trie 방식은 구현이 쉽고 교육용으로도 최고라 입문자에겐 여전히 1순위 추천이에요.

한국 개발자에게

한국어 서비스라면 자모 분리까지 고려해야 편집 거리가 직관적으로 동작하는데(안녕과 안영의 거리를 글자 단위로 보면 1이지만, 자모로 쪼개면 받침 하나 차이라 더 세밀하게 볼 수 있어요), 이런 전처리만 잘 얹으면 검색창 자동완성, 상품명 오타 보정, 관리자 검색 도구 같은 데 바로 써먹을 수 있어요. 특히 사내 도구처럼 데이터가 몇만~몇십만 건쯤 되는 규모라면, 굳이 Elasticsearch 띄우지 않고 Trie 하나로 메모리에서 충분히 빠르게 처리할 수 있다는 점이 매력이에요.