[펌] 한글 게임 정보 검색 시스템의 설계 및 구현

 

한글 게임 정보 검색 시스템의 설계 및 구현

정병진, 류근호

충북대학교 컴퓨터과학과

e-mail : {jbjin, khryu}@dblab.chungbuk.ac.kr

Design and Implementation of Korean game Information Retrieval System

                              ○

Byeogn-Jin Jeong, Keun Ho Ryu

Department of Computer Science, Chungbuk National University

충북 청주시 흥덕구 개신동 충북대학교 컴퓨터과학과 데이터베이스연구실

Tel 043)267-2254

한글 게임 정보 검색 시스템의 설계 및 구현 정병진, 류근호 충북대학교 컴퓨터과학과 Design and Implementation of Korean game Information Retrieval System                               Byeogn-Jin Jeong, Keun Ho Ryu Department of Computer Science, Chungbuk National University
	요     약 컴퓨터 게임과 인터넷의 급속한 대중화로 웹 상의 게임 정보가 급속히 증가하면서, 사용자들이 직접 웹 상에서 게임 정보를 검색하는 것은 거의 불가능하다. 따라서 기존의 범용 웹 정보 검색 시스템들을 사용하여 게임 정보를 검색하고 있다. 그러나, 범용 웹 정보 검색 시스템은 게임 정보와 관련 없는 정보를 많이 제공해주는 등의 문제가 있다. 이 논문에서는 사용자들에게 보다 적합하고 안정적인 게임 정보를 제공하기 위해 게임 용어 사전을 이용한 게임 정보 검색 시스템을 설계, 구현한다. 게임 정보 검색 시스템은 웹 로봇, 색인어 생성기, 질의 서버로 구성된다. 먼저, 웹 상의 문서를 수집하는 웹 로봇은 멀티 쓰레드 기법을 사용하여 자바로 구현한다. 색인어 생성기는 용어 추출 색인, N-gram 기법과 게임 용어 사전에 기반 한 자동 색인 기법으로 구현한다. 마지막으로 질의 서버는 CGI를 이용하여 사용자의 질의를 입력받아 검색 결과를 돌려준다. Abstract As the game information grows on the web rapidly through the rapid popularization of computer game and the internet, it is almost impossible for end-user to retrieve game information on the web. so end-user are retrieving the game information using general purpose web information retrieval. But on such system, there are some problems ,such as, providing the retrieving results with no relation to game information, and so on. In this paper, we are supposed to design and implement game information retrieval system to provide better relevant game information for end-user using game term dictionary. It consists of web robot, index builder and query server. At first, web robot which gathers documents on the web implemented Java using multi-thread method. Index builder is implemented using automatic indexing method based on derived indexing, N-gram method and game term dictionary. At last, query server return retrieving results for user query using CGI.

1. 서론

컴퓨터 게임과 웹(World Wide Web)의 대중화로 웹 상의 게임 정보가 증가하고 있다. 또한, 게이머들은 자신이 알고있는 게임에 대한 문제 해결 방법, 전술 및 전략들을 웹을 통하여 공개하고 있다. 그리고, 게이머들은 자신이 즐기고 있는 게임이나 새로운 게임에 대한 정보를 웹 상에서 찾고 있다. 그러나, 이런 정보들을 웹 상에서 찾으려 할 때 사용자가 직접 그 정보들을 찾기란 사실상 불가능하다. 이 문제를 해결하기 위해서 게이머들은 기존의 범용 웹 정보 검색 시스템을 사용하여 게임 정보를 검색하게 된다. 그러나, 범용 웹 정보검색 시스템들은 상당히 많은 검색 결과를 제공해 준다. 검색 결과들 중에는 사용자가 원하는 게임 정보와 관련이 없는 정보가 포함되어 있기도 하고, 사용자가 원하는 게임 정보와 관련이 없는 웹 문서 정보가 높은 우선순위를 가지고 검색 결과로 제시되어 지기도 한다. 따라서, 사용자들은 자신이 원하는 게임 정보의 검색에 실패하거나 원하는 정보를 찾을 때까지 결과로 제시된 웹 문서 정보를 하나하나 확인해 보아야 한다. 또한, 많은 검색 결과 중에는 변화하는 웹 문서 정보를 제대로 반영해주지 못하는 경우도 있다. 즉, 접근이 불가능한 문서들의 정보를 제시해 주기도 하고, 웹 문서의 내용이 변경되었는데  변경된 내용을 반영하지 못하여 다른  내용의 문서 정보를 검색 결과로 제공해주기도 한다.

