Bigram을 이용한 검색어 정정기능 개선 (PHP, MySQL)

앞선 글(Bigram을 이용한 오타 검색어 정정, 검색어 제안 기능)에서 Bigram을 활용해 검색어에 오타나 철자 오류가 있을때 유사한 검색어를 제안하는 방법에 대해서 설명했습니다. 여기서는 그 방법을 좀더 개선하는 방법에 대해서도 이야기해봅니다.

입력된 검색어를 2글자씩 끊어서 통계처리하는 방법은 중간에 한 두 글자 오타가 삽입되거나, 글자가 누락되거나, 글자 순서가 한 두개 바뀌는 것에 대해 높은 유사도로 변별해낼 수 있습니다. 문제는 문자 모양 혹은 발음이 비슷해서 헷갈리는 바람에 잘못 입력한 경우는 원래 사용자가 의도했던 검색어와 유사도가 높지 않을 수 있다는 것입니다.

로마자 알파벳 i와 L이 대표적인 예입니다. 대문자 I는 소문자 l과 거의 똑같이 생겼기 때문에 인쇄된 글을 그대로 타이핑하거나 외부에서 텍스트를 복사하는 경우 두 문자가 서로 바뀌었는지 모를수도 있습니다. 이를 해결하기 위해 퍼지 연산을 이용할 수 있습니다.

퍼지연산이란 애매모호함, 이것도 아니고 그렇다고 확실히 저것도 아닌 중간즈음 어딘가에 있는 것들을 처리하기 위한 수학적 모델입니다. 비교 연산을 예로 들면, 일반적인 비교연산은 1) 완전히 같거나 2) 그렇지 않으면 다르다 두 가지 결과로만 모든 것을 처리합니다. 둘이 비슷하긴한데, 조금 다르다, 혹은 아예 다르다, 거의 같다 이런건 비교연산에서 있을 수 없죠. 이걸 수식으로 쓰면 다음과 같이 될겁니다.

 (E는 i와 j의 비교함수입니다. 1이면 완전히 같음, 0이면 완전히 다름)

퍼지연산에서는 이 연산을 확장해서 E(i,j)가 0과 1사이의 모든 실수 값을 가질수 있게 합니다.

그러면 이제 우리는 다음과 같은 식으로 문자끼리의 유사도를 약속할 수 있습니다.

i와 i는 완전히 같으므로 1, i와 l은 많이 비슷하므로 0.7, u와 v는 약간 비슷하므로 0.5, a와 t는 완전히 다르므로 0.

이런식으로 26가지 알파벳에 대해 서로서로 닮은 정도를 값으로 미리 설정해놓고, 비교 연산에 사용하는 거죠. 이 값은 실제 오타에 관한 통계 자료를 바탕으로 사용자들이 자주 헷갈리는 문자에 대해서는 높은 값을, 거의 안헷갈리는 문자에 대해서는 낮은 값을 지정해줘야겠지만, 여기서는 제 가정만을 바탕으로 유사도 값을 설정해봤습니다.

이제 문자열끼리 비교하는 연산을 정의해봅시다. 기존의 문자열 비교연산은 문자열 중 하나라도 다른게 있으면 0(다름), 모두 같아야 1(같음)이었습니다. 즉 길이가 n인 문자열 A와 B에 대해

이었습니다. 이 함수를 다음과 같이 확장해봅시다.

이렇게 하면 F`함수는 기존의 F함수와 마찬가지로 E가 0혹은 1 두가지로만 설정되는 기존 비교 연산에서는 모든 문자가 같을때만 1의 결과를 내놓고, 나머지 경우는 0의 결과를 내놓습니다. E가 0과 1사이의 값일 경우에는 F`의 결과도 0과 1사이로 나오겠죠. 괜찮은 확장인거같습니다.

이 함수를 이용해서 문자열을 비교하면

F(au, au) = 1

F(ii, il) = 0.7

F(lis, ils) = 0.49

F(ai, at) = 0

