자동완성과 와일드카드 검색은 어떻게 작동할까?

부스트키워드 팀

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

검색창에 "제주도 흑돼"까지만 입력해도 "제주도 흑돼지 맛집"이라는 검색어가 바로 아래에 추천으로 나타납니다. 또 어떤 경우에는 단어의 정확한 철자를 다 몰라도, 일부만 알고 있는 상태에서 검색이 가능하기도 합니다. 이런 기능들은 어떻게 가능한 걸까요? 이 글에서는 단어의 일부만으로 검색을 가능하게 하는 와일드카드 검색과, 검색창의 자동완성 기능이 공통적으로 활용하는 원리를 살펴봅니다.

몇 글자만 쳐도 알아채는 검색창, 신기하지 않은가요

일반 역색인만으로는 부족한 이유

앞선 글에서 살펴본 역색인은 "완전한 단어"를 기준으로 어떤 문서에 등장하는지를 정리해둔 표입니다. 그런데 역색인은 정확히 일치하는 단어를 찾는 데는 매우 효율적이지만, "단어의 일부만 아는 경우"에는 그대로 활용하기 어렵습니다. 예를 들어 "제주도"라는 단어는 역색인에서 바로 찾을 수 있지만, "제주*"처럼 뒷부분이 빠진 검색어는 역색인 표 어디에서도 정확히 일치하는 항목을 찾을 수 없습니다.

정확한 단어를 몰라도 검색이 가능해야 하는 상황들

실제로 사용자는 정확한 단어를 다 기억하지 못하는 경우가 많습니다. 파일 이름의 일부만 기억하거나, 단어의 앞부분만 입력하고 나머지는 시스템이 알아서 완성해주길 기대하는 경우가 대표적입니다. 이런 상황을 지원하려면 역색인과는 다른 방식의 색인 구조가 추가로 필요합니다.

와일드카드 검색이란 무엇인가

"구글", "림픽"처럼 일부만 아는 단어 검색하기

와일드카드 검색이란 단어의 일부를 별표() 같은 기호로 대신하여, 그 부분에 어떤 글자가 들어가도 상관없이 검색하는 방식을 말합니다. 예를 들어 "구글"이라고 검색하면 "구글", "구글맵", "구글드라이브"처럼 "구글"로 시작하는 모든 단어를 찾을 수 있습니다. "*림픽"이라고 검색하면 "올림픽", "패럴림픽"처럼 "림픽"으로 끝나는 단어를 찾을 수 있습니다.

단어의 앞부분/뒷부분/중간을 모를 때의 차이

와일드카드가 단어의 뒷부분에 붙으면(예: "구글") 비교적 처리하기 쉽지만, 단어의 앞부분에 붙거나(예: "드라이브") 중간에 위치하는 경우(예: "구*이브")는 훨씬 더 까다로운 문제가 됩니다. 일반적인 사전은 알파벳(또는 가나다) 순서로 정렬되어 있어서, 특정 접두사로 시작하는 단어를 찾는 것은 쉽지만, 특정 접미사로 끝나는 단어나 중간에 특정 글자가 들어간 단어를 찾으려면 사전을 처음부터 끝까지 뒤져야 하기 때문입니다.

퍼뮤텀 색인(Permuterm Index): 단어를 회전시켜 저장하는 아이디어

단어를 여러 방식으로 돌려가며 미리 저장해두는 발상

이 문제를 해결하기 위한 대표적인 방법이 퍼뮤텀 색인입니다. 기본 발상은 이렇습니다. 하나의 단어 끝에 특수한 기호(문장의 끝을 표시하는 기호)를 붙인 뒤, 이 문자열을 한 글자씩 돌려가며 만들 수 있는 모든 회전형을 함께 저장해두는 것입니다. 이렇게 미리 여러 형태로 저장해두면, 단어의 어느 위치에 와일드카드가 들어오더라도 그에 맞는 회전형을 찾아내는 방식으로 통일해서 처리할 수 있습니다.

간단한 단어로 직접 만들어보는 퍼뮤텀 색인 예제

"hello"라는 단어를 예로 들어보겠습니다. 단어 끝에 특수 기호(여기서는 $로 표시)를 붙이면 "hello$"가 됩니다. 이 문자열을 한 글자씩 돌려가며 만든 회전형은 다음과 같습니다.

• hello$
• ello$h
• llo$he
• lo$hel
• o$hell
• $hello