범용 웹 정보검색시스템을 통해 원하는 모든 정보를 얻을 수 있다면 가장 이상적이지만 검색시스템의 속도와 업데이트 등 여러 요소에 한계가 있다. 따라서 앞으로는 분야별 전문화 된 검색시스템이 더욱 많이 나타나 검색시스템의 시장과 규모가 성장하는 상황의 기본환경으로 자리잡아야 한다[1].

따라서, 이 논문에서는 게임 정보 검색이라는 전문화된 분야에 있어서 게임 용어사전을 이용하여 보다 적합한 게임 정보를 사용자에게 제공해주는 게임 정보 검색 시스템을 설계, 구현한다. 게임 정보 검색 시스템은 웹 탐색 로봇, 색인어 생성기, 그리고 질의 처리기로 구성되고, 시스템은 UNIX 기반으로 구축한다. 먼저, 웹 탐색 로봇은 멀티 쓰레드 기법을 사용하여 Java로 구현하고, 인덱스 생성기 및 질의 처리기는 처리속도를 고려하여 C로 구현하며, 웹 문서 정보를 저장하기 위한 데이터베이스는 ORACLE을 사용하며, 질의처리는 CGI를 이용하여 연구를 수행한다

이 논문의 구성은 다음과 같다. 먼저 2장에서는 웹 정보 검색 시스템과 웹 정보 검색시스템의 구성요소들의 분석을 통해 웹 검색 시스템의 구성 및 구현기법을 살펴본다. 3장에서는 게임 용어 사전을 이용한 게임 정보 검색 에이전트 시스템을 설계하고, 4장에서는 게임 정보 검색 시스템 각 구성요소들을 구현한다. 5장에서는 기존의 범용 검색 시스템들과 비교 실험한다. 마지막으로 6장에서는 결론에 대해서 기술한다.

2. 관련연구

2.1 웹 정보 검색 시스템

웹 정보 검색 시스템은 웹 상의 문서에 포함된 정보를 수집하여 데이터베이스에 저장․관리한다. 그리고 사용자의 질의를 받아 데이터베이스에 저장된 데이터를 검색하여 사용자가 원하는 정보가 있는 웹 상의 위치 정보를 제공해준다[5].

일반적인 웹 정보 검색 시스템의 구성은 그림 1 과 같이 웹 검색 로봇, 색인어 추출기, 질의 서버 세 가지로 구성된다.

웹 검색 로봇은 웹 상에서 존재하는 문서들을 순환적으로 방문함으로써 웹 문서들의 정보를 수집하는 프로그램이다[8]. 웹에 존재하는 문서는 대부분 하이퍼링크를 이용하여 다른 웹 문서들과 연결되어 있는데, 자동적인 웹 문서 수집을 위해서는 하나의 웹 문서에서 출발하여 그 문서 내에 링크된 웹 문서들을 어떠한 순서로 검색할지 결정하여야 한다. 검색 로봇의 대표적인 항해 전략(traversal strategies)에는 깊이 우선 탐색(Depth First Search)과 넓이 우선 탐색(Width First Search) 두 가지 방법이 있다[10].

웹 검색 로봇을 사용하면 웹 문서정보를 쉽고 빠르게 찾을 수 있다는 장점이 있지만, 네트웍이나 검색되는 웹서버에 부하 가중시키는 등의 문제를 일으킬 수 있다. 이런 문제는 웹 검색 로봇이 URL의 특성을 인식하지 못하는 데서 발생한다. 즉, 같은 CGI URL을 무한히 반복적으로 접근하기도하고 한 서버의 URL만을 계속적으로 접근하여 그 서버에 부하를 가중시키거나 기능을 마비시키기도 한다. 이렇게 검색 로봇 검색으로 인한 웹 서버의 속도 저하 및 웹 서버에 기능에 영향을 줄 수 있는 CGI 검색을 막기 위해 Martijn Koster에 의해 로봇 배제 표준(A standard for Robot Exclusion)이 제안되었다[9].

그림 1) 웹 정보 검색 시스템의 구조

