아주 간단한 한국어 검색어 교정기 만들기
2020년 03월 07일 작성TL;DR
코드는 여기1.
원 글은 몇년전 컴퓨터 월드2 에 올렸었다. 백업용으로 간소화 시켜서 옮겨본다.
시작하며
개인적으로 오탈자를 제대로 처리하는 것이 검색서비스에서 가장 중요한 기능중 하나라고 생각한다.
오탈자를 제대로 처리있다면 사용자 경험과 서버 퍼포먼스 모두를 향상시킬 수 있고, 오탈자 처리에 들어가는 비용은 생각보다 크지 않기 때문이다.
예를 들어 이불을 검색하려다 이줄을 검색한 경우, 일반적으로 이불은 유효한 단어이기 때문에 캐싱을 해두지만 이줄은 캐싱을 해두지 않는다.
이렇게 캐시히트하지 않은 경우 캐시서버 대신 검색서버에 연산을 요청하게 되어 트래픽을 소비하게 되고, 사용자 입장에서도 어차피 다시 이불을 검색해야하는데, 그 사이 오타에 대한 검색시간까지 겪어야 하는 불편함이 있다.
본 글에서는 QWERTY 자판만을 기준으로 검색어 교정기를 만드는 간단하지만 효과적인 방법을 알아본다.
글에서 사용된 코드는 여기1 에서 확인할 수 있으며, 사용된 데이터는 실제 서비스의 검색패턴 중 일부를 반영한 데이터로 저장소의 query_logs.csv 파일에 CSV 형태로 포함돼있다.
문자 비교하기
이불과 이줄이 비슷하다는 것은 이불과 이놈이 상당히 다르다는 것만큼이나 명확하게 알 수 있다.
검색어를 교정하기 위해 먼저 할 일은 이불과 이줄, 그리고 이불과 이놈이 얼마나 다른지 컴퓨터에게 알려주는 일이다.
다시 말해 글자가 서로 다를수록 높아지는 점수를 diff_score라고 할 때, 이불과 이줄의 diff_score는 이불과 이놈의 스코어보다 반드시 낮아야 한다.
이때 글자의 차이만 보게 되면 둘 다 한 글자씩 다르기 때문에 같은 diff_score를 갖게 된다.
따라서 글자 단위가 아니라 자모음 단위로 비교해야 한다.
즉, 이불을 ㅇㅣㅂㅜㄹ 로 변환한 뒤 이줄과 이놈을 비교하면 ㅇㅣㅈㅜㄹ 과의 diff_store 가 ㅇㅣㄴㅗㅁ 과의 그것보다 훨씬 작다는 것을 알 수 있다.
유니코드 글자에서 자모음 분리하기
유니코드 이전에는 조합형과 완성형을 따로 처리했지만, 유니코드를 이용하게 되면서 이러한 구분이 사라졌다.
위 그림은 유니코드의 현대 한글 글자 모두를 가나다순으로 정렬·배치한 것이다.
현대 한글이 사용하는 자모는 초성 19자, 중성 21자, 종성 27자로, 조합 가능한 글자 수는 19x21x28(종성 없음 포함)=11,172자다. 그림을 보면 알 수 있듯이 종성과 종성, 중성과 중성, 종성과 종성 사이의 거리는 항상 일정하다.
이를 통해 사용자의 검색어를 유니코드로 바꾸고 각 거리를 계산해주면 유니코드 한글의 시작 위치인 가를 기준으로 한 초/중/종성 간 상대 거리를 얻을 수 있다.
췟을 예로 들면, 유니코드 테이블의 첫 글자인 가를 기준으로 종성 ㅅ까지 종성 간 거리가 19, 중성인 ㅞ까지의 중성 간 거리가 15, 초성인 ㅊ까지의 초성 간 거리가 14다.
각각 위치를 얻어 적절히 치환해주면 ㅊㅞㅅ이라는 분리된 자모음을 얻을 수 있다.
chut = 'ㄱㄲㄴㄷㄸㄹㅁㅂㅃㅅㅆㅇㅈㅉㅊㅋㅌㅍㅎ#'
ga = 'ㅏㅐㅑㅒㅓㅔㅕㅖㅗㅘㅙㅚㅛㅜㅝㅞㅟㅠㅡㅢㅣ#'
ggut = ' ㄱㄲㄳㄴㄵㄶㄷㄹㄺㄻㄼㄽㄾㄿㅀㅁㅂㅄㅅㅆㅇㅈㅊㅋㅌㅍㅎ#'
BASE = 0xAC00
query = '췟'
code = ord(query) - BASE
jongsung = code % 28
jungsung = ((code-jongsung) // 28) % 21
chosung = ((code - jongsung) // 28) // 21
print(chut[chosung], ga[jungsung], ggut[jongsung])
>>>
ㅊ ㅞ ㅅ
첫가끝은 첫소리, 가운뎃소리, 끝소리 를 줄여서 말하는 것으로 자모조합에서 일반적으로 사용하는 단어이다.
또, 이 첫가끝의 마지막에 # 은 나중에 비교할 때 편의를 위해 채워둔 값이다.
실제 오타는 첫가끝 중 한개또는 두개가 없는 경우가 많기 때문이다.
유니코드 자모음간의 거리 계산
이제 자모음을 분리했으니 글자 간 차이를 계산해보자. 가장 간단한 방법은 자모음을 분리한 결과를 한 줄로 나열해두고 차이를 계산하는 것이다.
즉 이불과 이줄로 생각했을 때는 ㅇㅣㅂㅜㄹ과 ㅇㅣㅈㅜㄹ로 보고 1의 차이가 난다고 볼 수 있다.
하지만 앞에서부터 차례대로 비교하는 방법을 이용했을 때 입불과 이불과의 차이는 1이 아니라 3이다.
ㅇㅣㅂㅂㅜㄹ과 ㅇㅣㅂㅜㄹ은 3번째 ㅂ을 기준으로 3개의 차이가 있기 때문이다.
이 문제는 최장공통부분수열 문제(LCS) 인데 python 에서는 해당 문제를 쉽게 풀수 있는 difflib 라이브러리를 제공한다.
difflib 의 ratio() 함수는 전체 문자 길이에 대한 LCS의 비율을 반환하는데 이 값을 우리의 diff_score 로 사용할 수 있다.
이를 적용한 코드를 보면 이불과 이줄 간 점수(0.83)가 이놈과의 점수(0.5)보다 높고, 입불과의 점수(0.83)와는 같다는 것을 확인할 수 있다
import difflib
from functools import reduce
def segment(ch):
'''유니코드 글자를 입력받아 초,중,종성에 대한 인덱스를 반환한다'''
code = ord(ch) - BASE
jongsung = code % 28
code = code - jongsung
jungsung = (code // 28) % 21
code = code // 28
chosung = code // 21
if chosung < 0:
chosung = -1
if 19 < jongsung:
jongsung = -1
return chut[chosung], ga[jungsung], ggut[jongsung]
def diff(word1, word2):
'''두 유니코드 단어의 거리를 계산하여 차이를 반환한다'''
L1 = ''.join(reduce(lambda x1,x2: x1+x2, map(segment, word1)))
L2 = ''.join(reduce(lambda x1,x2: x1+x2, map(segment, word2)))
differ = difflib.SequenceMatcher(None, L1, L2)
return differ.ratio()
print(segment(u'ㅜ'))
>>>
('#', 'ㅛ', '#')
print(diff('이불', '이줄'), diff('이불', '입불'), diff('이불', '이놈'))
>>>
0.8333333333333334 0.8333333333333334 0.5
사용자 검색어 교정하기
마지막으로 사용자의 검색어 로그와 해당 검색어에 대한 검색결과를 갖고 검색어 교정을 해보자. 검색어 교정을 위해 어떠한 정보가 필요할까?
먼저 아주 간단한 가설을 하나 세워보자.
사용자가 `Aa`를 검색했는데 검색결과가 거의 없고, 같은 세션 내 동일한 사용자가 `AA`를 검색했더니 `AA`에 대한 검색결과가 상당수 있었다.
이 경우에 한해 `Aa`는 `AA`에 대한 오탈자일 가능성이 클 것이다.
해당 가설을 검증하기 위해 먼저 데이터를 준비해보자.
- 총 5만개의 쿼리를 대상으로 같은 세션 내에서 60초 이내에 사용자의 검색어 목록을 DB에서 가져온다.
- 직전 검색어와 이후 검색어의 diff ratio가 0.7 이상인 검색어들을 저장한다.
- 직전 검색어와 이후 검색어에 대한 각각의 검색결과 개수를 저장한다.
위의 기준으로 저장된 데이터가 query_count.csv 에 들어있다.
코드에서는 데이터 분석을 위해 pandas 라는 라이브러리를 사용하는데, 데이터 분석에 관심이 있다면 반드시 알아둬야 하는 도구중의 하나이다.
여기서 제공하는 데이터 구조인 DataFrame를 이용하면 데이터 객체를 RDBMS의 테이블처럼 편리하게 사용할 수 있다.
import pandas as pd
df = pd.read_csv('query_count.csv', index_col='user_q').drop_duplicates()
df[:3]
마지막으로 앞서 세웠던 가설대로 먼저 검색한 결과(오타키워드)가 10개 미만이면서 후에 검색한 결과(정상키워드)에 비해 개수가 현저하게 적은 검색어를 출력하면 가설에 대한 검증을 할 수 있다.
for index in df2.index:
row = df2.loc[index]
row_type = type(row)
if pd.DataFrame == row_type:
if row[(row.user_q_count < 10) |
((row.user_q_count / row.later_q_count > 0.3) & (row.user_q_count / row.later_q_count < 1.0))
].any().user_q_count:
print(index, '=>', ','.join(row.later_q.values))
elif pd.Series == row_type:
if row.user_q_count < 10 and row.later_q_count > 10:
print(index, '=>', row.later_q)
>>>
이줄 => 이불
락엔락 => 락앤락
뷔아느레 => 비아느레
펏길 => 퍼실
숀리] => 숀리
전기매트 => 전기카페트,전기매트특대
초극셋 => 초극세사
김티 => 김치
엠씨엄 => 엠씨엠
댕만 => 대만
임모복 => 임부복
구그 => 구스
이렇게 작성된 내용으로 확인해보면 지긋지긋한이줄과 이불, 락엔락과 락앤락, 펏길과 퍼실` 등의 일반적인 오타를 올바르게 수정해주고 있는 것을 확인할 수 있다.
마치며
아주 간단한 통계적 방식으로 검색어를 교정했지만 실제로는 상당히 효과적인 방법이다.
다만 처음 세운 가설에서는 애초에 준비된 상품이 몇 개 없거나 독점 상품일 경우 등 예외사례들을 올바로 처리하지 못한다. 각 사례들을 해결하기 위해서는 클릭률, 이탈율과 같은 추가적인 데이터가 필요할 수 있다.
또한, 멀티디바이스 서비스의 경우 사용자의 IME 같은 것들에 따라 오탈자의 패턴이 상당히 달라지게 되므로, 운영체제에 따라(가능하면 입력방식을 기준으로) 다른 전략을 사용하는 것이 더 효과적이다.