오타를 자동으로 고쳐주는 원리: 스펠링 교정 알고리즘 쉽게 이해하기

부스트키워드 팀

검색 데이터로 키워드의 검색량, 트렌드, 검색 의도를 파악하고 마케팅 의사결정을 돕는 도구 부스트키워드를 만듭니다.

검색창에 "제쥬도 맛집"이라고 오타를 쳐도 검색엔진은 어김없이 "제주도 맛집"에 대한 결과를 보여주고, 하단에는 "혹시 이 검색어를 찾으셨나요?"라는 문구가 나타납니다. 사람이 봐도 눈치채기 어려운 사소한 오타를, 컴퓨터는 어떻게 이렇게 정확하게 알아채는 걸까요? 이 글에서는 검색엔진과 각종 서비스에 쓰이는 스펠링 자동 교정 기술의 원리를 예제와 함께 살펴봅니다.

"제쥬도 맛집"이라고 쳐도 결과가 나오는 이유

오타는 생각보다 자주 발생한다

사람이 키보드로 글자를 입력하다 보면 오타는 필연적으로 발생합니다. 자음과 모음의 위치를 착각하거나, 손가락이 옆 키를 잘못 누르거나, 발음 나는 대로 잘못 입력하는 경우까지 그 유형도 다양합니다. 특히 스마트폰의 작은 화면에서는 오타 발생률이 더욱 높아집니다. 만약 검색엔진이 정확히 일치하는 단어만 찾아준다면, 오타 하나 때문에 원하는 정보를 전혀 찾지 못하는 상황이 매우 자주 벌어질 것입니다.

검색엔진이 오타를 처리하지 않으면 벌어지는 일

실제로 오타를 전혀 교정해주지 않는 검색 시스템을 상상해보면, 사용자는 검색 결과가 하나도 나오지 않는 상황을 자주 겪게 되고, 결국 그 서비스에 대한 신뢰를 잃게 됩니다. 그래서 검색엔진뿐 아니라 워드프로세서, 스마트폰 키보드, 챗봇 등 텍스트를 다루는 대부분의 서비스는 오타를 자동으로 감지하고 교정하는 기능을 필수적으로 갖추고 있습니다.

컴퓨터는 '비슷한 단어'를 어떻게 판단할까: 편집 거리(Edit Distance)

편집 거리란 무엇인가

컴퓨터가 두 단어가 얼마나 비슷한지를 판단하는 대표적인 방법이 편집 거리(Edit Distance)입니다. 편집 거리는 한 단어를 다른 단어로 바꾸기 위해 필요한 최소한의 편집 횟수를 의미합니다. 여기서 편집이란 다음 세 가지 연산을 말합니다.

• 삽입: 글자를 하나 추가하는 것
• 삭제: 글자를 하나 지우는 것
• 치환: 글자를 다른 글자로 바꾸는 것

이 세 가지 연산을 몇 번 거쳐야 한 단어가 다른 단어로 바뀌는지를 세어, 그 횟수가 적을수록 두 단어가 서로 비슷하다고 판단합니다.

예제 단어로 편집 거리 직접 계산해보기

영문 예시로 "cat"과 "cot"을 비교해보겠습니다. "cat"의 가운데 글자 'a'를 'o'로 치환하기만 하면 "cot"이 됩니다. 즉 편집 연산이 단 1번만 필요하므로, 두 단어의 편집 거리는 1입니다.

이번에는 "제쥬도"와 "제주도"를 비교해보겠습니다. 두 번째 글자 '쥬'를 '주'로 치환하기만 하면 정답 단어가 됩니다. 역시 편집 거리는 1로, 매우 가까운 단어입니다.

반면 "제쥬도"와 전혀 관계없는 단어인 "부산"을 비교하면, 거의 모든 글자를 지우고 새로 넣어야 하므로 편집 거리가 매우 커집니다.

편집 거리가 짧을수록 정답에 가깝다

이 원리를 이용하면, 사용자가 입력한 오타와 사전에 등록된 정상적인 단어들 사이의 편집 거리를 각각 계산해서, 편집 거리가 가장 짧은 단어를 "사용자가 원래 입력하려던 단어"의 후보로 제시할 수 있습니다.

사전만으로는 부족하다: 후보 단어를 빠르게 찾는 방법

모든 사전 단어와 일일이 비교하면 느린 이유

