Bigram을 이용한 오타 검색어 정정, 검색어 제안 기능 (PHP, MySQL)

요즘 검색엔진은 친절해서 이용자들이 실수로 검색어를 잘못입력하거나 오타를 내도 알아서 수정해서 검색을 해줍니다. 세상 참 좋아졌지요!

라틴어 사전 이용자들의 이용 형태를 살펴보면서 어학 사전에서도 역시 검색어를 잘못 입력하는 실수 등이 자주 발생한다는 것을 알 수 있었습니다. 외국어 학습자의 경우 모국어 사용자에 비해 오타나 잘못된 단어를 입력할 가능성이 훨씬 높고, 잘못된 입력이 발생해도 어디가 틀려서 원하는 검색 결과를 얻지 못하는지 알기도 어렵습니다. 그래서 살아있는 라틴어 사전에서도 네이버나 구글 등의 검색엔진에서 제공해주는 검색어 정정 및 제안 기능을 비슷하게나마 제공해줘야겠다는 생각이 들었습니다.

문제는 어떻게 이 서비스를 제공할 것인가인데... 다행히도 영어전산언어학 수업이랑 정보검색론 수업에서 비슷한 내용을 아주 짧게 다루었던게 기억났습니다. 바로 N-gram 이죠. (N의 값에 따라 1일경우 Unigram, 2일경우 Bigram 등으로 부릅니다.) N-gram이 어떤 개념이냐하면 문장을 이루는 여러 단어들을 연속한 N개씩 묶어서 이 단위로 여러가지 처리(주로 빈도분석과 통계처리 등이 되겠죠?)를 수행하는 기법을 말합니다.

N이 1이면 그냥 한 단어씩 한 단어씩 처리하는것이므로 N-gram으로써의 의미는 딱히 없고, 주로 N이 2 이상인 Bigram부터 사용됩니다.

오타는 단어 단위가 아니라 문자 단위로 발생하는 것으므로 우리의 라틴어 사전에서 처리할 Bigram은 단어 단위가 아니라 문자 단위로 이루어질것입니다. 즉 puella 라는 단어가 있다고 하면, 이 단어를 문자 단위로 쪼개서

p, u, e, l, l, a

로 처리할것입니다. 만약 사용자가 puella를 입력하려다가 실수로 puela를 입력했다고 합시다. 입력된 문자열은

p, u, e, l, a

가 되겠죠. Unigram에서는 {p, u, e, l, l, a}와 {p, u, e, l, a}를 비교해서 두 단어가 얼마나 유사한지를 계산하고, 그 결과에 따라 제일 유사한 단어를 추천하는 단어로 보여주는거죠.

이를 간단하게 수식으로 써보겠습니다. 원래 단어를 C, 오타가 난 단어를 M이라고 할게요. 각각을 N-gram 성분들의 집합으로 표현하겠습니다.

두 단어가 얼마나 유사한지는 다음과 같은 식으로 계산할 수 있습니다.

이 공식대로라면 puella와 puela는 철자 하나가 빠졌지만, 집합에서 원소의 수를 셀때 중복은 계산안하므로 S(puela) = 1이 됩니다.

어떻게 보면 Unigram으로도 충분히 오타입력으로부터 회복할수 있는것처럼 보이지만, 문제는 Anagram입니다. Anagram은 구성성분은 같지만 문자의 순서만 다른 단어들을 일컫는데,

Unigram에서는 ager, gare, erga와 같은 단어들이 모두 같은 단어로 처리가 됩니다. 따라서 유저의 입력을 너무 과하게 바로잡아서, 아예 다른 단어를 추천해버릴수 있다는 문제점이 있지요.

검색어 정정은 다음과 같은 과정을 통해서 이루어질수 있습니다. 먼저 미리 색인어의 목록 C_i를 준비해놓고선 사용자의 입력을 색인어 목록 C_i와 비교해서 유사도를 계산합니다.

그리고 모든 단어 i에 대해 유사도값 S(M)이 가장 큰 i를 찾아냅니다.

이렇게 해서 가장 유사한 단어 C_i를 골라내어서 정정 검색어로 제시해주는 것이죠.

Bigram에서는 단어를 문자 2개 단위로 쪼갭니다. puella의 경우

^p, pu, ue, ul, ll, la, a$

로 표현이 됩니다. 여기서 ^와 $는 단어의 시작과 끝을 표시하는 기호입니다. 별뜻은 없어요.

사용자의 잘못된 입력인 puela의 경우는

^p, pu, ue, ul, la, a$

가 되겠죠.

Bigram상에서 두 단어의 유사도 S(puela)를 계산해보면 6/7 = 0.85...이 나옵니다. 두 단어씩 묶어서 처리했고 단어의 시작부분, 끝부분의 문자도 별도로 처리가 되기때문에 엉뚱한 단어와 매칭이 될 가능성이 낮아지죠.

Trigram(N=3)을 이용한다면 문자의 순서를 더 많이 반영하는 유사도 계산이 가능할겁니다. 하지만 3글자가 연속으로 같은 쌍은 그 수가 훨씬 줄어들기 때문에 유사도가 너무 낮게 나와 실용적으로 쓰기가 어렵습니다. 그래서 N=2인 경우인 Bigram을 주로사용하는거지요.