색인어 추출기는 수집된 웹 문서에서 색인어를 추출한다. 색인은 특정 단어에 대해 관련 있는 문서들의 링크로 구성되는데, 하나 이상의 문서가 같은 단어와 연관이 있을 경우 어느 문서가 더 관련이 있는지를 구별할 필요가 있게 된다. 이것은 사용자에게 결과를 출력해 줄 때 가장 우선순위가 높은 것부터 순서대로 보여줄 때 중요한 판단 요소가 될 수 있다. 색인어 추출 시 우선순위를 결정하는 대표적인 방법은 TF-IDF 알고리즘이다[12]. TF(Term Frequency)는 한 단어가 한 문서 내에 등장하는 횟수를 나타내고 DF(Document Frequency)는 한 단어가 검색된 N개의 문서의 집합 중에서 몇 개 문서에 등장하는가를 나타낸다. 특정 검색어가 한 문서에서 많이 나타난다면 그 문서는 해당 검색어에 대해 중요한 문서라고 판단할 수 있지만 여러 문서에 걸쳐 모두 나타난다면 그 단어에 대한 중요도는 떨어진다고 볼 수 있다. 따라서 문서의 우선 순위를 구하려면 TF값과 DF의 역인 IDF(Inverted Document Frequency)값을 곱한 값으로 나타낸다.

질의 서버는 사용자가 질의를 입력하면 색인된 정보를 이용하여 그 질의어가 포함되어 있는 웹 문서들의 위치 정보를 검색 결과로 보여준다. 일반적으로 질의 검색을 위해서 웹에서는 CGI를 이용하여 구현한다.

2.2 불리안 검색 모델

불리안 검색이란 불대수(Boolean Algebra)를 이용하여 질의를 만족시키는 문헌집단을 검색하는 것으로 검색논리는 논리적이거나 집합적 이론으로 해석할 수 있다[3]. 논리적 해석은 질의어가 포함된 문헌은 모두 질의 결과로 되는 것이다.  집합 이론적 해석은 질의문을 구성하는 각 질의어를 색인어로 갖는 문헌집합이 선택되고, 이 집합들에 AND, OR, NOT의 논리관계에 해당하는 집합 연산을 실시하여 질의 결과 문헌 집합을 구성한다.

불리안 논리를 이용한 질의는 정보 요구를 나타내는 용어인 색인어와 이 색인어들간의 논리적인 관계로 구성되므로, 정보요구를 비교적 정확하고 간단하게 표현할 수 있다.  또한 불리언 질의는 사용자가 작성하기에 편리하며 컴퓨터 처리가 용이하다는 장점을 가진다[4].

3. 게임 정보 검색 시스템

이 장에서는 게임 정보 검색 시스템의 구성에 대하여 살펴본다. 게임 정보 검색 시스템의 구성은 그림 2 에서 보는 것처럼, 데이터베이스 구축 모듈, 데이터베이스 관리 모듈 그리고 질의처리 모듈 세 부분으로 구성된다. 데이터베이스 구축 모듈은 웹 문서를 수집하여 게임에 관련된 문서들의 색인정보와 문서정보를 데이터베이스로 저장한다. 데이터베이스 관리 모듈은 저장된 웹 문서 정보의 접근 여부와 문서 변경 여부를 조사하여 안정적이고 최신의 정보를 제공한다. 마지막으로, 질의처리 모듈은 사용자가 입력한 질의를 가지고 데이터베이스를 검색하여 적합한 검색 결과를 사용자에게 제공한다.

그림 2. 게임 정보 검색 시스템

데이터베이스 구축 모듈은 Gamebot과, 게임 색인어 추출기로 구성된다. 먼저, Gamebot은 그림 3.와 같이 웹 문서 수집 모듈과 웹 문서 분석 모듈로 이루어진다.

그림 3. GameBot 구조

웹 문서 수집 모듈은 HTTP프로토콜[13]을 이용하여 미방문 URL들을 방문하여 웹 문서들을 수집한다. 웹 문서 분석 모듈은 웹 문서 수집 모듈이 전해준 웹 문서에서 방문할 URL들을 추출하여 미방문 URL 목록에 저장한다. 그리고 수집된 웹 문서의 색인어를 추출하기 위해 HTML 태그를 제거하여 색인어 추출기로 넘겨준다. Gamebot의 웹 문서 수집은 방문할 URL 데이터베이스에 더 이상 방문할 웹 문서정보가 없을 때까지 계속 검색한다.

게임 색인어 추출기는 게임 용어 사전을 이용하여 수집된 웹 문서가 게임 정보를 포함한 웹 문서인지 판별하여 게임 정보를 가지고 있는 웹 문서이면 색인어정보와 웹 문서 정보를 데이터베이스에 저장한다. 게임 색인어 추출기의 구성은 그림 4와 같이 색인어 추출 모듈, 가중치 부여 모듈과 저장 모듈로 이루어진다. 색인어 추출 모듈은 게임 용어 사전을 이용하여 웹 문서에서 색인어를 추출한다. 가중치 부여 모듈은 추출된 색인어에 가중치를 부여하고, 저장 모듈은 추출된 색인어와 문서의 정보를 데이터베이스에 저장한다.

          