위와 같은 결과가 나올것입니다. 나쁘지 않네요!

이제 이 비교연산을 이용해 앞 글에서 설명했던 두 Bigram 집합간의 유사도를 계산하면 되겠습니다만, 우리의 애매모호한 비교연산을 가지고 집합을 정의하는일은 까다로우니 적당히 생략하도록 하겠습니다.

문제는 실제로 이 계산방식을 어떻게 MySQL에서 적용하는가입니다. SQL에는 퍼지비교를 위한 구문이 없거든요. 그래서 약간의 타협을 보기로 했습니다.

애매모호한 비교연산을 위해 비교 단계를 2단계로 나눕시다. 첫번째 단계는 "엄격한 비교"라고 부르고, 두번째 단계는 "느슨한 비교"라고 부르겠습니다.

이제 우리에게는 3가지 상황이 있습니다. 

1) 두 문자열이 엄격한 비교와 느슨한 비교를 모두 통과하는 경우

2) 엄격한 비교는 실패하지만, 느슨한 비교는 통과하는 경우

3) 두 비교 다 실패하는 경우

1번의 경우는 완전 같음으로 해석하고, 2번의 경우는 반쯤 비슷함으로 해석하고, 3번의 경우는 아예 다름으로 해석하는 겁니다.

0과 1사이의 모든 유사도값에서 0, 0.5, 1 세 단계의 유사도 값만 가질수 있게 제한이 걸렸지만, 최종 결과는 크게 차이가 나지 않을거라는 희망을 가지고 진행해봅시다. (더 세밀한 유사도 값이 필요하다면 비교 단계를 더 늘려서 비교하면 됩니다. N단계로 나누면 유사도를 1/(N+1) 값의 차이로 근사할수있겠죠)

엄격한 비교는 우리가 일반적으로 행하던 비교 연산과 같습니다. 따로 처리할게 없습니다.

느슨한 비교는 비슷하다고 비교될만한 문자를 모두 같다고 비교합니다. 그러기 위해서 약간의 꼼수를 써야겠지요. 알파벳을 예로들면 i와 l이 같은 것으로 비교되어야하므로 사전에 i와 l을 특정한 같은 값으로 치환해놓는겁니다. 그러면 i와 l은 같은것으로 비교되겠지요.

다음은 제가 치환한 문자의 목록입니다. (대소문자는 다른것으로 처리됩니다.)

유사한 문자	이것으로 치환함	이유
b, d	B	모양이 비슷
c, k, q	C	셋 다 같은 발음이라서 헷갈리는 경우가 있음
i, j, l	I	i와 l은 모양이 비슷, i와 j는 라틴어에서 혼용되어 사용됨
f, p	F	발음이 유사해서 종종 헷갈림
u, v, w	U	셋 다 같은 발음이라서 헷갈리는 경우가 있음
x	CS	x는 cs또는 gs와 발음이 같게나서 헷갈리는 경우가 있음
h	빈 문자로 치환	어두의 h는 자주 탈락되고, ch, ph, th등에서의 h는 발음이 안됨

x와 h의 경우가 재미있는데요, nox는 nocs와 발음이 같게 나므로 둘을 같게 비교하게 만들어야겠죠. 위 표대로 치환을 진행하면

nox => NOCS

nocs => NOCS

로 둘이 같게 됩니다.

마찬가지 이유로 phil은 pil과 (대게) 발음이 같게 나므로 h를 빈 문자로 바꿔서 phil과 pil이 같게 만들어버리는거죠.

사전에 모든 Bigram을 추출해서 DB에 넣을때 엄격한 비교용 Bigram과 느슨한 비교용 Bigram을 모두 넣어놓고 비교시에 둘다 비교함으로써 우리는 퍼지비교연산을 조금이나마 흉내낼수 있습니다. puella를 예로 들어보죠. 퍼지연산이 없는 단순 Bigram에서는 다음과 같이 될겁니다.

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