주로 발생하는 오타의 형태와 Bigram 상에서 오타와 원래 단어의 유사도가 어떻게 나오는지 고찰해봅시다.

1) 철자 하나를 빠뜨림

원래의 단어 문자열이 다음과 같다고 합시다. 총 n글자의 단어입니다.

누락된 문자가 a_i라고 했을때 오타 문자열은 다음과 같을 것입니다.

이 경우 m의 Bigram 집합은 다음과 같아집니다.

일반적인 상황에서 가 C의 원소일 확률은 적으므로

두 문자열의 유사도는 

즉 철자 하나가 빠질때마다 유사도는 2/(n+1)씩 감소합니다.

2) 철자 하나를 삽입함

이 경우는 C와 M을 서로 맞바꾸면 1)의 경우와 같아집니다. 따라서 철자 하나를 삽입할때도 유사도는 2/(n+1)씩 감소합니다.

3) 연속으로 중복되는 철자 하나를 빼먹음

이 경우는 1)에서  인 상황이라고 할 수 있습니다.

그러면 이므로, 유사도는

즉 중복된 철자중 하나를 빼먹을경우는 유사도가 1/(n+1) 씩 감소합니다.

세 가지 경우 모두 원 문자열의 길이 n이 적당히 크면 유사도는 1에 가까울 것이라는 것을 예상할 수 있죠.

이제 본격적으로 PHP와 MySQL을 이용해 사전에 검색어 정정 및 제안 기능을 추가해보도록 합시다.

사실 처음에 이 기능을 추가해야겠다고 마음먹고선도 한참동안은 속도 문제로 구현을 망설이고 있었습니다. 서버가 PHP로 돌아가고 있기에 PHP를 이용해서 일일히 2만여 단어를 Bigram으로 분리하고 그 값을 비교하는것은 꽤나 오래걸릴것이라고 생각했기 때문이지요. 그런데 MySQL을 이용해서 쿼리한번에 빠르게 계산하는 방법이 번뜩 떠올라서 바로 구현해보게 되었습니다.

먼저 사전에 준비해둘것이 필요합니다. 색인어 C_i에 대해 미리 Bigram 집합을 계산해서 DB에 넣어두는 것이지요.

이 색인어 Bigram 집합 테이블을 bglist라고 하겠습니다. 구조는 다음과 같이 됩니다.

form	bg
색인어의 형태	각각의 Bigram 요소

form과 bg 모두 Primary Key로 설정해두고, 또한 빠른 검색을 위해 각각의 form과 bg 필드에 Index를 설정해두었습니다.

예를 들어 색인어 puella가 있다면

form	bg
puella	^p
puella	pu
puella	ue
puella	el
puella	ll

와 같이 들어가는거지요.

이 테이블은 다음과 같은 PHP코드로 쉽게 만들수 있습니다.

//divideBG 함수는 문자열을 Bigram 형태로 쪼개서 반환해줍니다. function divideBG($str) { $str = '^'.$str.'$'; $l = strlen($str) - 1; $ret = array(); for($i = 0; $i < $l; $i++) { array_push($ret, substr($str, $i, 2)); } return $ret; } // insertToDB함수는 단어 w를 Bigram으로 쪼개 DB에 넣습니다. function insertToDB($w) { if(strlen($w) < 3) return; $l = divideBG($fw); $s = "INSERT IGNORE INTO `bglist` VALUES "; foreach($l as $n) $s .= "('$w', '$n'),"; $s = substr($s, 0, -1); $result = mysql_query($s); if(!$result) { $message = 'Invalid query: ' . mysql_error() . "n"; $message .= 'Whole query: ' . $s; die($message); } } $s = "SELECT * FROM `word`"; // 사전 내의 모든 단어를 가지고 와서 $result = mysql_query($s); while($row = mysql_fetch_assoc($result)){ insertToDB($row['form']); // 단어 형태마다 DB에 넣어줍니다. }

단어 수가 많아도 생각처럼 그리 오래걸리지는 않습니다.

자 실제로 정정 검색어를 골라내는 코드를 살펴봅시다.