그런데 여기서 실용적인 문제가 하나 생깁니다. 국어사전이나 검색엔진이 알고 있는 단어의 수는 수십만, 많게는 수백만 개에 이릅니다. 사용자가 오타를 입력할 때마다 이 모든 단어와 일일이 편집 거리를 계산한다면, 시간이 너무 오래 걸려 실시간 서비스에 쓰기 어렵습니다.

후보를 빠르게 좁히는 아이디어

그래서 실제 시스템에서는 편집 거리를 계산하기 전에, 애초에 비교 대상이 될 만한 단어들을 먼저 빠르게 추려내는 과정을 거칩니다. 예를 들어 입력된 단어를 짧은 글자 조각(2~3글자 단위)으로 쪼갠 뒤, 이 조각을 공유하는 사전 단어들만 먼저 후보로 뽑아내는 방식이 널리 쓰입니다. "제쥬도"라는 오타라면 "제쥬", "쥬도" 같은 조각을 사전에서 검색해, 이 조각을 포함하는 단어들만 우선 후보로 삼는 식입니다. 이렇게 하면 사전 전체와 비교하는 대신, 실제로 비슷할 가능성이 있는 소수의 후보만 골라 편집 거리를 계산하면 되므로 속도가 크게 빨라집니다.

여러 후보 중 진짜 정답을 고르는 방법

편집 거리만으로 부족한 경우

편집 거리가 같은 후보 단어가 여러 개 존재하는 경우도 흔합니다. 예를 들어 오타 하나로부터 편집 거리 1인 후보가 두세 개 나올 수도 있습니다. 이럴 때는 편집 거리만으로 정답을 하나로 좁히기 어렵습니다.

어떤 단어가 더 자주 쓰이는지도 함께 고려하기

이런 경우 실제 시스템은 각 후보 단어가 평소에 얼마나 자주 사용되는 단어인지를 함께 고려합니다. 아주 희귀한 단어보다는 사람들이 실제로 많이 검색하거나 사용하는 단어일 가능성이 더 높기 때문입니다. 즉 "얼마나 비슷한가(편집 거리)"와 "얼마나 흔하게 쓰이는 단어인가(사용 빈도)"를 함께 반영해서 최종적으로 하나의 후보를 제시하는 방식이 널리 쓰입니다.

문맥을 함께 살펴보는 교정

더 정교한 시스템에서는 오타가 있는 단어 하나만 보는 것이 아니라, 그 앞뒤에 함께 입력된 단어까지 살펴봅니다. 예를 들어 "제쥬도 흑돼지"라는 문장이 입력되었다면, "흑돼지"라는 단어와 자주 함께 등장하는 지명이 "제주도"라는 사실까지 반영해서 교정 정확도를 더욱 높일 수 있습니다. 이렇게 주변 단어와의 관계까지 고려하는 방식을 문맥 기반 교정이라고 부릅니다.

실제 서비스에서는 어떻게 쓰일까

검색엔진의 "혹시 이 검색어를 찾으셨나요?"

구글이나 네이버 같은 검색엔진에서 오타를 입력했을 때 나타나는 추천 문구는 지금까지 설명한 편집 거리 계산과 확률적 판단, 문맥 분석을 종합한 결과입니다. 검색량이 워낙 방대하기 때문에, 실제 사용자들이 어떤 오타를 입력한 뒤 곧바로 다른 단어로 다시 검색했는지에 대한 데이터까지 함께 활용해 교정 정확도를 높이기도 합니다.

스마트폰 자동완성·자동수정, 문서 작성 도구의 맞춤법 검사기

스마트폰 키보드의 자동 수정 기능이나 워드프로세서의 맞춤법 검사기 역시 같은 원리를 기반으로 동작합니다. 다만 이런 도구들은 검색엔진만큼 방대한 사용자 검색 데이터를 활용하기보다는, 미리 구축된 사전과 언어 모델을 기반으로 교정을 제공하는 경우가 많습니다.

정리하며

스펠링 교정 기술은 "두 단어가 얼마나 비슷한가"를 편집 거리라는 수치로 계산하고, 여기에 단어의 실제 사용 빈도와 문맥 정보를 더해 가장 그럴듯한 정답을 추천하는 방식으로 작동합니다. 사소해 보이는 이 기능 뒤에는 방대한 후보 단어를 빠르게 좁히는 자료구조와, 확률적 판단을 결합하는 정교한 설계가 숨어 있습니다. 다음에 오타를 쳤는데도 검색엔진이 정확히 알아채는 순간을 만나면, 그 뒤에서 어떤 계산이 이루어지고 있는지 한번 떠올려보셔도 좋겠습니다.