검색어 제안, 맞춤법 검사(단어교정)

각종 검색엔진이나 입력 키보드들은 입력하는 내용을 보고 사용자의 의도를 예측해서 제안해주곤 한다. 흔히 말하는 자동완성, 검색어 제안 기능이다.

Image for post
Image for post
Google에서 ‘김ㅊ’라고 검색했을 때 검색제안들
Image for post
Image for post
네이버 검색화면의 검색 제안과, 삼성 안드로이드 키보드 상단에 뜨는 입력 제안

이러한 기능들은 입력중인 내용이 문법적으로 올바르거나 다른 사람들이 많이 입력한 내용일 경우 제안할 수 있다. Trie등의 자료구조를 사용하면 빠르고 효과적으로 구현할 수 있다.

그렇지 않을 경우, 즉 알 수 없는 내용을 사용자가 입력중이라면, 문법적으로 틀렸거나 프로그램에 등록되지 은 새로운 내용을 입력하는 것이다. 이 경우 입력 중인 내용에 대해 맞춤법 검사를 하고, 새로운 문장을 제안해야한다. 입력한 내용이 바른지 더 빠르게 확인하고자 한다면 블룸 필터와 같은 자료구조를 사용할 수 있다. 기존의 Trie등으로 구축된 사전에서 입력중인 내용을 비교하는 것보다 더 적은 메모리를 사용하고, 더 빠르게 틀렸다는 걸 확인할 수 있다.

Image for post
Image for post
구글에 ‘mispell’을 입력한 결과 ‘misspell’로 바꾸어서 검색 단어를 제안해준다.

현재까지 찾아본 바로는 입력 제안이 크게 2가지 부류로 나뉘는 것 같다.

사전 기반

사전 기반은 문법적으로 올바른 단어, 혹은 많이 쓰이는 단어 등을 사전으로 만들어서, 입력한 내용과 유사한 단어를 사전에서 찾는 것이다. 유사한 단어를 찾는 방법에 따라 성능이 극과 극으로 갈린다.

편집 거리

우선 두 문자열이 얼마나 유사한지를 판단할 수 있는 기준이 있어야 한다. 이 때 사용되는게 편집 거리(Edit Distance)이다. 이 편집 거리에 대표적으로 사용되는 것이 Levenstein Distance이다. 이는 문자열 A를 B로 바꾸려면 몇 번의 추가(Insert), 삭제(Delete), 대체(Replace)을 거쳐야 하는지를 알려준다.

예를 들어 ‘Laptop’ 을 ‘Desktop’으로 바꾼다고 해보자. 앞의 세글자 ‘Lap’을 ‘Des’로 바꿔야 하고, ‘Des’와 ‘top’ 사이에 ‘k’를 추가해야 하므로 3번의 변경과 1번의 삽입이 발생하므로 편집 거리는 4이다.

하지만 실제로 편집거리를 사용할 땐 삽입, 삭제, 대체 외에 교환(Transposition)이 추가된 Damerau-Levenstein Distance를 사용한다. 예를 들어 ‘The’와 ‘Teh’의 Levenstein 거리는 2번의 대체로 인해 2이지만, Damerau-Levenstein 거리에선 1이다(h와 e의 교환).

단순한 방법(Naive Approach)

단순하게 입력된 단어와 사전에 있는 모든 단어의 편집 거리를 비교한 후 편집 거리가 작은 단어를 찾는다면 단어교정을 할 수 있을 것이다. 하지만 기본적으로 수 십만에서 수 백만개의 단어와 편집 거리를 계산하려면 많은 시간이 소모될 것이다.

Peter Norvig의 방법

Peter Norvig의 Brute Forcing적인 방법은 가장 단순하고, 이해하기 쉬우며 잘 알려진 방식이다. 그의 웹사이트에서 30줄도 안되는 파이썬 코드로 구현했다.

이 방식을 요약하면 입력한 단어에서 편집 거리가 2 이내인 모든 단어를 만든다. 이후 사전에서 이 단어를 찾아본 후, 가장 자주 사용되는 단어를 선택한다. 예를 들어 ‘Ther’을 입력했을 때 편집 거리 2이내인 단어로는 ‘The’와 ‘There”이 검색될 수 있을 것이다. 이제 이 중에서 더 자주 사용되는 단어인 ‘The’를 선택한다.

어떤 단어가 더 자주 사용되는지 판별하기 위한 방법은 아주 간단한데, 위 링크의 예제에선 실제 사전에서 등장하는 단어들을 카운팅해서 각 단어마다 몇 번 등장했는지 기록한다.

간단한 만큼 이 방식은 몇가지 문제점이 있다.

  1. 후보단어들이 너무 많아질 수 있다.
    입력한 단어의 길이를 n이라고 했을 때, 편집 거리가 1인 단어를 생성하려면 알파벳 기준으로 54n+25개의 후보 단어가 생성된다. 편집 거리가 2이면 다시 여기에 54n+25를 한다. 위 예제에서 ‘somthing’의 편집거리가 1후보는 442개, 편집거리가 2인 후보는 90902개가 나왔다. 중국어는 글자가 몇 만개 단위로 사용되고, 다른 기초문자가 많은 언어들도 이보다 더 많은 후보단어들이 생성될 수 있다.
  2. 시간이 오래 걸린다
    1의 문제로 인해 발생하는 문제다. 많은 메모리를 사용함은 물론이고 이 많은 후보군에 대해 모두 사전에서 찾는 데 시간이 많이 소모된다.