function match($q, $limit = 10) { $bgl = divideBG($q); // 입력된 q를 Bigram으로 쪼개서 foreach($bgl as &$v) $v = "'" . $v . "'"; $s = "SELECT `form`, COUNT(*)/SQRT(LENGTH(`form`)) FROM `bglist` WHERE `bg` IN ("; $s .= implode(',', $bgl); // 쿼리문에 쑤셔넣습니다. $s .= ") GROUP BY form ORDER BY COUNT(*)/SQRT(LENGTH(`form`)) DESC LIMIT " . $limit; $result = mysql_query($s); if (!$result) { $message = 'Invalid query: ' . mysql_error() . "n"; $message .= 'Whole query: ' . $s; die($message); } $ret = array(); while($row = mysql_fetch_assoc($result)) { array_push($ret, array('f'=>$row['form'], 'c'=>$row['COUNT(*)/SQRT(LENGTH(form))'])); } return $ret; }

쿼리가 바로 떠오르시지 않는 분들을 위해 match함수에 $q로 'puela'를 주었다고 합시다. 생성되는 쿼리는 다음과 같을 겁니다.

SELECT form, COUNT(*), COUNT(*)/SQRT(LENGTH(form)) FROM `bglist` WHERE `bg` IN ('^p', 'pu', 'ue', 'el', 'la', 'a$') GROUP BY `form` ORDER BY COUNT(*)/SQRT(LENGTH(`form`)) DESC LIMIT 10;

길어보이지만 쪼개보자면

조건부 WHERE `bg` IN ('^p', 'pu', 'ue', 'el', 'la', 'a$')는 bg가 ^p, pu, ue, el, la, a$ 인 행들을 골라내라고 하고 있지요.

그룹 지정하는 부분 GROUP BY `form`은 골라낸 행들을 form이 같은 녀석들끼리 묶으라고 하고 있습니다.

정렬을 지정하는 부분 ORDER BY COUNT(*)/SQRT(LENGTH(`form`))에서는 그 묶인 결과들을 COUNT(*)/SQRT(LENGTH(`form`))순서로 내림차순 정렬하라고 하고 있습니다.

COUNT(*)/SQRT(LENGTH(`form`))가 뭘까요?

COUNT(*)는 GROUP으로 묶인 행들의 개수입니다. form이 puella인 bg들을 살펴보면 ^p, pu, ue, el, ll, la, a$가 있는데 이중 조건을 만족하는 녀석은 6개입니다. 즉

form	COUNT(*)	LENGTH(form)	COUNT(*)/SQRT(LENGTH(form))
puella	6	6	2.6...

이겠죠. LENGTH는 form의 길이를 반환하니 6이 되겠죠, 최종적으로 제일 오른쪽의 복잡한 식의 값이 나옵니다.

이 식은 

과는 약간 다릅니다. 분모 부분이 n(C)보다 1작고 게다가 제곱근까지 씌워져있지요. 제곱근을 씌운 이유는 제곱근을 벗기면 길이가 짧은 form에 대해 지나치게 높은 유사도가 나와서 그걸 좀 조절하기 위해 적당히 타협했습니다. 좀더 세밀한 조정은 더 많은 실험을 바탕으로 해야겠지만, 지금은 이정도로 만족스럽네요.

실제로 이렇게 해서 어떤 결과가 나왔을까요?

실제로 각각의 입력에 오타를 내보고 제시되는 정정 검색어 후보를 추려봤습니다.

오타	match함수로 제안된 녀석들(유사도 계수가 높은 상위 3개만)
puela	puella puellula puera
coniacio	conglaciō cōniciō conciō
strella	stēlla sella stilla
huis	huius vīs duis

굵게 처리한 놈이 원래 의도하던 검색어였습니다. 오호 이정도면 간단한 알고리즘으로 꽤나 좋은 성능을 발휘하는거같아요. 아주 흡족합니다. 게다가 속도도 매우 빠릅니다. match함수의 쿼리 처리시간은 0.01초도 안 걸리네요. (bglist에 30만개 가까운 행들이 있지만 그래도 빠릅니다.)

이 방법을 좀더 개선하는것도 가능합니다. 퍼지 연산을 이용해서 헷갈리기 쉬운 철자끼리 비교시에 중간 정도에 유사도를 주는 방법이지요.

즉 i와 l 은 헷갈리기 쉬우니 ille대신 llle라고 적어도 둘이 반정도는 일치한다고 계산해주는거죠.

문제는 MySQL에서는 이런 식으로 비교를 제공하지 않습니다. 그래도 약간의 편법을 이용해서 개선하는 방법이 가능합니다.

글이 너무 길어지는 관계로

그 내용은 다음 글에서 계속 다뤄보겠습니다.

---------------------------------------------

여러가지 경우를 가지고 실험을 해봤는데 유사도 함수를 조정하는게 더 좋은 결과를 가져온다는 사실을 알아냈습니다.

위 SQL 코드에서 사용한 공식은 위에서 소개한 S(M)에서 분모에 루트를 씌운형태였습니다.

위에서 소개했다시피 루트를 씌운 이유는 분모값이 너무 커져서 길이가 긴 색인어들이 후보에서 제외되는 현상을 배제하려고 한 것이었는데요, 루트를 씌워버리니 이제 역으로 길이가 짧은 색인어들이 상대적으로 불리해져버렸습니다. 또한 이 경우 S`(M)이 정규화되지 않아서(즉 평균적으로 유사도가 몇이 나오고, 최대치가 몇인지 등을 파악하기가 어려워져서) 특정 값을 기준으로 필터링하기가 힘들더라구요. 그래서 아예 다음 공식으로 식을 수정했습니다.

두 Bigram의 합집합과 교집합의 비율로 유사도를 계산하도록 고쳤습니다. 이제

인것이 자명하므로, 유사도 값들도 0과 1사이에 고르게 분포해서 특정 값을 기준으로 필터링하기도 용이해졌구요, 전반적으로 품질이 괜찮아졌습니다.