검색 시스템 톺아보기 — 1. 검색어 자동완성과 오타 교정 기능

Published in

LBOX Team

13 min readJul 2, 2023

최초 글은 2023년 6월 21일 발행이 되었습니다.

안녕하세요, LBox ML Engineer 이동준입니다.

구글 검색을 이용하면서 아직 검색어를 다 입력하지 않았음에도 원하는 검색어가 자동완성되어 있는 경험을 해보셨을 것입니다. 그리고 오타를 입력해도 원래 의도한 대로 교정 해주기도 하지요. 이런 검색 시스템의 내부가 어떻게 동작하는지 궁금하지 않으신가요?

이번 글은 앞으로 작성하게 될 검색 시스템에 관련된 시리즈의 첫 번째 글로서, 검색 시스템에서 필수 기능인 ‘검색어 자동완성’ 과 ‘오타 교정’ 을 다뤄보고자 합니다.

💡 TL;DR LinkedIn에서 발표된 ‘Efficient Neural Query Auto Completion’ 논문을 기반으로 검색어 자동완성 기능의 알고리즘에 대해서 설명합니다. 그리고 여러 오타 케이스 중에 검색어 입력 오류와 띄어쓰기 교정 알고리즘에 대해서 다룹니다. 마지막으로 Airflow 기반으로 구성된 데이터 파이프라인에 대해서 살펴봅니다.

검색어 자동 완성

검색어 자동완성은 검색 시스템의 기본적인 기능으로서, 1) 사용자가 직접 검색어를 입력하는 수고를 덜어주고 2) 오타를 입력하지 않도록 도와주며 3) 사용자의 의도와 연관된 검색어를 발견할 수 있게 도와줍니다. 즉 사용자가 원하는 결과를 빠르고 쉽게 찾을 수 있도록 도와주는 것이 가장 큰 목적입니다.

이러한 검색어 자동완성 시스템은 다음과 같이 구성이 됩니다.

기본적인 검색어 자동완성 프레임워크 구조 (출처: A Survey of Query Auto Completion in Information Retrieval)

구체적으로 엘박스와 같은 판례 검색 시스템의 경우 다음과 같은 추천을 해줄 수 있습니다.

입력한 검색어를 기준으로 쿼리 로그를 통한 검색어 자동완성
최근 검색어 보여주기
최근 조회한 판례 및 관련 관련 판례 추천
판사명 검색에 해당하는 경우 판사 이름 자동완성

이렇게 입력한 검색어(prefix)를 기반으로 이렇게 다양한 추천이 가능합니다. 이번 글에서는 특히 가장 기본이 되는 쿼리 로그 기반의 검색어 자동완성을 다뤄보고자 합니다.

Efficient Neural Query Auto Completion

현재 저희 엘박스의 기본 검색어 자동완성 기능은 Linkedin에서 발표된 Efficient Neural Query Auto Completion 을 참고하여 구현하였습니다. 이 논문에서는 MCG(Maximum Context Generation)라는 방식을 제안하고 있습니다. 방식은 다음과 같습니다.

