[PHP + MySQL] 언어 식별기(Language Detection) 개발기

요즘 뭔가를 만들고 나면 반드시 기록을 남겨두려고 노력하고 있습니다. 안 그러면 만든 저 자신조차 나중에 어떻게 만들었는지 잊어버려서 수정하거나 더 발전시키기가 어려워지더라구요. 나중에 안 까먹으려면 건물을 지었을때 설계도를 잘 남겨두어야겠죠. 그래야 건물이 무너져도 다시 지을수 있을테니깐요.

삽질에 대한 머릿말

몇 주 동안(시험기간 빼면 사실 별로 안되지만) 언어 식별기(Language Detector)를 만들고자 노력해봤습니다. 사실 이미 더 좋은 성능의 언어 식별 라이브러리가 여기저기 널려 있죠. 특히 구글이 제공하는 것은 확실히 구글답게 막강하다고 할 수 있습니다. 그래도 그냥 한 번 스스로 만들어보고 싶었어요. 그냥 재미있을거같아서. 

기초적인 아이디어는 예전에 라틴어 자동 크롤러(LMC: Latin Mini Crawler)를 작성했을때, 크롤러 모듈 중에 Bigram을 이용해서 해당 텍스트가 라틴어인지 추정하는 파트가 있었습니다. 간단한 아이디어는 아래와 같았습니다. 임의의 문자열 abcde가 있다고 할때, 라틴어라는 환경에서 abcde라는 문자열이 등장할 확률은 다음과 같이 계산할 수 있습니다.

( P(x|y)는 y환경에서 x가 일어날 조건부 확률입니다. )

그리고 이 조건부확률은 다음과 같이 계산할수있겠죠.

( count(x, y)는 Bigram 'xy'의 등장횟수입니다. )

즉 x다음에 y가 등장할 확률은 xy형태의 Bigram의 등장횟수를 x_ 형태의 모든 Bigram의 등장횟수로 나누면 구할수 있다는 거죠. 따라서 적당히 큰 라틴어 텍스트를 바탕으로 Bigram을 구축해놓으면 특정 문자열이 입력되었을때 이 Bigram 데이터를 바탕으로 라틴어에서 해당 문자열이 등장할 확률을 계산해 낼수 있다고 가설을 세워볼수 있습니다.

근데 이 확률이 얼만큼 나와야 입력 문자열이 라틴어라고 추정할 수 있을까요? 혼자 고민해보다가, 문자를 아무렇게 나열한 같은 길이의 문자열이 등장할 확률과 비교해보기로 했습니다. 각 문자가 26가지가 있으므로 해당 문자열이 아무 규칙없는 상태에서 등장할 확률은 

이 되겠죠. 이 둘을 비교해서 라틴어에서 해당 문자열이 등장할 확률이 높으면 라틴어라고 추정해보자고 규칙을 세웠습니다. 즉

아마도 라틴어: 

아마도 라틴어가 아님: 