여기서 느슨한 비교용 Bigram까지 합쳐봅시다. puella를 위의 치환표대로 치환하면 FUEIIA가 됩니다.

^p, pu, ue, el, ll, la, a$, ^F, FU, UE, EI, II, IA, A$

이제 잘못 입력된 문자열 pueiia가 puella와 얼만큼의 유사도를 가지는지 계산해볼까요.

A. 이전의 방법

pueiia를 Bigram으로 쪼개면

^p, pu, ue, ei, ii, ia, a$

이 경우 {^p, pu, ue, a$}가 교집합이 되므로 전체 유사도는

공식에 따라 4 / (7+7-4) = 0.4가 됩니다.

B. 2단 비교를 통한 방법

느슨한 비교를 위해 pueiia를 치환하면 FUEIIA가 되고, 이를 Bigram으로 쪼개면

^F, FU, UE, EI, II, IA, A$

입니다. 느슨한 비교의 경우 교집합은 {^F, FU, UE, EI, II, IA, A$}가 되고, 엄격한 비교와 느슨한 비교 끼리 겹치는 경우는 없으므로 전체 유사도는

(4+7) / (7+7-4 + 7+7-7) = 11/17 = 0.647...가 됩니다.

유사도가 훨씬 높게나왔습니다. 의도하던 대로지요.

PHP로 이를 구현하는건 어렵지 않습니다. 문자열 치환만하면 되죠.

function looseAlphabet($needle) { return str_replace(array( 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', ' '), array( 'A', 'B', 'C', 'B', 'E', 'F', 'G', '', 'I', 'I', 'C', 'I', 'M', 'N', 'O', 'F', 'C', 'R', 'S', 'T', 'U', 'U', 'U', 'CS', 'Y', 'Z', ''), $needle); }

Bigram 생성부는 약간만 수정하면 됩니다.

// insertToDB함수는 단어 w를 Bigram으로 쪼개 DB에 넣습니다. function insertToDB($w) { if(strlen($w) < 3) return; $l = divideBG($fw); $l = array_merge($l, divideBG(looseAlphabet($q))); // 느슨한 비교용으로 치환한 것도 배열에 추가! $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에 넣어줍니다. }

match함수도 약간만 수정하면 됩니다.

function match($q, $limit = 10) { $bgl = divideBG($q); // 입력된 q를 Bigram으로 쪼개서 $bgl = array_merge($bgl, divideBG(looseAlphabet($q))); // 느슨한 비교용으로 치환한 값도 bgl에 추가! $bn = count($bgl); // bgl의 원소의 갯수를 bn에 저장 foreach($bgl as &$v) $v = "'" . $v . "'"; $s = "SELECT `form`, COUNT(*)/(2*LENGTH(`form`) - COUNT(*) + " . $bn . ") AS c FROM `bglist` WHERE `bg` IN ("; $s .= implode(',', $bgl); // 쿼리문에 쑤셔넣습니다. $s .= ") GROUP BY form ORDER BY c 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['c'])); } return $ret; }

이게 전부입니다. 약간의 꼼수와 수정이지만 더욱 오타를 잘 잡아낼수 있게되었죠.

좀더 사용자의 의도를 잘 반영하기 위해서 다른 기법도 적용할 수 있습니다. 검색어별로 등장 빈도수를 계수로 적용하는겁니다. 이렇게하면 자주 등장하는 검색어일수록 높은 점수를 받을 수 있습니다. 검색엔진 등에서는 Bigram 유사도 결과에 빈도수도 반영해서 최종 계수로 평가하지 않을까 추측해봅니다만, 라틴어 사전에서는 이렇다할만한 빈도분석 자료가 아직 없어서 적용은 하지 않기로 했습니다.

굳이 사전에서 이 방법을 적용한다면 코퍼스 분석을 통해 어형별 빈도수를 추려내고 이를 Bigram 유사도 결과에 합치는 방법을 쓸수있을거같네요. 이건 앞으로의 숙제로 남겨두고 오늘 글은 여기서 마무리하겠습니다~