MCG 동작 방식 (출처 : https://arxiv.org/pdf/2008.02879.pdf)

‘cheapest flights from seattle to’ 라는 검색어가 들어오면 검색어 로그를 통해 구성한 FST(Finite State Machine)을 통해서 뒤에 나올 단어를 생성해 줍니다. 생성할 수 있는 단어가 없을 때는 앞에서부터 하나씩 단어를 지워가면서 검색어 후보군을 생성하도록 합니다.

단계적으로 맥락을 덜 고려하게 되는 것으로서, 위 테이블에 나온 예제의 경우 초반에는 ‘flights from seattle to’ → ‘sfo’ 를 생성하다가 앞의 단어가 생략되면서(회색 글자) 이후에는 ‘to’ → ‘airport’, ‘study’ 까지 다양한 검색어를 생성하게 됩니다.

해당 알고리즘의 Pseudo-code는 다음과 같습니다.

MCG Algorithm (출처 : https://arxiv.org/pdf/2008.02879.pdf)

출처: https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_state_automaton

알고리즘을 구현하기 위해서는, 먼저 검색 로그를 기반으로 QueryFST 와 SuffixFST를 만들어야 합니다. QueryFST는 검색어들을 그대로 사용하고, SuffixFST는 검색어들을 뒤에서부터 n-gram으로 구성하게 됩니다. (FST는 Finite State Transducers의 약자로 FSM 와 같은 의미로 사용됩니다.)

이렇게 MCG는 단순한 알고리즘임에도 불구하고 뛰어난 성능을 보이며, 이전에 검색이 된 적이 없는(Unseen) 새로운 검색어를 추천할 수 있습니다.

MCG Performance (출처 : https://arxiv.org/pdf/2008.02879.pdf)

Ranking Performance (출처 : https://arxiv.org/pdf/2008.02879.pdf)

마지막으로 위 오른쪽 테이블에 따르면 MCG 알고리즘을 기반으로 검색어 후보군에 대한 Ranking(Learning to rank)을 학습한 언어 모델이 높은 성능을 보여주고 있음을 알 수 있습니다. 자세한 내용은 위 논문을 참고해 주시길 바랍니다.

자동완성의 prefix 단위

검색어 자동완성에서 한글이 가지는 독특한 특징이 하나 있습니다. 바로 교착어로서 하나의 문자를 초성, 중성, 종성으로 나눌 수 있다는 것입니다. 이 방식으로 인해서 조합형(초성, 중성, 종성을 각각 따로 표시), 완성형(글자 하나마다 코드를 부여)이라는 두 가지 방식의 인코딩 방식이 존재합니다.

현재는 완성형의 인코딩 방식을 사용하고 있기 때문에, ‘ㅅ’, ‘사’ 각각이 하나의 문자로 인식이 되고 있습니다. 그래서 ‘상습사기’ 라는 검색어 로그를 기반으로 별도의 전처리 없이 QueryFST를 만든다면, 다음과 같이 구성이 됩니다.

'상' -> '습' -> '사' -> '기'

하지만 이는 우리가 키보드로 검색어를 입력하는 방식과는 차이가 있습니다. 자음 모음 단위로 하나하나 입력을 해야 하기 때문입니다. 즉 QueryFST 역시 자음 모음 단위로 아래와 같이 구성이 되어야 합니다.

'ㅅ' -> 'ㅏ' -> 'ㅇ' -> 'ㅅ' -> 'ㅡ' -> 'ㅂ' -> 'ㅅ' -> 'ㅏ' -> 'ㄱ' -> 'ㅣ'

오타교정

많은 분들이 검색창에 실수로 오타를 입력하였을 때 검색 시스템이 자동으로 교정한 검색 결과를 보여주는 것을 경험해 보셨을 것입니다.

이런 검색어 입력 오타는 크게 세 가지 종류가 있습니다.

검색어 입력 오타 : 예) ‘음쥬운전’ → ‘음주운전’ → 해결 방식: SymSpell 으로 오타 교정
한글을 영어로 입력 : 예) ‘dmawndnswjs’ → ‘음주운전’ → 해결 방식: 알파벳과 자음모음 매칭 후, 조합
띄어쓰기 : 예) ‘공유재산변상금’ → ‘공유재산 변상금’ → 해결 방식: soyspacing 을 통한 띄어쓰기 교정

각각의 오타를 해결하는 방법 중, 검색어 입력 오타 교정법(SymSpell 알고리즘)과 띄어쓰기 교정법 두 가지에 대해서 살펴보도록 하겠습니다.

SymSpell

오타 교정 알고리즘은 edit distance를 기반으로 구현이 되어 있습니다. 예를 들어, ‘음주운전’ 이라는 단어가 있다면 edit distance를 1으로 기준으로 하는 오타들은 다음과 같습니다.

(자모기준) 음주운전 -> [음쥬운전, 음주운젼, 은주운전 등...]

이렇게 edit distance 기반으로 입력이 될 수 있는 오타를 미리 생성하여, 매핑을 해주는 방식입니다. 이 방식에는 단어가 길어질수록 생성해야 하는 오타 후보군의 수가 많기 때문에 메모리 사용량이 급격하게 증가하게 됩니다.

이러한 단점을 보완하기 위해 SymSpell 알고리즘은 모든 오타 후보군을 생성하는 것이 아니라, edit distance 기준 ‘삭제’ 만을 추가하고 오타 교정으로 들어온 입력 또한 ‘삭제’ 기준의 후보군을 만들어서 탐색하는 방식입니다. 메모리와 검색 속도 면에서 기존에 비해서 아주 빨라졌는데, 자세한 내용은 이 블로그 글을 참고하시길 바랍니다.

띄어쓰기

한국어의 맞춤법에서 아마 가장 헷갈리는 부분이 띄어쓰기가 아닐까 싶습니다. 다음의 단어들은 어떤 띄어쓰기를 써야 할까요?

이번주 / 이번 주
지난주 / 지난 주
다음주 / 다음 주

바로 정답은 … ‘이번 주, 지난주, 다음 주’ 입니다. 이렇듯 한국어 띄어쓰기는 어려운 문제입니다. 하지만 사람에게는 띄어쓰기가 잘못되어도 문맥과 함께 이해를 쉽게 할 수 있지만, 시스템에게는 혼동을 줄 수 있습니다.

띄어쓰기 교정의 필요성은 검색 알고리즘에 대한 이해가 필요합니다. 검색의 가장 기본적인 알고리즘은 TF-IDF 으로 Term을 기반으로 구성이 됩니다. 그리고 여기서 Term은 보통 한글의 형태소 단위로 구성이 됩니다. 즉 기존 문서를 형태소 단위로 잘 나누는 것이 제대로 된 검색 결과를 만드는 데 있어서는 기본이 됩니다.

형태소를 제대로 나누기 위해서는 문자들이 제대로 된 띄어쓰기와 함께 입력이 되어야 합니다. 띄어쓰기에 따라서 형태소는 다음과 같이 분리가 잘못 될 수 있기 때문입니다.

- "공유재산 변상금" -> ["공유", "재산", "변상", "금"]
- "공유재산변상금" -> ["공유", "재", "산변", "상금"]

그렇다면 이런 띄어쓰기를 어떻게 교정할 수 있을까요?

띄어쓰기의 경우, lovit 님의 soyspacing 을 통해서 교정을 해주고 있습니다. 이 알고리즘을 선택한 이유는 규칙기반의 휴리스틱 알고리즘에 기반하기 때문에 속도가 빠르고, 더 많은 판례에서 보이는 띄어쓰기 형식으로 글이 교정되기 때문 입니다.

검색 성능 Zero Result Rate

이렇게 오타 및 띄어쓰기를 교정하면 검색 성능지표 중 ZRR(Zero Result Rate)에 직접적인 영향을 줄 수 있게 됩니다. 검색어에 오타가 포함되어 있거나, 잘못된 띄어쓰기를 사용할 경우 아무런 검색 결과를 얻지 못하는 경우가 많기 때문입니다.

다양한 상황에 의존하는 ZRR 지표 특성상 값이 요동치는 경향이 있지만, 오타 & 띄어쓰기 교정 이후 ZRR의 비율이 줄어드는 것을 볼 수 있습니다.

검색어 로그 파이프라인

위에서 소개했던 검색어 자동완성과 오타 교정 모두 검색어 로그를 기반으로 하고 있으므로, 주기적으로 업데이트해주는 데이터 파이프라인이 필요하게 됩니다.

이 데이터 파이프라인을 통하여 기존에 입력된 검색어 로그를 기반으로 기존의 자동완성과 오타 교정 서비스를 업데이트하면 데이터가 쌓일수록 점점 더 정확한 검색어를 추천할 수 있게 됩니다.

데이터 파이프라인으로는 Apache Airflow 를 사용하고 있습니다. Airflow는 Python 코드를 기반으로 워크플로우를 손쉽게 작성할 수 있고, 최근에 발표된 Airflow 2 버전에서는 TaskFlow API를 통해서 더 직관적으로 코드를 작성할 수 있습니다.

위 Workflow를 풀어서 설명한다면 다음과 같습니다.

검색어 Raw 데이터를 가지고 온 다음, 전처리를 진행하고 이 데이터로 각각 QueryFST, SuffixFST, 그리고 오타 교정용 단어 사전을 만들어 S3에 업로드를 하는 것입니다. 이 과정을 통해서 서비스의 사용 로그가 주기적으로 서비스에 반영이 되는 것이죠.

끝으로

지금까지 검색 시스템의 기본이 되는 검색어 자동완성과 오타 교정을 살펴보았습니다. 검색 시스템은 기본적으로 로그를 통해서 더 견고한 시스템을 만들 수 있으므로, 데이터 파이프라인이 굉장히 중요합니다. 위와 같이 데이터가 흐를 수 있도록 길을 만들어주면 시간이 지날수록 더 견고한 시스템이 만들어질 수 있습니다.

축적된 데이터 로그를 더 잘 활용하기 위해서는 고등의 자연어 처리, 이해 기술이 필수적입니다. 다음 글에서는 딥러닝에 기반한 자연어 처리 기술로 검색 시스템에 사용되는 다양한 기능(연관 검색어, 검색 랭킹 등)의 성능을 올리는 방향에 대해서 다뤄보도록 하겠습니다.

많은 피드백을 주신 황원석, 성건우, 이진님께 감사를 전합니다.