이렇게 해보자는 게 처음의 아이디어였습니다. 그러나 이 방법을 사용한 라틴어 식별기는 품질이 많이 낮았습니다. (해당 라틴어 식별기는 http://latina.bab2min.pe.kr/xe/recogLang 에서 확인가능합니다.) 이유를 분석해본 결과

1. Bigram은 특정 언어에서 등장하는 음소배열제약을 제대로 반영하기엔 너무 약하다.
   라틴어와 대부분 단어의 형태가 유사한 스페인어, 이탈리아어, 프랑스어 등은 Bigram만으로는 너무 유사도가 높아서 제대로 식별을 해내지 못했습니다. 
2. 특정 문자열이 라틴어 환경에서 등장할 확률과 다른 환경에서 등장할 확률을 비교하는 것이 아니라, 특정 문자열이 라틴어일 확률과 다른 언어일 확률을 비교해야 한다.
   단어가 길어지거나 형태가 특이해질수록 라틴어 환경에서 등장할 확률은 한 없이 낮아집니다. 그렇다고 해당 단어가 라틴어가 아닌건 아니죠. 애초에 처음 세운 규칙에 오류가 있었던 것입니다. 각각의 언어에서 해당 형태의 단어가 등장하는 것을 전체로 보고, 라틴어에서 해당 형태의 단어가 등장하는 것의 확률을 계산해야 제대로된 확률 계산식이겠지요. 따라서 어떤 단어가 라틴어 단어인지 판별하기 위해서는 각종 언어에서 해당 단어가 등장하는 비율을 파악하고 있어야합니다.

이를 해결하기 위해서 1년만에 언어 식별기 제작 프로젝트를 시작하게 되었죠. 이 프로젝트는 작년의 라틴어 크롤러 프로젝트에서 제시되었던 두 문제점을 해결하는데 주안점을 두었습니다. 이번 프로젝트 계획은 대강 아래와 같았습니다.

1. 라틴어 크롤러(LMC)를 개조하여 각종 언어를 크롤링하는 크롤러로 만든다.
2. LMC로 각종 언어별 wikipedia를 수집한다.
3. 수집된 wikipedia 코퍼스를 언어코드별로 분류하고, unigram과 trigram, word별로 분석하여 DB에 저장해둔다.
4. 임의의 텍스트가 입력되면, unigram, trigram, word로 분석하고, DB에서 언어코드별 일치도를 구하여 산출한다.

1. LMC를 개조하여 범용 크롤러로 개선하기

class LMCrawler { private $sql; private $ruleData = array(); private $stopList = null; const RULE_CACHE = '30 DAY'; const PAGE_CACHE = '15 DAY'; const MAX_CRAWLDEPTH = 4; static function splitWord($w) { return preg_split("/[- ,.;:|\"'!*+[\]?#0-9()<>\/`_$&]|‘|’|“|”|\\s|—/", $w, -1, PREG_SPLIT_NO_EMPTY); } static function httpGet($url, $header = true, $timeout = 15) { $ch = curl_init(); curl_setopt($ch, CURLOPT_URL, $url); curl_setopt($ch, CURLOPT_RETURNTRANSFER, true); curl_setopt($ch, CURLOPT_HEADER, $header); curl_setopt($ch, CURLOPT_TIMEOUT, $timeout); curl_setopt($ch, CURLOPT_USERAGENT, 'Mozilla/5.0 (compatible; LMCBot/1.0; +http://latina.bab2min.pe.kr/)'); if(preg_match('/^https:/', $url)) { //curl_setopt($ch, CURLOPT_SSLVERSION,3); curl_setopt($ch, CURLOPT_SSL_VERIFYPEER, FALSE); } $output = curl_exec($ch); $info = curl_getinfo($ch); if(curl_error($ch)) { print('Line '. __LINE__ ." $url ".curl_error($ch)); return; } curl_close($ch); return array($output, $info); } static function absolutePath($url, $cur) { if(preg_match('/^\/\//', $url, $match)) { // protocol path preg_match('/^([^:]+:)\/\//', $cur, $match); return $match[1] . $url; } else if(preg_match('/^\//', $url)) { // host path preg_match('/^([^:]+:\/\/[^\/]+)\/(.*)$/', $cur, $match); return $match[1] . $url; } else if(preg_match('/^([^:]+:\/\/[^\/]+)(.*)$/', $url, $match)) { // full path return $url; } else { // current path preg_match('/^(.+\/)[^\/]*$/', $cur, $match); return $match[1] . $url; } } function __construct(){ $this->sql = new mysqli('----', '----', '****', '----'); } static function parseHeader($header) { $hl = explode("\r\n", $header); $ret = array(); foreach($hl as $h) { if(preg_match('/^([^:]+): (.+)$/', $h, $match)) { $ret[$match[1]] = $match[2]; } } return $ret; } static function splitURL($url) { if(!preg_match('!^([^:]+://[^/]+)/(.*)$!', $url, $match)) return; if(preg_match('!^([^#]*)#!', $match[2], $n)) $match[2] = $n[1]; return array($match[1], $match[2]); } function addPage($url, $newDepth, $fromPage = null, $anchorText = '') { if(!($match = self::splitURL($url))) return; $host = $match[0]; if(preg_match('/[^ -~]/u', $match[1]))$url = str_replace('%2F', '/', urlencode($match[1])); else $url = $match[1]; if(!$this->sql->query("INSERT INTO `lmc_page` (`host`, `url`, `status`, `last`, `depth`) VALUE ('" .$host."', '".$url."', 'p', NOW(), ".$newDepth.")")) { $s = "UPDATE `lmc_page` SET `depth` = ".$newDepth." WHERE `host` = '".$host."' AND `url` = '".$url ."' AND ((`depth` > ".$newDepth." AND `status` IN ('p', 'f', 'c')) OR DATE_ADD(`last`, INTERVAL ".self::PAGE_CACHE.") < NOW() )"; if(!$this->sql->query($s)) /*die('Line '. __LINE__ .$s ."\n". $this->sql->error)*/; } if($fromPage) { $anchorText = preg_replace('/<[^>]+>/', '', $anchorText); $s = "SELECT id FROM lmc_page WHERE host = '".$host."' AND url = '".$this->sql->real_escape_string($url)."'"; if(!($res = $this->sql->query($s))) die($s . $this->sql->error); $toPage = $res->fetch_assoc()['id']; $this->sql->query("REPLACE INTO lmc_link (fromPid, toPid, anchorText) VALUE (".$fromPage.", ".$toPage.", '".$this->sql->real_escape_string($anchorText)."')"); } } function fetchPage($limit = 10) { $s = "SELECT * FROM ((SELECT * FROM lmc_page WHERE status != 'd' AND DATE_ADD(last, INTERVAL ".self::PAGE_CACHE.") < NOW() ORDER BY last LIMIT ".($limit/2).") UNION (SELECT * FROM lmc_page WHERE status = 'p' ORDER BY last LIMIT ".$limit.")) t LIMIT $limit"; if(!$result = $this->sql->query($s)) die('Line '. __LINE__ .$s ."\n". $this->sql->error); if($url && $result->num_rows == 0) { $this->sql->query("INSERT INTO lmc_page (host, url) VALUE ('".$host."', '".$url."')"); $result = $this->sql->query($s); } $rarr = array(); while($row = $result->fetch_assoc()) array_push($rarr, $row); $result->close(); foreach($rarr as $row) { $cont = self::httpGet($row['host'] . '/' . $row['url']); if($cont) { $err = $cont[1]['http_code']; $header = self::parseHeader($cont[0]); } else $err = 0; $rcont = null; if($err >= 200 && $err < 300) { if((!$header['Content-Type']) || preg_match('/^text/', $header['Content-Type'])) { $rcont = $this->preprocPage($cont[0], $row); $st = 'f'; } else { $rcont = array(); $rcont[1] = $header['Content-Type']; $st = 'd'; } } else if($err >= 300 && $err < 400) { $this->addPage($header['Location'], $row['depth']); $st = 'e'; } else $st = 'e'; $cs = ''; if($rcont[0]) $cs = md5($rcont[0]); if($rcont[0] && $cs == $row['checksum']) { $st = $row['status']; if($st == 'p') $st = 'f'; } $s = "UPDATE `lmc_page` SET `content` = '". $this->sql->real_escape_string($rcont[0])."', `title` = '". $this->sql->real_escape_string($rcont[1])."', `lang` ='". $rcont[2]."', `charset` = '". $rcont[3]."', ". "`error` = ".$err.", `status`='".$st."', `last`=NOW(), `checksum` = '". $cs."' WHERE `id` = ".$row['id']; if(!$this->sql->query($s)) die('Line '. __LINE__ .$s ."\n". $this->sql->error); } } function preprocPage($cont, $ex) { // Extract Title if(preg_match('/<title>([^<]*)<\/title>/i', $cont, $match)) { $title = trim($match[1]); } // Extract Lang if(preg_match('/]*lang=(\'[^\']+\'|"[^"]+")[^>]*>/i', $cont, $match)) { $lang = strtolower(substr($match[1], 1, -1)); if(preg_match('/^([^-]+)-/', $lang, $nl)) $lang = $nl[1]; } // Extract Charset if(preg_match('/<meta [^>]+http-equiv=(\'|")Content-Type(\'|")[^>]+content=(\'[^\']+\'|"[^"]+")>/i', $cont, $match)){ if(preg_match('/charset=([^\'"]+)/', $match[3], $m)) $encoding = $m[1]; } else if(preg_match('/<meta charset=(\'[^\']+\'|"[^"]+")>/i', $cont, $match)){ $encoding = substr($match[3], 1, -1); } else $encoding = ''; $cont = preg_replace('/^.*?<!DOCTYPE[^>]*>/is', '', $cont, 1); $cont = preg_replace('/^.*?<(x?)html[^>]*>/is', '', $cont, 1); $cont = preg_replace('/<head>.*?<\/head>/is', '', $cont); $cont = preg_replace('/<(script|style)( [^>]*)?>.*?<\/\\1>/is', '', $cont); if($ex['depth']+1 < self::MAX_CRAWLDEPTH) { $this->sql->query("DELETE FROM lmc_link WHERE fromPid = ".$ex['id']); if(preg_match_all('/<a[^>]*href=(\'[^\']+\'|"[^"]+"|[^\'" ]+)[^>]*>(.*?)<\/a[^>]*>/', $cont, $match)) { foreach($match[1] as $k=>$m) { if(preg_match('/^[\'"]/', $m)) $m = substr($m, 1, -1); $m = html_entity_decode($m); $path = self::absolutePath($m, $ex['host'] . '/' . $ex['url']); $purl = self::splitURL($path); if(preg_match('/^http(s?)/i', $purl[0]) && preg_match('!^[-_a-zA-Z0-9:/.]+$!', $purl[0]) && preg_match('/wikipedia\.org/', $purl[0]) && $this->testRobotRule($purl[0], $purl[1])) $this->addPage($path, $ex['depth']+1, $ex['id'], $match[2][$k]); } } } $cont = preg_replace('/<link [^>]*>/is', '', $cont); $cont = preg_replace('/<meta [^>]*>/is', '', $cont); $cont = preg_replace('/<img [^>]*>/is', '', $cont); $cont = preg_replace('/<(audio|video) [^>]*>.*?<\/\\1>/is', '', $cont); $cont = preg_replace('/<embed [^>]*>/is', '', $cont); $cont = preg_replace('/<([^>]+) style=(\'[^\']*\'|"[^"]*"|[^\'" >]+)([^>]*)>/is', '<\\1 \\3>', $cont); $cont = preg_replace('/<([^>]+) class=(\'[^\']*\'|"[^"]*"|[^\'" >]+)([^>]*)>/is', '<\\1 \\3>', $cont); $cont = preg_replace('/<([^>]+) id=(\'[^\']*\'|"[^"]*"|[^\'" >]+)([^>]*)>/is', '<\\1 \\3>', $cont); $cont = preg_replace('/<([^>]+) href=(\'[^\']*\'|"[^"]*"|[^\'" >]+)([^>]*)>/is', '<\\1 \\3>', $cont); $cont = preg_replace('/<([a-zA-Z0-9]+)[^>]*>\\s*<\/\\1>/is', '', $cont); $cont = preg_replace('/\\s+(\/?)>/is', '\\1>', $cont); $cont = preg_replace('/<!--.*?-->/is', '', $cont); $cont = preg_replace('/(\\s)\\s+/is', '\\1', $cont); return array($cont, $title, $lang, $encoding); } function testRobotRule($host, $url) { if(!array_key_exists($host, $this->ruleData)) { $this->fetchRobotRule($host); } //print_r($this->ruleData[$host]); foreach($this->ruleData[$host] as $userAgent => $botRules) { // No disallows and no crawl delay? Ignore this ruleset. if((empty($botRules['disallow']) || !is_array($botRules['disallow']) || !count($botRules['disallow'])) && empty($botRules['crawl-delay'])) { continue; } // If the user agent matches ours, or is a catch-all, then process the rules: if($userAgent == '*' || preg_match('/' . str_replace('/', '\/', $userAgent) . '/i', "LMCBot")) { foreach($botRules['disallow'] as $rule) { $disallow = $rule; $disallow = preg_quote($disallow, '/'); $disallow = (substr($disallow, -1) != '*' && substr($disallow, -1) != '$') ? $disallow . '*' : $disallow; $disallow = str_replace(array('\*', '\$'), array('*', '$'), $disallow); $disallow = str_replace('*', '(.*)?', $disallow); if(preg_match('/^' . $disallow . '/i', '/'. $url)) { return false; } } } } return true; } function fetchRobotRule($host) { $s = "SELECT * FROM `lmc_rule` WHERE `host` = '".$host."' AND DATE_ADD(last, INTERVAL ".self::RULE_CACHE.") > NOW()"; if(!($result = $this->sql->query($s))) die('Line '. __LINE__ .$s ."\n". $this->sql->error); if($result->num_rows > 0) { $row = $result->fetch_assoc(); $this->ruleData[$host] = self::parseRobotsTxt($row['data']); $result->close(); } else { $res = self::httpGet($host . '/robots.txt', false, 10); if($res && $res[1]['http_code'] >= 200 && $res[1]['http_code'] < 300) { $txt = preg_replace('/^#.*$/m', '', str_replace("\r", "", $res[0])); $txt = preg_replace('/\n\n+/', "\n", $txt); $txt = preg_replace('/^\n/', "", $txt); $txt = preg_replace('/\n$/', "", $txt); } else $txt = ''; $s = "REPLACE INTO `lmc_rule` (`host`, `data`, `last`) VALUE ('". $host."', '".$this->sql->real_escape_string($txt)."', NOW())"; if(!$this->sql->query($s)) die('Line '. __LINE__ .$s ."\n". $this->sql->error); $this->ruleData[$host] = self::parseRobotsTxt($txt); } } static function parseRobotsTxt($rules) { $rules = explode("\n", str_replace("\r", "", $rules)); $outRules = array(); $lastUserAgent = '*'; foreach($rules as $rule) { if(trim($rule) == '') { continue; } if(strpos($rule, ':') === false) { continue; } $key = strtolower(trim(substr($rule, 0, strpos($rule, ':')))); $val = trim(substr($rule, strpos($rule, ':') + 1)); if($key == 'user-agent') { $lastUserAgent = $val; } if(!isset($outRules[$lastUserAgent])) { $outRules[$lastUserAgent] = array(); } if($key == 'disallow') { $outRules[$lastUserAgent]['disallow'][] = $val; } if($key == 'crawl-delay') { $outRules[$lastUserAgent]['crawl-delay'] = (float)$val; } } // Empty 'Disallow' means, effectively, allow all - so clear other rules. foreach($outRules as $ua => &$userAgent) { if(!isset($userAgent['disallow'])){ continue; } foreach($userAgent['disallow'] as $rule) { if($rule == '') { $userAgent['disallow'] = array(); break; } } } return $outRules; } }

LMCrawler 인스턴스를 생성하고 fetchPage() 함수를 호출해주면 DB lmc_page에 저장되어있는 웹페이지를 쫓아다니며 읽어들이고 새로운 페이지들을 DB에 추가합니다.

lmc_page 테이블 구조 lmc_rule 테이블 구조

미리 lmc_page에 wikipedia.org의 몇개 사이트를 넣어둡니다. 위키백과는 서로 유기적으로 연결되어있어서, 몇번 크롤링하다보면 각종 언어 페이지를 다 쫓아다니게 됩니다. 크롤링 깊이가 깊어지면 크롤링 대상이 너무 많아지므로 MAX_CRAWLDEPTH를 적당히 조절할 필요가 있었습니다.

2. Wikipedia 크롤링

우분투 서버에 crontab으로 해당 페이지를 붙여놓고 주기적으로 실행하여 약 2~3주 정도 크롤링 돌렸습니다. 그리하여 250개국어로 전체 약 8만여개의 페이지를 수집했습니다.

3. 수집한 코퍼스를 언어 코드별로 분석

class ProcPage { private $sql; function __construct(){ $this->sql = new mysqli('----', '----', '****', '----'); } /* 특정 문자열을 유니코드 단위로 한글자씩 끊어 배열로 반환*/ static function mbStringToArray($string) { while (mb_strlen($string)) { $array[] = mb_substr($string, 0, 1, "UTF-8"); $string = mb_substr($string, 1, NULL, "UTF-8"); } return $array; } /* 특정 문자열을 유니코드 단위로 n 자씩 묶어 배열로 반환*/ static function mbStringGram($string, $n = 3) { $string = '^'.$string.'$'; while (mb_strlen($string) >= $n) { $array[] = mb_substr($string, 0, $n, "UTF-8"); $string = mb_substr($string, 1, NULL, "UTF-8"); } return $array; } static function preprocText($page) { $page = preg_replace('!<p( [^>]*)?>(.*?)</p>!ui', '\2 ', $page); $page = preg_replace('!<(h[1-6])( [^>]*)?>(.*?)</\1>!ui', '\3 ', $page); $page = preg_replace('!<(br|div|ul|ol|li)( [^>]*)?>.*?</\1>!ui', ' ', $page); $page = preg_replace('@https?://[^\s]+@ui', '', $page); $page = preg_replace('!<[^>]*>!ui', '', $page); $page = preg_replace('! !ui', ' ', $page); $page = html_entity_decode($page); $page = preg_replace('@[-!\@#$%^&*()_=+\\/`~[\\]{};:\'"<>,.?—•→。、，«»·0-9]@ui', ' ', $page); return $page; } function procPage($num = 100) { $sum = 0; $res = $this->sql->query("SELECT * FROM lmc_page WHERE status = 'f' LIMIT ".$num); while($row = $res->fetch_assoc()) { $row['content'] = self::preprocText($row['content']); $this->makeGram1($row); $this->makeGram3($row); $this->makeWord($row); $this->sql->query("UPDATE lmc_page SET status = 'c' WHERE id = ".$row['id']); $sum++; } return $sum; } function makeGram1($row) { $page = $row['content']; $page = preg_replace('/\s/ui', '', $page); $c = array_count_values(self::mbStringToArray($page)); $q = "REPLACE INTO gram1 (pid, lang, chr, count) VALUES "; foreach($c as $k=>$v){ $q .= "(".$row['id'].", '".$row['lang']."', '".$this->sql->real_escape_string($k)."', ".$v."),"; } $q = substr($q, 0, -1); $this->sql->query($q); } function makeGram3($row) { $page = $row['content']; $ws = preg_split('/\s+/ui', $page, -1, PREG_SPLIT_NO_EMPTY); $arr = array(); foreach($ws as $w) { $arr = array_merge($arr, self::mbStringGram($w)); } $c = array_count_values($arr); $q = "REPLACE INTO gram3 (pid, lang, chr, count) VALUES "; foreach($c as $k=>$v){ $q .= "(".$row['id'].", '".$row['lang']."', '".$this->sql->real_escape_string($k)."', ".$v."),"; } $q = substr($q, 0, -1); $this->sql->query($q); } function makeWord($row) { $page = $row['content']; $ws = preg_split('/\s+/ui', $page, -1, PREG_SPLIT_NO_EMPTY); $arr = array(); $c = array_count_values($ws); $q = "REPLACE INTO word (pid, lang, chr, count) VALUES "; foreach($c as $k=>$v){ $q .= "(".$row['id'].", '".$row['lang']."', LCASE('".$this->sql->real_escape_string($k)."'), ".$v."),"; } $q = substr($q, 0, -1); $this->sql->query($q); } function sumGram1() { $this->sql->query("REPLACE INTO gram1_sum SELECT lang, lchr, SUM(count) FROM gram1 GROUP BY lang, lchr WITH ROLLUP"); } function sumGram3() { $this->sql->query("REPLACE INTO gram3_sum SELECT lang, lchr, SUM(count) FROM gram3 GROUP BY lang, lchr WITH ROLLUP"); } function sumWord() { $this->sql->query("REPLACE INTO word_sum SELECT lang, chr, SUM(count) FROM word GROUP BY lang, chr WITH ROLLUP"); } };

ProcPage 클래스의 procPage를 호출하면 수집된 코퍼스를 unigram, trigram, word별로 분석하여 DB에 저장합니다. 모든 페이지의 처리가 끝났다면 sumGram1, sumGram3, sumWord 함수를 호출하여 언어코드별 특정 형태의 등장빈도를 추출해냅니다. unigram과 trigram을 고른 이유는 처음엔 막연히 bigram을 이용해서 실패했던 경험에 기반하여 bigram보다 한층더 강력한 trigram을 이용하면 문자배열체계를 좀더 잘 반영할 수 있을거라는 기대 때문이었어요. 근데 trigram을 도입하려하니, 한글, 한자 같은 경우 너무도 많은 문자 갯수 때문에 각 문자별로 충분한 갯수의 trigram을 얻으려면 전체 코퍼스 크기가 무지막지하게 커야하고, 그만큼 처리가 오래걸리게 된다는 문제가 있었습니다. 그래서 작은 규모의 trigram을 사용하되, 한글, 한자 등에서 일치도가 부족하게 나오는 현상은 unigram에서 채우고자 했습니다. 사실 한글이나 한자가 등장하면 unigram만 이용해도 어떤 언어인지 다 알아낼수 있으니까요.

gram1 테이블 샘플 각 페이지 별로 어떤 언어에 어떤 문자가 몇번 등장했는지 정보가 들어간다. gram1_sum 테이블 샘플 gram1 테이블을 분석하여, 해당 언어에서 특정 문자가 몇번 등장했는지 저장한다. gram3_sum 테이블 샘픔 gram3 테이블을 분석하여 얻어지며, 해당 언어에서 특정 trigram 쌍이 몇번 등장하는지 저장한다. ^는 단어시작, $는 단어끝을 의미함.

gram3_sum테이블은 gram3 테이블을 분석하여 얻어지며, 해당 언어에서 특정 trigram 쌍이 몇번 등장하는지 저장한다. ^는 단어시작, $는 단어끝을 의미함.

(te언어에 민국$이 1번등장한것으로 보아 한글로 고유명사 '대한민국'이 들어간 있었던듯함. 이런식으로 위키백과 코퍼스는 약간의 오류가 포함된다는 것을 확인해 볼 수있죠.)

이런식으로 gram1_sum 테이블(약 200만 행)과 gram3_sum 테이블(약 500만 행), word_sum 테이블(약 600만 행)을 구성했습니다. 이 DB를 이용해서 언어식별 테스트를 돌렸으나, 결과는 너무 느리고 부정확했습니다. 원인을 분석해봤습니다.

1. 분석에 사용하는 테이블 크기가 너무 크다. 또한 분석에 사용하는 연산비용도 비싸다. 연산비용과 테이블 크기를 줄일 필요가 있다.
2. 위키백과의 특성 상 오염된 코퍼스가 많다. 특히 코퍼스 크기가 작은 언어의 경우 섞여 들어가는 불순 텍스트의 비중이 더 커진다.

먼저 2번을 해결하기 위해 전체 문헌의 수가 1000개 미만인 언어를 후보로 올리고 수집된 텍스트를 살펴보면서 오염여부를 확인해 다 삭제해버렸습니다. (심지어 어떤 소수 언어 위키는 전체 문서가 100개도 안되는데 다 영어로 써져있더라구요. 이런건 과감히 배제해버렸습니다.) 그리고 1번과 2번을 동시에 해결하기 위해 약간의 분석을 실시해봤습니다.

gram1_sum 테이블의 sum값별 빈도수

gram3_sum 테이블의 sum값별 빈도수

수업시간에 Zipf의 법칙을 배운게 엊그제 같은데(그리고 그걸로 중간고사 본게 실제로 엊그제인데!), 여기서 다시 마주하게 되었습니다. 가로축은 전체문헌에서 등장하는 횟수입니다. 세로축은 그 횟수에 해당하는 형태 수이구요. 즉 전체 문헌에서 1번만 등장하는 형태가 어마어마하게 많고, 여러번 등장하는 형태의 비중은 낮다는 것을 알수있습니다. 이 그래프를 뒤집어 거꾸로 그리면 Zipf의 법칙에서 자주보던 그 그래프가 되죠. (여러번 등장하는 형태가 소수라는 것은 소수의 형태가 전체 중 큰 비중을 차지한다는 뜻이죠.) 즉 그래프의 왼쪽부분이 Zipf 그래프의 Tail에 해당하는것입니다.

저는 이 Tail을 과감하게 버리기로 결정했습니다. 일단 워낙 조금 등장하는 형태다보니 이것이 제거되어도 전반적인 일치도의 변화는 미미하고, 또한 이렇게 조금 등장하는 형태들은 가끔 섞여들어가는 오염 요소인 경우가 많았기 때문이죠. 게다가 이 Tail들이 전체 DB에서 차지하는 비중이 매우 크기 때문에 이를 제거하면 테이블 크기는 획기적으로 작아집니다.

Tail을 지우기는 단순히 N이 특정한 값보다 작은 놈을 날려버리는것이 아니라, 각 언어의 전체 등장빈도 대비 차지하는 비율이 극히 작은(0.1% 미만) 녀석을 지우는 것으로 수행했습니다. 그 결과 gram1_sum 테이블은 약 4만행(이전의 1/50 크기), gram3_sum 테이블은 약 70만행(이전의 1/8 크기)로 줄일수 있었습니다. 

또한 여러번의 실험결과 word 일치도를 넣거나 빼거나 전체 결과에는 큰 영향을 주지 않는다는 사실을 깨달아 word 테이블은 아예 제외했습니다. word 일치도의 대다수를 차지하는 항목들이 짧은길이의 고빈도 사용어휘인데, 이 경우는 trigram과 일치도가 꽤나 종속적이기 때문에 이런 결과가 나온것같습니다. 그래서 가장 큰 크기를 차지하는 word_sum 테이블도 지워버렸습니다.

4. 입력된 언어와 DB내 언어별 특성과 일치도를 분석하기

3번까지 작업을 통해 DB를 구축했으니, 이제 SQL 연산을 통해 일치도를 계산해볼 차례입니다. 처음에는 DB에 해당 항목이 존재하면 그 비중을 합하여 전체 일치도를 계산하는 방법을 사용했습니다.

예)  abcde 문자열을 입력하면, ^ab, abc, bcd, cde, de$를 DB에서 찾고, 존재하는 항목의 가중치를 모두 합한 것이 일치도.

그런데 이 경우 unigram 간 일치도 계산을 실시할 때, 서로 비슷한 알파벳을 사용하는 로마 알파벳권 언어간 일치도가 다 높게 나와버리는 한계가 있었습니다. 같은 알파벳을 사용해도 언어별로 알파벳 사용비중이 다를수 있으니, 그 비중을 반영하여 일치도를 계산하는게 더 식별력 강한 일치도 계산방법이겠죠. 따라서 unigram의 경우 N차 벡터로 보고 벡터 간 내적을 통해 일치도를 계산하기로 했습니다. 두 벡터가 정규화되어있을 경우 내적값은 1에서 -1사이에 위치하고, 1에 가까울수록 더 일치한다는 결론을 내릴수 있겠죠. trigram에도 벡터 유사도 계산법을 적용하면 좋겠지만, trigram은 등장 형태가 너무 다양해서 벡터 차수가 지나치게 커져 합리적인 시간내에 연산을 끝낼수가 없었습니다. 

따라서 unigram은 벡터 유사도 연산, trigram은 일반적은 n-gram 유사도 연산을 사용하고, 이 두 결과를 합하는 방식으로 코드를 작성했습니다. 이를 위해서 gram1_sum 테이블은 각 언어별 벡터 크기로 나누어서 미리 정규화하였고, gram3_sum 테이블은 각 언어별 전체 trigram 횟수로 나누어 정규화했습니다.

gram1_sum 테이블 정규화. 벡터 크기로 정규화 실시 gram3_sum 테이블 정규화. 전체 빈도수로 정규화

class detectLang { private $sql; static function splitWord($w) { $w = preg_replace('@[-!\@#$%^&*()_=+\\/`~[\\]{};:\'"<>,.???→。、，≪≫·]@ui', ' ', $w); return preg_split('/\s+/', $w, -1, PREG_SPLIT_NO_EMPTY); } /* 입력 문자열을 유니코드 단위로 한 글자씩 쪼개어 배열로 반환 */ static function mbStringToArray($string) { while (mb_strlen($string)) { $array[] = mb_substr($string, 0, 1, "UTF-8"); $string = mb_substr($string, 1, NULL, "UTF-8"); } return $array; } /* 입력 문자열을 유니코드 단위로 N글자씩 쪼개어 배열로 반환 */ static function mbStringGram($string, $n = 3) { $string = '^'.$string.'$'; while (mb_strlen($string) >= $n) { $array[] = mb_substr($string, 0, $n, "UTF-8"); $string = mb_substr($string, 1, NULL, "UTF-8"); } return $array; } function __construct(){ $this->sql = new mysqli('----', '----', '****', '----'); } function detect($text, $max_result = 10) { // tokenize by space/special chrs $ws = self::splitWord($text); if(!$ws) return false; //make 3-gram array $tg = array(); foreach($ws as $w) { $tg = array_merge($tg, self::mbStringGram($w)); } $tg = array_unique($tg); // make 1-gram vector $c = array_count_values(self::mbStringToArray(strtolower(implode($ws)))); // 전체 벡터의 크기를 계산(제곱의 합에 루트 씌우기) $sc = sqrt(array_reduce($c, function($a, $x){return $a+$x*$x;}, 0)); // 전체 벡터 크기로 각 요소를 나눠 정규화 실시 $c = array_map(function($t) use($sc){return $t/$sc;}, $c); // input 1-gram vector into tmp table $this->sql->query("CREATE TEMPORARY TABLE IF NOT EXISTS ugt (lchr VARCHAR(4), s DOUBLE, PRIMARY KEY (lchr)) ENGINE=Memory"); $this->sql->query("TRUNCATE ugt"); $qr = "INSERT INTO ugt VALUES "; foreach($c as $k=>$v) { $qr .= "('".$this->sql->real_escape_string($k)."',".$v."),"; } $this->sql->query(substr($qr, 0, -1)); // query similarity by languages $qr = "SELECT uni.lang code, uni.v * .5 + IFNULL(tri.v, 0) weight FROM " /* 임시 테이블과 gram1_sum 테이블을 조인하여 내적 연산을 수행 */ ."(SELECT s.lang, SUM(s.sum*u.s) v FROM gram1_sum s " ."INNER JOIN ugt u ON s.lchr = u.lchr " ."WHERE s.lchr <> '' " ."GROUP BY s.lang) uni " /* trigram의 경우 존재유무만 체크해 가중치 총합 계산 */ ."LEFT JOIN (SELECT ts.lang, SUM(ts.sum) v FROM gram3_sum ts " ."WHERE ts.lchr IN ('".implode("','", $tg)."') GROUP BY ts.lang) tri ON tri.lang = uni.lang " ." ORDER BY weight DESC LIMIT {$max_result}"; if(!($res = $this->sql->query($qr))) return false; $result = array(); while($row = $res->fetch_assoc()) { $result[] = $row; } return $result; } }

detectLang 클래스의 detect 함수를 호출하면, 입력 텍스트를 분석하여 각 언어별 일치도를 계산해 반환해줍니다.

unigram으로 나온 유사도 값이랑 trigram으로 나온 유사도 값을 합칠때 unigram 쪽 유사도를 5배 가중하여 더했는데, 그냥 경험적인 값입니다. 왜인지는 모르지만 이러면 그럴싸하게 결과가 나오더라구요.

이곳에서 직접 테스트해볼수 있습니다. http://lab.bab2min.pe.kr/detectLang

한계와 앞으로 고민해볼 것들

일단 사용된 코퍼스가 위키백과 기반인지라 태생적으로 오염이 많습니다. 매우 높은 품질을 보장하기는 어렵죠. 하지만 이는 제가 선택한 코퍼스의 한계이지, 여기서 사용한 기법들의 한계는 아닐겁니다. 더 강력한 서버와 남아도는 시간이 있다면 다른 웹페이지도 크롤링하여 고품질의 코퍼스를 확보할 수도 있을겁니다.

또한 기본적으로 통계적 처리에 기반하다보니, 입력 텍스트가 일정 크기 이상이 되어야 유효한 결과를 냅니다. 널리 쓰이는 알파벳으로 두 세 단어 입력할 경우 어떤 언어인지 판별하는데 실패하곤 합니다. 이를 극복하려면 DB에 단어 사전을 추가해야할텐데, 위에서 설명했다시피 그럴 경우 처리해야할 대상이 너무 많아지고, DB가 기하급수적으로 커집니다.

어떻게 이런 문제들을 효율적으로 해결할지 고민해볼 만하겠군요. 다른 언어 모델을 적용해보는 것도 방법이 될수 있으려나요..?

p.s.

그리고 이 프로젝트를 진행도중, 수업시간에 특강으로 트위터 한국어 처리 라이브러리 (https://github.com/twitter/twitter-korean-text) 를 개발하신 선배님의 말씀을 듣게 되었는데, 언어 식별은 대게 trigram 모델로 처리한답니다. 제가 우연히도 모델을 잘 골랐었네요! Lucky Guy~!

p.s.2

코드만 이쁘게 정리된다면 누구나 이용할수있게 공개해보려고 합니다.

(디비 구조)

dl.sql