그림 4. 색인어 추출기

게임 색인어 추출기에서 사용하는 게임 용어 사전은 낙스닷컴(주)에서 제작한 것으로 사전의 구성은 표 1 과 같다. 이 논문에서는 색인어 추출을 위해 게임 용어 사전 중에 한글 키워드와 한글 게임 타이틀을 사용하였다.

표 1. 게임 용어 사전 예

장르	게임타이틀(영문)	게임타이틀(한글)	한글 (키워드1)	영문 (키워드2)	분류	의미 (설명)
전략 시뮬레이션	Fallout	폴아웃	스트렝스	Strength	기타	힘을 나타낸다. 들고 다닐 수 있는 무게, 맨손, 칼 공격의 데미지에 영향을 준다....
롤플레잉	Baldur's Gate	발더스 게이트	투시력	Clairvoyance	기타	사정거리:특별, 지속시간:즉시, 캐스팅 시간:3, 효과범위:특별, 마법방어력계산:없음. 마법사는 ...
롤플레잉	Tempest	템페스트	아이스 블링거	Ice Blinger	무기	얼음속성의 세검으로 공격력 40, 한계력 100...

데이터베이스 관리 모듈은 저장된 게임 정보 웹 문서들이 사용자에게 검색 결과로 제시되었을 때 접근할 수 없게 되거나 다른 내용으로 변경되어 검색에 실패하는 것을 예방해준다. 그림 5에서 보는 것처럼 웹 문서 접근 모듈은 저장된 웹 문서 정보가 접근 할 수 있는지 조사하고, 변경 날짜를 이용하여 문서의 변경 여부를 검사하여 변경이 되었는지 검사한다. URL 추가 모듈은 문서에 변경이 있을 경우 Gamebot이 방문할 URL 데이터베이스에 URL을 추가하여 다시 문서를 분석할 수 있도록 한다.

그림 5. 데이터베이스 관리 모듈

질의 처리 모듈은 사용자에게 질의어를 입력받아 데이터베이스에서 질의어에 해당하는 문서 정보를 검색하여 관련 문서 정보들의 목록을 제공해준다. 질의 처리 모듈은 그림 6과 같이 입력 모듈, DB 검색 모듈, 순위부여모듈, 출력 모듈로 구성된다. 입력 모듈은 사용자로부터 검색할 질의어를 입력받는다. 검색 모듈은 입력받은 질의어와 일치하는 색인어 정보를 데이터베이스에서 검색한다. 순위 결정 모듈은 검색된 결과들을 게임 용어사전을 이용하여 질의어와 색인어들간의 연관성을 계산하여 연관성이 높게 나온 순으로 순위를 부여한다. 마지막으로, 출력 모듈은 한 페이지에 출력할 개수 만큼씩 검색 결과를 사용자에게 보여준다

그림 6. 질의처리 모듈

4. 게임 정보 검색 시스템 구현

이 장에서는 게임 정보 검색 시스템의 구현에 대한 내용들을 기술한다. 즉, 게임 정보 검색  시스템 각 구성 요소의 구체적인 동작 순서들에 대해 설명한다.

시스템의 구현은 UNIX 기반으로 구축한다. 먼저, 웹 탐색 로봇은 멀티 쓰레드 기법을 사용하여  Java로 구현하고, 인덱스 생성기 및 질의 처리기는 처리속도를 고려하여 C로 구현하며, 데이터베이스는 ORACLE을 선정하여 연구를 수행하였다. 그리고 질의서버는 CGI를 사용하여 사용자의 질의를 처리한다.

4.1 GameBot

GameBot은 처음으로 검색할 URL을 가지고 실행된다. 처음으로 실행되는 것이 아니면 검색할 웹 문서 데이터베이스에서 검색할 웹 문서 URL을 가져온다. 검색할 웹 문서 데이터베이스에 더 이상 방문할 웹 문서가 없으면 실행을 마친다. 검색할 웹 문서가 있으면 그 정보를 가져오고 검색할 웹 문서 데이터베이스에서 삭제한다. 가져온 웹 문서가 이미 검색한 웹 문서인지 확인한다. 검색한 웹 문서이면 검색할 웹 문서 데이터베이스에서 다른 웹 문서 URL을 가져온다. 검색하지 않은 웹 문서이면 해당 사이트를 검색하고 검색한 웹 문서를 분석하여 색인어 생성기에서 색인을 추출할 수 있도록 URL과 문서변경 날짜, TITLE 그리고 BODY의 내용을 그림 8과 같은 형식으로 저장한다. 분석한 웹 문서에 새로운 링크가 있으면 검색할 웹 문서 데