이제 "hel*"이라는 와일드카드 검색어가 들어왔다고 해봅시다. 이 검색어 뒤에 $ 기호를 붙이고 순서를 조정하면 "$hel"로 시작하는 회전형을 찾으면 된다는 것을 알 수 있고, 위 목록에서 "$hello"가 이 조건에 해당하므로 "hello"라는 단어가 검색 결과로 나오게 됩니다. 이런 방식으로 와일드카드가 단어의 어느 위치에 있더라도 결국 "특정 접두사로 시작하는 회전형을 찾는" 동일한 문제로 바꿔서 처리할 수 있습니다.

k-gram 색인: 더 실용적인 방법

단어를 짧은 글자 조각으로 쪼개어 저장하기

퍼뮤텀 색인은 개념적으로 명확하지만, 모든 단어의 모든 회전형을 저장해야 하므로 저장 공간이 많이 필요합니다. 그래서 실제로는 이보다 더 실용적인 k-gram 색인이 널리 쓰입니다. k-gram이란 단어를 2~3글자 단위의 짧은 조각으로 쪼갠 것을 말합니다. 예를 들어 "hello"를 2글자 단위(2-gram)로 쪼개면 "$h", "he", "el", "ll", "lo", "o$" 같은 조각들이 만들어집니다. k-gram 색인은 이런 짧은 글자 조각을 기준으로, 그 조각을 포함하는 단어들의 목록을 미리 정리해둔 표입니다.

예제로 이해하는 k-gram 색인 구성과 검색 과정

앞서 스펠링 교정 글에서도 소개했던 이 개념을 와일드카드 검색에 적용해보면, "구글*"이라는 검색어가 들어왔을 때 이를 "구글"로 시작하는 단어를 찾는 문제로 바꾸고, "구글"이라는 조각을 포함하는 단어들을 k-gram 색인에서 빠르게 찾아낼 수 있습니다. 이렇게 찾아낸 후보 단어들 중에서 실제로 조건에 맞는 단어만 최종적으로 걸러내면, 사전 전체를 뒤지지 않고도 빠르게 와일드카드 검색을 처리할 수 있습니다.

자동완성은 여기서 한 걸음 더 나아간 기술

자주 검색된 단어 목록을 미리 정렬해두는 방식

와일드카드 검색이 "패턴에 맞는 모든 단어를 찾는" 기술이라면, 자동완성은 여기에 한 가지 요소를 더 결합합니다. 바로 "그 후보 단어들 중 어떤 것을 먼저 보여줄 것인가"를 정하는 것입니다. 검색엔진은 실제 사용자들이 얼마나 자주 검색했는지에 대한 데이터를 미리 정리해두고, 입력된 글자로 시작하는 후보 단어들 중 검색량이 많은 순서대로 상위에 노출시킵니다.

개인화(내 검색 기록 반영)까지 더해지는 경우

더 나아가 많은 서비스는 사용자 개인의 과거 검색 기록이나 자주 방문한 페이지 같은 정보까지 함께 반영해서, 같은 글자를 입력해도 사용자마다 조금씩 다른 자동완성 결과를 보여주기도 합니다.

실제 서비스에서는 어떻게 응용될까

검색엔진의 자동완성, 쇼핑몰의 상품 검색 자동완성

포털 검색창의 자동완성뿐 아니라, 쇼핑몰에서 상품명을 검색할 때 나타나는 추천 검색어, 지도 서비스에서 장소를 검색할 때 나타나는 추천 목록 등이 모두 비슷한 원리로 작동합니다.

코드 편집기의 자동완성과의 공통점

흥미롭게도 프로그래머들이 사용하는 코드 편집기의 자동완성 기능도 비슷한 원리를 공유합니다. 함수나 변수 이름의 일부만 입력해도, 그 글자로 시작하거나 그 글자를 포함하는 후보들을 미리 정리된 목록에서 빠르게 찾아 보여주는 방식이기 때문입니다.

정리하며

와일드카드 검색과 자동완성은 모두 "정확한 완전한 단어를 몰라도 원하는 정보를 찾을 수 있어야 한다"는 필요에서 출발했습니다. 퍼뮤텀 색인과 k-gram 색인처럼 단어를 미리 다양한 형태로 쪼개거나 회전시켜 저장해두는 아이디어 덕분에, 사전 전체를 매번 뒤지지 않고도 빠르게 후보 단어를 찾아낼 수 있습니다. 여기에 실제 검색 데이터를 반영한 정렬 방식이 더해지면서, 오늘날 우리가 익숙하게 사용하는 편리한 자동완성 기능이 완성됩니다.