Peter Norvig의 글에 따르면 대부분의 오타는 편집 거리 2 이내에서 발생한다고 한다. 하지만 위 방식으론 편집 거리 3 이상인 후보군까지 포함할 경우 더 많은 리소스가 사용될 것이다.

Symmetric Delete Spell Correction(SymSpell) 방법

아이디어를 고안한 사람이 쓴 위 링크의 글에 자세하게 설명돼있다. 내가 이전에 쓴 내용들도 이 글에 간단히 설명이 되어있다. 간단히 설명하면 Peter Norvig의 방식에서 일정 편집 거리 이내의 Delete만을 이용한 후보단어군을 만든다. 또한 사전의 모든 단어에 대해서도 Delete후보군을 만든다.

예를 들어 단어 ‘The’에서 후보로 ‘T’, ‘h’, ‘e’, ‘Th’, ‘Te’, ‘he’, 그리고 원래 단어인 ‘The’까지 7개만을 만들어낸다. Peter Norvig의 방법에선 편집 거리 1인 후보만 최대 150개 가량이 생성되었을 것이다. 편집 거리가 2였으면 천~만단위로 나왔을 것이다.

이후 이 Delete 후보군들을 이용해서만 사전에서 검색을 한다. 이 방식은 더 적은 후보군을 만들어내지만, 사전의 모든 단어도 일정 편집 거리 이내의 후보들을 만들어야해서 사전의 크기가 훨씬 커진다. 위 글에서 평균 5글자 단어 10만개가 있는 사전에서 편집 거리 2 이내의 후보들을 포함한 사전을 만들면 사전이 갖게 되는 단어의 수가 150만개나 된다고 한다.

사전의 크기가 늘어난 만큼 검색 속도도 늘어날 것 같지만, 이 방식은 검색에 해쉬테이블을 사용한다면 O(1)으로 검색을 할 수 있다고 한다. 때문에 글 제목처럼 천배 빠르게 단어교정을 할 수 있다고… 하지만 분명 메모리 사용은 더 많아질 것이다. 아래는 성능 비교

딥러닝 기반

이전의 전통적인 방식들과 다르게 딥러닝이 연구되면서 RNN을 이용한 단어교정 역시 등장하고있다. 이부분은 여러 글과 예제를 아직 보고있는데, Recurrent Neural Network 를 이용해서 Sequence-to-Sequence로 입력된 문장에서 맞춤법 오류를 찾아내서 수정하는 듯 하다. 번역에 사용되는 방식과 비슷한 것 같다.

단어 Sequence를 입력받는 게 아닌, 문자 Sequence를 입력받게 해서 숫자나, ?!., 같은 문장부호, 또 모든 언어들에 적용 가능한 방식이라고 한다. 이 방법은 계속 예제를 찾아보고 공부해야 할 것 같다.

추가로 고민중인 내용

word2vec

word2vec을 이용하면 유사 단어를 가져올 수 있고, Fasttext를 이용하면 사전에 등록되지 않은 단어도 유사 단어를 가져올 수 있다. 다만 이 방식이 단어 교정에 적합할 지는 더 생각해봐야 할 것 같다. 입력한 단어와 유사한 단어를 알아내는 것과, 입력한 단어에서 원래 입력하려고 했던 것 같은 단어를 알아내는 건 조금 다른 영역인 것 같다.

교정할 단어 고르기

단어 교정을 위해선 단어 교정 후보군을 빠르게 찾아내는 것 만큼 중요한 것이 하나 있다. 바로 찾아낸 후보군 중에서 어떤 단어가 사용자가 입력하려던 단어일 지 알아내는 것인데 딥러닝이 아닌 방식들에선 단순히 더 많이 사용되는 단어를 가져온다. 하지만 사용자의 입력 기록에서 힌트를 얻거나, 이전에 입력한 단어를 활용해서 더 유용한 단어를 제안하거나 알맞게 교정해줄 수 있을 것이다.

여기에는 n-gram model이라는 걸 사용하면 된다는데,,, 더 알아봐야 할 것 같다. 또 Google에서 수십 조개의 문서를 문석해서 n-gram모델을 만든 후 공개한 데이터가 있다. 기회가 되면 이런 것도 활용하면 좋을듯?

단어 검열

단어 사전을 만들 때 비속어나 논란, 불쾌감을 일으킬만한 단어는 삭제해야한다. 네이버에서 성인검색어를 판단하는 API를 제공하고있다. 이런 것들을 활용하면 도움이 될 것 같다.

참고자료

Written by

2020.12.8 ~ 2022.6.9 군복무중 Serving in the South Korean Military Service

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store