[정보] 정보검색론에관하여
페이지 정보
작성자 최고관리자 댓글 0건 조회 1,393회 작성일 20-02-05 16:04본문
출처:http://tong.nate.com/ggtong/23258835
웹 로봇을 개발하자!
1. 개요
검색엔진에서 말하는 로봇이란 다음과 같이 정의할 수 있다.
컴퓨터를 사용하여 주기적, 비 주기적으로 데이타를 능동적으로 수집하는 자동화된 프로그램.
여기서 "수많은 정보"들은 단순한 HTML문서가 될 수도 있고, XML, 워드문서, 이미지, 멀티미디어 정보, DB 데이타등도 포함된다. "주기적, 비주기적"이란 말은 로봇이 특정 대상을 지속적으로 감시하면서 데이타를 수집할 수도 있고, 그렇지 않을 수도 있다는 것이다. "능동적으로 수집"한다는 의미는 어떤 정보로부터 새로운 정보를 얻어내어 연관된 다른 정보를 스스로 찾아다닌다는 것을 말한다.
한가지 예를 들면, 매체사로부터 뉴스기사를 전송받아 DB에 저장하는 데몬이 있다고 하자. 이러한 녀석도 데이타를 수집하기 위한 장치임에 분명하나 로봇이라 부르지 않는다. 이유는 매체로부터 전송된 데이타를 수동적으로 받는 입장이며, 새롭게 받은 데이타에서 추가적인 정보를 유추해 내어 새로운 정보를 찾아내지도 않는다. 물론 로봇도 새로운 정보를 찾지 않고 이미 입력된 몇몇의 시드만을 사용하여 데이타를 수집하도록 할 수 있다. 그렇더라도 수집의 주체인 로봇 자체가 능동적으로 해당 데이타를 찾아가서 전송받게 된다는 것이 위의 예와는 차이라 볼 수 있다.
IE와 같은 웹브라우져도 넓은 의미에서는 로봇이라 볼 수 있다. 보통은 agent라는 용어를 쓰기도 하지만 브라우져 또한 로봇과 다를게 없다.
위 의미에 맞춰 생각해보면 이해할 수 있으리라 본다.
위 의미를 좀더 확장하여 웹로봇을 정의하면 다음과 같이 말할 수 있겠다.
인터넷상에 존재하는 수많은 정보들을 주기적 또는 비 주기적으로 수집하는 자동화된 프로그램.
위 정의의 의미는 로봇은 로봇인데 특정한 DB에 직접 접속하여 정보를 수집하는 것이 아니라 인터넷을 사용하여 인터넷 상에 존재하는 정보를 수집하는 로봇을 웹로봇이라고 보겠다는 것이다.
얼마전 필자는 로봇과 크롤러, 에이전트의 차이점에 대한 질문을 받은 적이 있다. 솔직히 세분하자면 용어를 사용한 사람들의 말을 직접 들어 봐야 할 것이다. 그러나 일반적인 통념상 로봇, 크롤러, 에이전트, 게더러 등등은 동일한 말이라 봐도 무방할 것이다. 단지 세분화 한다면 인터넷의 데이타를 수집하는 것은 웹로봇, 웹크롤러 등등으로 말하고 DB정보를 수집하는 것을 DB 로봇, DB 크롤러등으로 명명하는 것이 보통이다.
* 다음은 "효율적인 웹 로봇의 설계 및 구현에 관한 연구" 1997. 심해청 학위논문에서 발취한 내용이다. 웹로봇의 필요성에 대한 간략한 설명이라고 보면 되겠다.
하루가 다르게 변하는 정보화 사회에서 인터넷이라는 거대한 공간 속에서 노아의 홍수와 같은 엄청난 정보가 넘쳐나고 있다. 이러한 정보의 홍수 속에서 사용자가 원하는 정보를 찾는다는 것은 모래사장에서 바늘 찾기 보다 더 어렵다. 검색도구는 이렇게 찾기 힘든 정보를 쉽게 찾을 수 있도록 도와주는데 큰 도움을 주고 있으며 그 위치는 하루가 다르게 높아가고 있다. 그래서 인터넷 상에는 많은 검색 도구들이 등장하고 있다. 이러한 검색 도구들은 수동, 또는 웹로봇을 이용하여 자동으로 정보를 수집하는데 지금은 거의 웹 로봇을 사용하고 있다.
그러나 대부분 상업적인 목적으로 인하여 그 기술이나 특징에 대해 공개되지 않아 검색 도구의 특징을 보고 어림잡을 뿐이다. 검색 도구들은 보통 정보를 수집하기 위한 웹 로봇(Web Robot, Robot agent)과 수집되 자료에서 정보를 검색하는 검색엔진 부로 이루어져 있다.
검색엔진부는 정보검색이라는 분야로서 많은 연구가 이루어져 있으나 웹로봇은 그다지 맣은 연구가 이루어지지 않았다. 또한 이러한 웹로봇은 쉽게 작성할 수 있다는 이유로 아주 작은 부분으로 취급되어 지기도 한다. 그러나 검색엔진부는 수집된 자료가 있어야만 수행되어질 수 있으며 수집된 자료가 빈약할 경우 당연히 서비스의 질이 떨어지게 된다. 그러므로 웹 로봇의 위치는 아주 중요한 위치에 있는 것이다.
* 웹로봇의 구성요소
웹로봇에는 HTML 파서, HTTP 프로토콜, 소켓, 쓰래드, 대용량 데이타 저장 구조 등이 필요하다.
HTML 파서는 html안에서 새로운 url을 추출하여 반복적인 데이타 수집을 하기 위해 필요하다. 웹로봇용으로 쉽게 파서를 구현하려면 strstr함수를 사용하여 href만 찾아내어 문자열을 짤라내어 버리면 된다.
html 구조 자체가 간단하다 하더라도 초보자가 html 파서를 제작하는 것은 조금 버거운 일일 수 있다. 그래서 많은 프로그래머들이 공개된 소스나 모듈들을 많이 사용하고 있다.
그러나 이 강의에서는 html 파서를 직접 제작할 것이다. 누누히 강조하지만 원리를 모르는 상태에서 있는 모듈을 쓰기만 하는 프로그래머는 프로그래머가 아니다. 단지 코더일 뿐이다.
HTTP 프로토콜은 웹로봇 자체가 인터넷의 정보를 수집하는 기능이기 때문에 반드시 필요한 것이다. 이 프로토콜도 아주 잘 만들어진 오픈소스나 모듈들이 많이 있다. 그러나 만들것이다. ^_^;
소켓은 HTTP프로토콜 자체가 tcp/ip기반으로 동작하는 프로토콜이므로 반드시 필요한 부분이다. tcp/ip에 대해서는 본 강의 범위를 넘어서게 되므로 관련 책자를 참고하기 바란다. 이 강의에서는 소켓라이브러의 사용법과 멀티 쓰래딩 시의 타임아웃 처리에 대해 집중적으로 다룰 것이다.
쓰래드는 고속 처리를 위해서는 반드시 사용해야 할 구조이다. 웹로봇의 특성상 수천만건의 데이타를 빠른 시일안에 수집하기 위해서는 단일 쓰래드로는 무리가 있다. 만일 단일 쓰래드로 로봇을 만든다면 하루종일 데이타를 수집해도 10000~30000개의 문서를 수집하기도 힘들 것이다.
대용량 데이타 저장구조는 소량의 데이타를 수집할 목적의 로봇이라면 필요치 않다. 그러나 웹로봇의 경우는 앞서말한 모든 기술적 이슈보다도 오히려 큰 문제로 대두된다. 웹로봇 수행시간에서 가장 많은 시간을 소모하는 것이 url을 저장하고 관리하는 부분이다.
보통 천만개의 문서를 수집한다면 처리해야 할 url의 개수는 적개는 수억에서 많게는 수십, 수백억개의 url이 될 수 있다. 이는 개수 뿐만이 아니라 용량에도 아주 많은 영향을 받게 된다.
참고로 대량의 데이타를 처리할 경우는 DB를 사용하지 않기를 권한다.
조금 복잡해 보이기는 하지만 차근차근 훓어 보면 그리 복잡한 구조가 아닙니다.
왼쫀 아래에 보면 dic(사전)들이 있습니다. 이것은 형태소분석기에서 사용하는 사전으로 색인시에 사용했던 사전들과 동일한 구조로 되어 있는 것이 바람직합니다. 물론 서비스 구성에 따라 형태소분석기 세팅 자체를 서로 다르게 할 수도 있습니다. 바로 옆에 있는 시소러스 사전은 별도로 동작하게 할 수도 있으나 대부분 형태소 분석기에서 사전과 같이 처리하는 것이 일반적인 예입니다. 이런 시소러스사전류는 검색시 입력되는 질의를 확장한다거나 할 경우 많이 사용됩니다.
여기서 질의를 확장한다라는 의미는 뭘까요? 쇼핑몰 검색을 예로 봅시다. 어떤 구매자가 나이키의 조깅화를 구입하려 하는데 갑자기 조깅화란 단어가 떠오르지 않는다면 어떤식으로 질의를 입력 할까요? 보통 나이키, 아니면 운동화 정도로 우선 검색을 할 것입니다. 이때 운동화라는 개념을 좀더 확장하여 조깅화, 런닝화, 축구화, 등등의 키워드들을 추가하여 검색하게 된다면 보다 쉽게 최종 결과에 도달할 수 있을 것입니다. 단, 부적절한 질의확장은 검색성능이나 결과 개수에 악영향을 미칠 수 있으므로 많은 연구가 필요할 것입니다. 당연히 시소러스 사전 자체도 서비스에 맞게 잘 구성되어 있어야 합니다.
다음으로.. 바로옆에 있는 index db는 색인기가 만들어 놓은 색인 정보들입니다. 이전 강좌에서 설명했던 내용이니 확인해 보시면 될 것이구요.. 다른것 하나는 term cluster dic인데 검색 엔진의 기본기능이 아닌 관계로 넘어가겠습니다. ^_^;
사용자가 검색질의 엔진에 던지게 되면 방식은 여러가지가 있습니다. 물론 서비스를 구성하는 것에 따라 방법이 달라지게 되구요. 많이 쓰이는 것들은 인터넷 검색엔진들이 되겠지요. 보통 CGI를 통해 질의를 받아서 CGI가 엔진으로 전달하고 결과를 받게 됩니다.
엔진에서 클라이언트 API를 제공하거 어떤 프로토콜을 제공해 준다면 윈도용 어플리케이션에서도 결과를 받아볼 수 있겠지요. 어차피 소켓통신을 하는 데몬이기에 프로토콜만 알게 되면 어떠한 응용 프로그램에서도 엔진과 바로 맞붙어서 데이타를 주고 받을 수 있습니다.(당연하겠지요?) 그래서 이런 경우에는 client api, activeX 콘트롤, 일반 APPs, 관리도구 등에서 다양하게 접속하여 엔진의 결과를 받을 수 있습니다.
그러나 검색포탈이나 SI업체들의 검색엔진은 프로토콜을 공개하지 않습니다. 이유는 당연하겠지요. 네이버가 검색 프로토콜을 공개한다면 하루에도 수십번 해킹을 당할 수 있을 것입니다. 하지만 검색엔진을 직접 개발하는 한 그룹내에서는 이런한 프로토콜을 공개하는 것이 개발시 도움이 될 수 있습니다.
아무튼, 클라이언트에서 입력된 검색질의는 엔진에서 받아들이게 되면 맨 처음 질의분석기(Query Analayzer)라는 녀석이 받아들입니다. 그래서 유효한 검색질의인지, 유효하다면 엔진이 이해할 수 있는 방식으로 검색질의를 파싱한 후 어떤식으로 검색을 수행할지, 어떤 필드에서 검색을 할지, 키워드를 확장할지 등등을 결정하게 됩니다.
결정이 되면 바로 연산기(calculator)로 파싱된 질의를 전달하여 질의에 대한 연산을 수행합니다. 이때 연산기는 자연어처리모듈, 논리연산 처리모듈, 숫자처리 모듈들을 내장하여 검색옵션에 맞게 결과를 계산하게 됩니다.
연산기가 계산대상이 되는 데이타를 먼저 로딩하기 위해 파싱된 텀별로 index DB의 데이타를 읽기 위해 Retriever에게 질의를 던지게 되면 Retriever는 필요한 정보들을 index DB에서 로딩하여 연산기로 전달해 줍니다.
연산기가 모든 연산을 마치게 되면 결과는 순위화된 문서들의 일련번호와 문서들의 랭킹점수등이 남게 됩니다. 이러한 내용들을 Stream Generator로 전달하게되고 Stream Generator는 최종 사용자가 확인할 수 있는 결과(제목, 본문, URL, 기타 부가정보등등)를 만들어서 다시 질의분석기 에게 돌려주게 됩니다.
그러면 질의분석기는 정해진 프로토콜에 맞게 Stream을 정리하여 클라이언트에 전달하게 되고 최종 검색결과를 클라이언트에서 마음대로 조작한 후 보여지게 됩니다.
그림에서 오른쪽에 Summary Server와 Log Server가 있습니다. 후자는 일반검색엔진과는 별 상관이 없는 부분입니다. Summary Server는 보통 검색엔진 내에 요약정보를 따로 두는 경우가 많습니다. 그러나 대용량 데이타일 경우는 요약정보가 하나의 서버에 같이 존재하게 되면 Disk I/O문제도 발생할 수 있으며 여러가지 성능에 안좋은 영향을 미칠 수 있으므로 위와 같이 요약서버 자체를 분리하여 구성할 수도 있습니다.
이상 간단한 검색기 구조였습니다.
위부터 아래로 훑어 내려가면 되겠네요.
우선 색인 대상 데이타로 HTML, DB, W/P용 문서들, 기타 등등 Text-base의 모든 데이타는 색인 대상이 될 수 있습니다. 이러한 데이타를 검색엔진(특히 색인기)이 인지하려면 각각의 포맷을 알야아 할 것입니다. 그래야 필요한 정보를 추출할 수 있겠지요.
어제는 그러한 부분은 Dumper라고 간략히 말씀드렸읍니다. 이녀석을 오늘은 좀 다른말로 표현해보지요. 여기서는 Document Recognizer(문서 인식기)라고 표현하였습니다.
물론 인터넷 어디를 뒤져봐도 이런 용어를 찾기 쉽지 않을 거구요. ^^;
이녀석의 역할을 각각의 문서 포맷별로 필터를 가지고 있어서 해당 문서를 정확히 분석하여 F-TXT를 생성하는데 있습니다. 여기서 F-TXT는 검색엔진이 이해할 수 있는 형식화된 텍스트 문서입니다. 만일 색인기가 F-TXT형식으로 XML을 사용하겠다면 색인기는 XML파서만 있으면 되겠지요? 이런 경우라면 Document Recognizer는 각각의 문서들을 분석하여 XML로 재구성한 후 저장해 둘 것입니다.
일반적인 엔진들은 Document Recognizer를 필요에 의해서 간단한 프로그램을 작성하기도 합니다. F-TXT의 형식은 정해질 지라도 검색 대상 문서들의 포맷을 모두 지원하지 못하기 때문에 서비스를 구성할 때 간단한 프로그램으로 색인 대상 데이타를 F-TXT로 변환합니다. 결국 색인기는 F-TXT라는 형식만 인식하는 구조로 작성하고 Document Recognizer를 서비스 개발자가 직접 작성하게 하면 아주 유연한 엔진이 될 수 있을 것입니다.
다음은 F-TXT의 구성 예입니다.
DOCID : 1
TITLE : 정보검색시스템이란 무엇인가.
BODY : 정보검색이란... 어쩌구저쩌구.. 지화자 좋구나....
DATE : 20040520 130222
SIZE : 3428
URL :http://내도메인/data/ir.html
위 예는 간단한 예일 뿐입니다. 엔진 구성하는 사람의 마음이죠. ^^;
F-TXT가 만들어 지면 F-TXT 파서는 퍼블리슁이 필요할 경우 HTML Generator에게 파싱된 데이타를 전달하여 서비스 페이지를 만들게 됩니다. 또한 index Generator에게도 파싱된 데이타를 전달하여 실제 색인을 하도록 도와줍니다. 결국 핵심이 되는 것은 index Generator로서 이 녀석이 모든 색인DB를 생성하고 화일들을 관리하게 되지요.
Index Generator는 형태소분석기를 내장합니다. 물론 형태소 분석기는 여러가지 사전을 가지고 있어서 이런 사전정보와 경험정보, 규칙들을 사용하여 형태소 분석을 수행합니다. 형태소분석기를 사용하는 이유는 이전 강좌에서 간단히 말씀드렸던것 같네요.. 다시 말하자면 한국어 특성을 고려한 색인어를 추출하기 위함입니다. 물론 형태소분석기가 없더라도 색인어는 추출할 수 있습니다. 또한 어떤 경우는 형태소분석기가 오히려 색인어를 제대로 추출하지 못하는 경우도 있습니다. 그러나 여기서 보여드리는 색인구조는 국내의 엔진들이 일반적으로 사용하는 구조를 말씀드리는 것이구요. 아무튼.. 색인기는 형태소분석기를 통해 색인어를 추출하고 추출된 색인어를 기반으로 역화일을 생성합니다. 그리고 최종 요약정보도 생성하고 색인 과정을 마치게 됩니다. 이때 생성되는 화일들이 mapping table, term(keyword) trie, posting file, summary file 등입니다. 여기서 term trie와 posting화일을 역화일구조로 작성하게 됩니다.
위의 F-TXT 예를 기초로.. 검색서비스를 구성할 때 title에서만 검색, body에서만 검색, 날짜구간 검색 등의 검색서비스를 구축할 수 있을 것입니다. 이때 title, body, 날짜등은 별도의 역화일로 구성하면 의미상 명확할 뿐 아니라 검색효율을 상당히 높일 수 있습니다. 이유는 필터링을 할 필요가 없기 때문인데요.. 이렇게 구성하게 될 때 사용자가 title에서만 검색하는 명령을 내리게 되면 엔진에서는 title 필드에 해당하는 역화일을 찾아갈 수 있어야 합니다. 이런 부분을(title은 몇번째 역화일이다 라고 하는) 명시하는 것이 mapping table입니다.
term(keyword) trie는 index Generator가 생성한 모든 term(keyword)들을 트리형태로 표현하고 있는 색인 정보 입니다. 엔진마다 b-tree, b+ tree, trie, p tree등 다양한 방법을 사용합니다. 성격에 맞는 자료구조를 사용하면 되겠네요.. term trie는 posting file의 offset을 가지고 있어서 어떤 term이 나타난 문서들의 목록을 posting화일로 찾아가 구할 수 있도록 합니다.
posting화일은 문서들의 목록을 가지는 화일입니다. 단순히 문서번호를 나열해 둔 화일로서 term-trie에서 이 화일을 참조하여 문서목록을 가져옵니다. 여기서 문서목록이란 쉽게 생각하면 검색결과 목록이 될 수 있습니다.
summary file은 요약화일로서 검색결과를 화면에 보여줄 대 화면에 출력 가능한 데이타들을 모아둔 화일입니다. 쉽게 구성한다면 F-TXT를 그대로 사용해도 무방하겠지요.
그외의 모듈들은 사실 반드시 필요한 모듈들은 아닙니다. 필요에 의해 만들어 둘수도 있는 모듈들이라 설명은 하지 않겠습니다.
이상 간단한 색인기 구조였습니다.
검색 기법
다음은 BELKIN, NICHOLAS J.and CROFT, W. BRUCE,"Retrival Techniques," ARIST, 22(1987), PP. 109-145 에서 발취한 내용들이다.
BELKIN, NICHOLAS J.and CROFT, W. BRUCE등에 의해 제안된 검색기법의 분류방법
+-- Exact match
+-- Partial match --+-- Individual --+--- Structure-based
+-- Network +--- Feature-based
1. Exact match techniques(완전일치 기법)
검색된 도큐먼트들의 표현(representation)이 질문의 표현과 완전하게 일치된 것만 검색하는 방식이다. 초창기 대규모 검색시스템들에서 대부분 사용하던 방식이다. 이런 방법의 적용 예로는 불리언 검색, 전문검색, 스트링검색등이 있다. 단점으로는 다음과 같은 것들이 지적되어 왔다.
1) 이용자의 질의에 부분적으로 일치되는 경우의 텍스트들이 그 유용성에도 불구하고 검색에서 누락되는 예가 많다.
2) 검색된 텍스트들에 대한 적절성의 순위를 정하지 못한다.
3) 질문 및 텍스트 내에 존재하는 상호관련성이 있는 중요개념들을 전혀 고려하지 않는다.
4) 질문의 논리적 형성과정이 까다롭다.
5) 이용자의 질의 표현과 텍스트의 표현 비교가 오직 동일어휘로만 한정되어 있다.
이러한 단점에도 불구하고 초창기 많이 쓰이게 된 이유는 다음과 같다.
1) 검색기법을 변경하는데 드는 비용이 너무 많기 때문에 비경제적이다.
2) "exact match"기법이외의 대체기법들을 아직까지 대규모 시스템 환경에서 운영(테스트)해 본적이 없다.
3) 그러한 대체 기법들 조차도 실험적인 시스템 환경에서 테스트해 본 결과 그다지 만족스러운 것이 아니었다.
4) 이용자의 정보요구나 질의를 표현하는데 있어서 블리안 기법이 비교적 우수하다고 볼 수 있다.
그러나 현재 진보된 검색시스템들을 보게되면 위의 3,4번에 대한 이유가 무색해 진다. 현재 사용되고 있는 대부분의 상용 검색엔진들은 경험적으로나 이론적으로나 위의 3,4번에 대한 경우가 잘못된 생각임을 증명하고 있다.
2. Partial match techniques(부분일치 기법)
검색된 도큐먼트들의 표현이 질문의 표현과 부분적으로 일치된 경우의 것들로 함께 검색하는 방식이다. 여기서 Individual 방법은 이용자 질의를 각각의 개별 도큐먼트들과 비교 하는 방식을 말하며 Network 방법은 이용자 질의를 개별 도큐먼트들의 표현과 비교하 는 것이 아니라 개별 도큐먼트들 및 이와 관련된 다른 도큐먼트들과의 관계성 에 중점을 두어 작성되는 표현들과 비교한 검색기법이다. 이러한 네트웍 검색기법 에서는 개별 도큐먼트들의 내용에만 전적으로 의존하여 검색이 이루어지기 보 다는 이들과 관련을 맺고 있는 네트웍 기법으로는 cluster에 근거한 검색기법 과 Browsing기법 및 Spreading activation기법이 있다.
2.1 Individual, Feature-based
이용자의 질의 및 도큐먼트들의 표현방식 을 "색인어"와 같은 일련의 특징들로 표현하는 방식 --> 이러한 일련의 Features(특징)들은 각각 가중치로 표현될 수 있으며, text내에서 나오는 보다 복잡한 현상들을 표현하기에 적합하다. 이러한 feature-based기법에는 다시 Formal mode(여기에 해당되는 기법으로, Vector space model, 확률모델, fuzzy set model 등이 있다)과 Ad-hoc model이 있다.
이러한 범주의 기법들은 이용자의 질의를, 일련의 특징들 혹은 색인어들로 나타내는 도큐먼트 표현과 비교하는 방식을 취하고 있다. 이때의 도큐먼트 표현물들은 수작업이나 자동색인의 방식으로 도큐먼트의 텍스트 상으로 부터 추출되어지며, 마찬가지로 이용자 질의용어 역시 자연어로 표현된 질문으로 부터 직접 추출되거나, 색인어휘상의 용어를 사용하기도 한다.
여기에서 "feature"로 채택되는 요소들은, 단어나 어근, 구 혹은 개념들로서 이들과 관련된 가중치(weighte)값을 지니게 된다. 이러한 가중치들은, 그러한 각 요소들이 한 도큐먼트에 출현하는 빈도수나 혹은 이의 역 빈도수에 의하여 측정될 수 있다. 이러한 가중치의 표현방법이나 사용방법 및 계산방법 등은 각 시스템이 채택하고 있는 검색기법에 따라 다를 수가 있다.
(Formal) ==> Vector space model, probabilistic model, fuzzy set model.
2.1.1 Vector space model(벡터 공간 모델)
벡터공간 모델 상에서 각 도큐먼트들과 질문자들은 n차원 공간속의 벡터들로 취급되며, 이때 각 차원들은 색인용어들로 표현된다.
이 기법에 의한 검색절차는 다음과 같다.
1) 용어의 가중치는 정규화된 도큐먼트내의 빈도(tf)와 이의 역빈도수를 조합하여 계 산한다.
2) "낮은 식별치"(poor discriminatin value)의 값을 지닌 용어들은 시소러스내의 저 빈도용어들로 대치되며 구의 경우 고빈도 용어들로 대체된다.
3) 각 도큐먼트들은 이용자 질문에 대해서 그 유사성의 순위별로 출력되며, 이러한 과정은 "코사인"상관도(cosine correlation)에 의해 계산된다(벡터 공간내에서 이 용자의 질의에 가장 근접해 있는 도큐먼트들을 직관적으로 검색해 낸다)
2.1.2 Probabilistic model(확률모델)
확률모델은 지금까지의 검색기술에 새로운 방법론을 제시한 것으로서, 그 기술적 기반은 위의 벡터공간 모델로 부터 나온 것이다. 이 모델의 기본적인 목적은 이용자의 질의에 대한 적절성의 고확률순으로 도큐먼트의 순위를 정하여 검색하는 것이다. 즉, 각각의 도큐먼트를 구성하는 용어의 가중치가 "1"혹은 "0"의 값을 가질 수 있고 또한 이러한 각각의 용어들은 다른 용어들에 대해서 독립성을 지녔다고 가정하여 각 도큐먼트들의 순위를 정하는 방법이다.
2.1.3 Fuzzy set(퍼지 집합 이론)
이것은 겁색기법상으로 볼 때 블리언 질문기법과 도큐먼트 순위 매김기법을 통합한 기법이나 벡터공간 모델에 기초한 확장된 블리언 검색기법과 비교해 볼 때, 이러한 통합에는 한계가 있음이 드러났다.
2.1.4 Ad hoc(애드 혹 모델)
이 모델의 기본은 질의 용어군과 도큐먼트 용어군과의 겹침(over-lap)의 정도를 측정하여 그 유사성의 정도에 의하여 문헌을 검색하는 기법이다.
2.2 Individual, Structure-Based Techniques(개별적, 구조기반 기술)
이러한 범주에 드는 검색모델의 특징은 이용자 질의나 도큐먼트의 내용을, 색인어 등의 방식이 아닌 좀 더 복잡한 구조적 형태(structure)로 표현하여 이를 비교하는 방식이다. 이러한 검색기술은 특히, 특정한 전문주제분야에 적용되는 것이 적절하다.
2.2.1 Logic(논리모델)
도큐먼트의 텍스트가 담고있는 핵심적인 정보는 몇개의 짧은 문장으로 표현될 수 있으며, 이러한 문장들은 일정한 논리식으로 표현이 가능하다. 이와 마찬가지로 이용자의 질의도 논리식에 의한 표현이 가능하며, 이러한 질의는 논리식과 연계된 추론법칙에 의해서 그 해답이 가능하다.
예) 도큐먼트의 주제내용.
"If a company sells computer, it is financially viable".
==> 논리식으로 표현
==> (for all(x) (if (sells x computer) (viable x)))
이때 이용자의 질문(viable?)의 경우 "forward chaming"으로 해답이 가능하다. 이러한 모델의 가장 커다란 어려움은 각 텍스트들을 논리식으로 전환하는 작업인데, 현재는 수작업으로 하고 있다.
2.2.2 Graph(그래프 모델)
이 모델은 그래프 형태의 표현방법을 이용한 검색기법이다. 즉, 그래프 형태의 표현방법은 노드들과 이러한 노드들간의 edges(links)들로 이루어져 있는데, 이러한 노드들과 edges들은 주로 자연어 처리과정을 통해서 얻어지는 의미망(semantic nets), 혹은 의미프레임(semantic frames)으로 표현된다. 검색기법은 질의어의 그래프 구조와 도큐먼트의 그래프 구조를 서로 비교하여 그 유사성에 의거하여 문헌을 검색하거나 그 순위를 정하는 방식이다.
2.3 Network(네트웍 모델)
2.3.1 Cluster(클러스터 모델)
클러스터란, 내용이 유사한 일련의 도큐먼트군을 의미한다. 이것은 SMART프로젝트에 채택된 검색기법으로서, 클러스터 계층구조(CLUSTER HIERACHY)에 의한 것이었다.
* 클러스터 계층구조 --> 전체의 도큐먼트들을 몇개의 클러스터들로 나눈후에 각각의 클러스트들을 또다시 작은 클러스터들로 나누는 반복된 작업구조.
검색방법은 이용자의 질의내용을 최상위의 클러스터로 부터 최하위의 클러스터들 까지 하향식으로 비교하여 그 유사성의 큰 것부터 차례대로 검색해 내는 방식.
2.3.2 Browsing(브라우징 기법)
각각의 도큐먼트, 색인용어, 서지적 정보들을 시스템상에서 노드와 컨넥터들로 표현된 네트웍 구조로 만들 수 있다면, 이 때, 이용자는 이러한 네트웍을 훌터나가면서(Browsing) 필요한 도큐먼트들을 검색하는 기법.
이러한 Browsing기법에서 주목할 사항은 검색기법상 이용자 질문식의 형성(query formulation)에는 중점을 덜 두는 반면에, 이용자로 하여금 Browsing과정 중에서, 즉각적인 피드백을 강조하는 시스템이다.
I R 시스템의 예
노드(node) --> 도큐먼트, 색인어, 주제영역지식, 저자, 저널명.
링크(links) --> 색인정보, 시소러스 정보, 인접노드정보, 인용, 저자사항.
2.3.3 Spreding activation(스프래딩 액티베이션 모델)
위의 Browsing기법과 유사한 모델
네트웍 상에서 이용자의 질문에 해당되는, 어느 한 부분의 노드(색인어 혹은 도큐먼트) 및 이와 관련된 또 다른 노드들만 활성화(activate)시켜 가면서 최종 도큐먼트를 검색해 내는 방식. --> 예를들어 이용자의 질문에 의해서 어느 한 색인어가 선택되어 졌을 때, 이 색인어와 연결된 도큐먼트들 및 관련 색인들 역시 함께 활성화시키게 되는 방식.
2.4 Feedback Methods(피드백 기법)
이 기법은, 원래 "Feature-based"기법에서 발전되어 온 것으로서 현재는 모든 검색기법에서 응용되고 있다. 이 기법의 핵심은, 질의 용어에 대한 기준치를 검색도중에 수정해 가면서 최적의 도큐먼트들을 검색해 내는 방식이다. 이러한 가중치의 수정은, 적합한 것으로 판단된 도큐먼트들 속에 포함된 색인어들의 빈도수에 의해서 결정된다. 10-20%.
Relative Performance of Retrieval Techniques(검색기법의 상호성능 비교)
(Comparation Performance Studies)
1) 전반적으로 완전일치(exact match)기법보다는 부분일치(paricial-match)기법에 의 한 검색 결과가 더우수한 것으로 나타났다.
2) Feature-based기법 중에서는 특히 색인어에 대한 가중치 부여 기법을 사용한 확률 모델 기법이 가장 우수한 것으로 조사되었으며, 이때 용어의 가중치를 주는 방식 에 따라 그 검색성능이 크게 달라졌음이 밝혀졌다.
3) 클러스터 검색기법의 경우 "individual feature-based"검색에 버금가는 성능을 지녔으며, 특히 다른 검색기법들에 비해서, 높은 정확율을 가져온 것으로 나타났다. 따라서 클러스터 기법은 "individual feature-based"모델을 대체할 수 있는 좋은 기법이다.
정보검색시스템의 구성요소
1. 정보검색시스템이란?
정보 수요자가 필요하다고 예측되는 정보나 데이터를 미리 수집, 가공, 처리하여 찾기 쉬은 형태로 축적해 놓은 데이터 베이스로부터 요구에 적합한 정보를 신속하게 찾아내어 정보 요구자에게 제공하는 시스템을 말한다.
2. 배경학문
자료구조론 (Speed & Memory Trade-off)
데이터베이스론 (DB Indexing)
검색알고리즘
AI의 Search, NLP, Story understanding Algorithm
ES의 Inferencing
3. 구성요소
웹로봇
웹상에 존재하는 문서들을 가져오기 위해서 웹의 하이퍼텍스트 구조를 자동적으로 추적하여 참조되어지는 모든 문서들을 재귀적으로 검색하는 프로그램을 말한다. 여기서 '재귀적으로'라는 의미는 어떤 명시된 트래버스 알고리즘으로 유한하게 정의되어지는 것이 아님을 주목하라. 비록 로봇이 문서 선택을 위해 몇몇의 발견적인 학습법을 허락한다거나 방문하기 위한 문서의 순서를 정한다거나 하더라도 여전히 로봇이다.
일반적인 웹브라우저는 로봇이 아니다. 왜냐하면 그것들은 인간에 의해 수행되어진다. 그리조 참조되어지는 문서들을 자동적으로 수집하지 않는다.
크롤러(crawler), 스파이더(spider), 개더러(gatherer), 웸(worms), 안츠(ants) 등 다양한 이름으로 불리우지만 일반적인 명칭으로는 로봇이라 칭하는 비율이 높은듯 하다.
로봇을 얘기하면서 빼 놓을 수 없는 것이 로봇 배제 표준(robot exclusion standard)이다. 봇은 상당히 무책임한 프로그램이 될 수 있으며, 심한 경우는 웸바이러스와 같은 행동을 보일 수 있다. 필자의 경우 회사에서 로봇을 구동시키던 도중 국내의 유명 쇼핑몰의 DB를 죽여버린 경우가 있었다. 다행히 관용을 베풀어 주셔서 조용히 넘어갈 수 있었지만 돌이켜 보면 무척이나 위험한 상황이었다. 이처럼 잘못 구성된 로봇으로 인해 특정 사이트를 죽여버리거나 망 자체를 마비시킬 수도 있는 것이 로봇이다. 이런 로봇의 위험에서 자신의 웹사이트를 보호하기 위한 표준적인 방법이 로봇 배제 표준이라 생각하면 된다. 하지만 대다수의 로봇들이 이러한 표준을 지켜주는 것이 아니란 것을 명심하라. 독자가 로봇을 로봇을 만들 생각이라면 반드시 이 표준을 지켜주기를 권장한다.
로봇 배제표준에 대한 자세한 설명은 시간이 나는대로 따로 간단한 강좌를 만들겠다.
스토리지
검색엔진에서 사용할 색인용 데이타를 컴퓨터의 저장장치에 기록하여 두는 곳을 말한다. 초창기 상용화된 검색엔진들은 일반적인 DBMS를 사용하여 데이타를 저장하였다. 이는 관리 및 사용이 아주 용이하기 때문에 매우 효과적으로 수행될 수 있었으나 데이타가 대용량화 되어지고 알고리즘이 복잡해 지면서 점차 화일 시스템을 직접 제어하여 데이타를 저장하는 방식을 많이 사용한다. 단순하게는 화일에 필요한 키워드 정보와 포스팅화일 요약화일을 저장하는 방식에서 좀더 성능을 향상시키기 위해 물리적인 계층에서 저장장치(보통 하드디스크)를 제어하여 자체의 검색엔진 전용 화일 시스템을 구축하는 경우도 있다. 몇몇 공개된 소프트웨어 중에서는 검색엔진 전용 색인 DB를 만들어 배포하는 곳도 있다.
검색엔진을 구축하다보면 용도에 따라 Read-only 시스템으로 구축하는 경우와 read-write 시스템으로 구현하는 경우가 있다. 전자의 경우는 화일 시스템을 구성하는 것이 무척이나 간단한 문제이지만 후자일 경우는 아주 심각해진다. 허나 후자와 같은 시스템을 요구하는 업체들의 비중이 점점 높아지는 추세이며 업계에서는 이런 부분에 많은 투자를 하고 있는 시점이다.
검색엔진에서 사용되는 기본적인 스토리지의 구성은 보통 3단계로 구성되며, 이는 텀리스트, 포스팅 화일, 요약화일로 구성된다.
색인기
웹로봇을 통해 수집된 문서들을 빠르고 정확하게 검색하기 위해 문서의 중요 키워드를 추출하고 이러한 키워드들의 상관관계나 문서들의 상관관계를 정의하여 스토리지에 저장하는 프로그램이다. 키워드를 추출하기 위해 형태소분석기나 스테머등을 사용하거나 또는 n-gram 방식을 사용하기도 한다. read-write시스템의 경우는 색인기와 검색기가 하나의 시스템으로 구성되기 때문에 임계영역에 대한 문제가 대두된다. 다양한 랭킹 알고리즘에 의해 색인기의 모양은 달라지게 되면 알고리즘의 복잡도와 추출되는 색인어의 양에 의해 색인 속도에 많은 영향을 주게 되며, 이러한 색인 속도는 색인기의 전체 성능을 평가하는 기준이 되기도 한다. 스토리지는 색인기의 일부분으로 구성될 수 있으며 결국 스토리지의 구조는 검색 모델(또는 랭킹 알고리즘)에 의해 결정되어진다.
형태소분석기
형태소 분석이란 여러 형태소들의 묶음이 표층 형태로 나타나는 하나의 어절로부터 의미를 갖는 최소 단위인 각 형태소를 분석해는 내는 것으로 정의된다.(강승식) 문서의 핵심 키워드를 추출하는 기본적인 시스템이다.
검색엔진에서는 보통 형태소분석기의 모든 기능을 사용하지 않고 색인어 추출만 하기위해 특정 형태소만 취하는 경우가 대부분이다. 초기 정보검색에서는 색인어로 적합한 형태소는 명사로 국한하였다. 허나 발전을 거듭하면서 현재는 각 형태소의 구조적인 관계 및 의미관계까지 고려한 색인어를 추출하기도 하며, 이러한 방식은 자연어 검색의 기본이 된다.
스테머
보통 어근 추출용으로 많이 사용되었으며 영어권 언어에 대해서 많이 적용된다. 언어적 특성상 한국어와 같은 교착어는 어미변화와 활용형들이 아주 심한 편이어서 단순한 스테밍 알고리즘만으로 처리하기에는 문제점이 있기 때문에 한국어는 형태소분석기를 주로 사용한다. 영어같은 경우 몇가지의 간단한 룰만 적용하여 스테머를 구성할 수 있기 때문에 속도가 빠르고 효율적인 시스템을 구성할 수 있다.
검색기
사용자가 입력한 검색 질의를 색인기가 생성하여 둔 스토리지에서 정의된 검색 모델(랭킹 알고리즘)에 의해 가장 유사한 문서를 추출하여 검색하여 주는 기능이다. 질의 분석기가 별도로 내장되어 있어야 하며 특성상 대량의 정보를 빠른 시간안에 주어진 알고리즘으로 계산해 내는 능력이 필요하다. 순위화를 위해 랭커를 가지고 있으며 보다 빠른 검색을 위 캐쉬를 사용하기도 한다.
브로커
검색엔진에서 사용하는 컬렉션은 다양한 여러 종류로 구성될 수 있다. 이러한 다양한 컬렉션에 대해 하나의 질의로 검색을 할 경우 어느 컬렉션을 검색할지 최종 검색된 컬렉션별 결과들을 어떻게 취합할지에 대한 문제가 발생하게 된다. 이러한 문제를 해결해 주는 것이 브로커이다. 입력된 질의를 분석하여 검색할 대상을 찾고 각 컬렉션에서 결과를 검색한 후 이에 대한 최종 결과를 취합하여 전달해 주는 역할을 하게된다. 포탈 사이트의 통합검색 CGI도 넓은 의미에서 브로커라 할 수 있겠다.
요약기
문서의 핵심이 되는 내용을 간결한 문장으로 축약하여 주는 기능이다. 검색된 문서의 모든 내용을 보여주기에는 그 양이 너무 많기 때문에 검색자의 편의를 위해 잘 정제된 요약 내용을 보여줄 필요가 있다. 경우에 따라서는 검색기에 이런 요약기능을 부여하기도 하며 별도의 서버로 구축될 수도 있다. 자동요약 분야는 아직도 많이 연구가 되어지고 있는 분야이다.
각종 필터
다양한 포맷의 문서들에서 텍스트 정보를 추출하기 위한 기능이다. doc 화일 같은 경우 binary로 구성되어 있기 때문에 실제 text정보를 추출해 주는 doc 필터가 필요하다. 마찮가지고 html문서도 그대로 색인시 html tag도 색인이 되어질 수 있으므로 html parser를 통해 필터링을 걸쳐 text정보만을 색인하게 된다. 이런식으로 text-based 검색엔진에서는 다양한 문서들에 대한 검색 서비스를 하고자 할 경우 각각의 문서 포맷에 맞는 개별적인 필터가 있어야만 한다.
랭커
검색 결과에 대한 순위를 매겨주는 기능이다. 검색 모델 및 랭킹 알고리즘에 맞게 구성되어지는 것이 보통이며 검색기의 일 부분으로 동작하게 된다. 주된 기능은 질의에 대한 각 문서들의 연관성을 수치화 하는 기능과 결과 정렬 기능이다. 실제 검색 속도에 가장 영향을 많이 주는 부분은 포스팅화일을 스토리지에서 메모리로 로딩하는 과정과 이 랭커에서 랭킹을 하는 두 부분이다.
질의분석기
사용자가 입력한 비 정규적인 질의를 파싱하여 검색에 적합하도록 정의된 정규화된 질의 문법으로 변환하는 기능이다. 입력된 질의는 대다수 내부적인 연산에 적합하게 구성되지 않는다. 이를 최대한 연산하기에 적절한 문법으로 변환하기 위한 필수 과정이다. 분석기는 때때로 형태소분석기나 기타 토큰 분리기 등을 포함하고 있어서 질의중에 꼭 필요한 키워드만 추출할 수 있도록 하기도 한다. 논리연산을 위해서 정의된 기호들을 연산자로 대치하기도 하고 질의에 대한 파스트리를 생성하기도 한다. 또한 주어진 컬렉션들 중에 어디에서 검색할 것인가를 명확히 표현해 주기도 한다.
파서
문자열 파서가 대부분이다. 경우에 따라서는 오토마타, 형태소분석기, 기타 토큰분리기 등을 사용한다. 색인기에서 색인어 추출을 위해 사용하기도 하며 검색기에 포함되어 있는 질의 분석기에서 질의를 분석하기 위해서 사용하기도 한다.
오토마타
유한오토마타를 사용하여 주어진 질의나 문서를 파싱하기 위해 사용한다.
컬렉션
검색 대상이 되는 집합을 말한다. 웹문서 검색일 경우 로봇이 수집한 HTML문서등이 하나의 컬렉션이 될 수 있다. 다양한 조건 및 여러 필드 검색을 지원하기 위해 컬렉션은 여러개로 나뉘어 질 수 있으며 웹문서하나도 여러개의 컬렉션으로 쪼개어 구성시킬 수 있다. 예를 들어 www.yahoo.co.kr 하위의 문서 중에 '꾸러기'라는 키워드로 검색하고자 할 경우, 웹문서들의 text부분을 모아서 하나의 컬렉션으로 구성하고, url부분을 모아서 다른 하나의 컬렉션으로 구성한 후 두개의 컬렉션중에 url은 url 컬렉션에서 찾고, 키워드는 text 컬렉션에서 찾은 후 두 결과를 and 연산을 통해 최종 결과를 산출한다. 이런식으로 데이타 성격이 다른 여러개의 집합들을 개별 컬렉션으로 구성하여 다양한 연산을 통해 복잡하면서도 잘 정의된 검색 결과를 계산할 수 있다.
DB
색인기가 생성한 색인 정보들을 저장할 DB를 말한다. 일반적인 상용 RDB를 사용하여 색인 DB를 구성할 수도 있으며 속도를 위해 파일 시스템을 제어하여 별도의 화일시스템으로 구성할 수도 있다. 컬렉션의 크기와 종류가 작을 경우는 상용 RDB를 사용하는 것이 사용하기에 아주 편리하다. 그러나 대용량 컬렉션일 경우는 파일 시스템을 직접 제어하는 것이 성능상 더 효율적일 경우가 많다. 검색엔진 전용으로 연구되어진 DB들이 몇몇 대학의 연구소를 중심으로 발표되어 있긴 하나 상용으로 적용된 사례가 많지 않다. 버클리 DB를 사용하여 동적 색인을 가능케 한 검색엔진들이 발표되어 있긴 하나 성능이 만족할 만 한지는 의문이다.
프리뷰어
검색된 페이지를 직접 방문하지 않고 검색엔진 자체에 저장되어 있는 문서를 사용하여 엔진 자체에서 미리보기 형식으로 보여주는 기능이다. 웹로봇이 문서를 수집할 당시에 살아 있던 링크라 하더라도 검색하는 시점에서는 이미 삭제되어 버린 문서일 수도 있다. 또는 속도가 느려서 실제 페이지를 방문할 때 브라우져를 통해 보기가 만만찮을 경우도 있다. 이런 경우 엔진에서 저장하고 있는 데이타를 사용하여 미리보기 형식으로 데이타를 보여주어 사용자의 편의를 도모할 수 있다.
중복제거기
최근 검색엔진들의 비약적인 발전으로 인해 검색 결과에서 중복되는 문서들이 나타나는 경우는 드물다. 실제 엔진 내부에는 중복된 내용을 가지는 문서들이 상당수 존재하는 것이 일반적인 현상이며, 이러한 중복 문서를 제거하기 위해 별도의 중복 제거기가 필요하다. 크게 3부분에서 중복문서를 제거시킬 수 있으며, 첫째로 로봇에서 문서를 수집하는 시점 또는 수집후에 모든 문서들을 비교해서 중복 문서를 제거할 수 있다. 둘째로 색인 시점에서 색인과 동시에 중복되는 문서를 제거시킬 수 있으며, 마지막으로 검색한 결과에 대해서 검색기에서 검사하여 결과를 조절하는 방식으로 제거시킬 수 있다. 구글이나 네이버에서는 마지막 방법까지 사용하여 중복문서를 제거한다.
이러한 방식 때문에 실제 검색 결과와 마지막에 보여지는 개수에 차이가 보여지기도 한다.
역화일
파일 시스템 또는 데이터베이스 등과 같이 대량의 자료가 관리되는 곳에서 보다 빠르게 자료를 검색하기 위하여 각각의 자료에 대한 색인이 구성되어 있는 파일을 지칭하는 용어. 이러한 파일에는 각각의 데이터 레코드에 대한 키 값과 이러한 키 값에 의하여 지칭되는 레코드의 위치가 하나의 쌍을 이루고 있다. 키워드를 빠르게 찾기 위해 B+tree나 B-tree, trie, 페트리샤트리 등을 사용한다.
* 검색엔진의 역사
우리가 많이 사용하고 있는 검색엔진들은 과연 얼마나 오래 된 것들일까? 최근의 폭발적인
인터넷 사용자 증가와 활성화된 많은 검색엔진 제공 사이트들로 인해 이제는 검색엔진이란
단어 자체를 모르는 사람들은 거의 없을 것이다. 그러나 검색엔진 자체의 역사에 대해
관심있게 살펴본 사람은 아마도 관련업계 사람들이나 직접적인 개발자 정도가 아닐까 한다.
요즘 한참 인기가 있는 지식검색들을 유심히 지켜보면 현 시점의 대다수 사용자들이 무엇을
원하고 있는지, 요즘의 추세는 어떤지를 간접적으로나마 파악할 수 가 있다. 이는 대량의
사용자 지식이 축적된 결과로 인한 많은 부산물 중의 하나이다. 지식검색에 대한 얘기를 하려
하는 것은 아니고... ^_^; 이러한 지식검색에서 조차도 검색엔진 자체의 역사에 대한 질문은
찾아보기 힘든다. 대부분 인기있는 검색엔진의 역사정도만을 질문하는 정도이다.
일반 사용자들에게는 사실 이러한 문제가 별로 관심사가 아니기 때문에 이런 현상이 나타
나는 것으로 보여진다. 하지만 검색엔진의 개발자들이라면 한번쯤은 이 부분에 대한 자료를
찾아본 적은 있을 것이다.
각설하고..
의외로 검색엔진의 역사는 상당히 길다고 볼 수 있다. 문헌정보학 적인 측면에서 본다면
컴퓨터가 출현하기 훨씬 이전부터 기본적인 개념들은 있었던 것으로 보여진다. 전산학적인
측면에서 보면 컴퓨터가 출현하면서 바로 정보검색의 역사도 시작했다고 봐도 과언은 아닐
것이다.
정보검색(IR, Information Retrieval)이란 말은 처음 1945년 Vannervar Bush의 논문에서
처음 제시되었다. 그 후 1950년대 초반 1세대 컴퓨터의 등장 시기에 미국에서 사용되었다.
이 때부터 본격적인 정보검색의 역사가 시작된다고 보면 무리가 없을 것이다.
박민우님께서 정리한 내용에 의하면 정보검색의 역사를 요람기, 유년기, 성년기, 성숙기의
4단계로 구분해 잘 정리해 놓았다. 아쉽게도 현재의 시기에 대한 단계를 설정하지 않은 것이
있긴 하지만..
각 시기별 세부 내용을 살펴보자.
1. 요람기(1945~1955)
정보검색이란 용어가 처음 사용되었다. 이 때를 검색엔진의 태동기라 말할 수 있으며
이 때에 이미 기계번역에 대한 최초의 제안이 제시되었다. 중요한 인물들로는 1949년도의
Warren Weaver, Andrew D.Booth등이 있으며, 이때에 정보검색과 기계번역에 대한 모든
아이디어가 제시되었다. 이러한 이론들은 계속 발전되어가다 60년대에 이르러서 시스템으로
구축되는 계기가 되었다.
2. 유년기(1960년대)
위대한 경험의 시대라고 표현이 되어 있는 것만으로도 이 시대가 상당히 다양한 연구 및
개발이 있었다는 것을 미루어 짐작할 수 있을 것이다. 현재 거론되고 있는 대부분의 검색
모델들이 이 시대에 정립되었다. 또한 대용량 정보검색 시스템의 초기 모델이 제시되었다.
Free-Text Indexing 기법이 보편화 되었으며, 정보검색 시스템의 평가 기준이 완성되었다.
1966년 Cyril Cleverdon은 재현율, 정확율 기준을 마련하였다. 1968년 Gerard Salton은
다국어 검색기법을 제시하였으며, Relevance feedback 등의 신기술 검색기법이 태동되었다.
또한 BRS라는 대용량 정보검색 시스템이 구현되었다.
3. 성년기(1970년대)
전자문서의 시대로 표현될 수 있다. 이 기간에 워드프로세서의 등장으로 인해 처리해야 할
문서의 수와 양이 비약적으로 증가되었다. 하드웨어적으로는 디스크드라이브가 처음 발표
되었으며(당시 1M당 2000달러정도) 이러한 제반 요건들은 대용량 검색시스템들의 상용화를
자연스럽게 이끌게 되었다. 이때 상용화된 검색시스템으로 Dialog, Orbit, BRS등이 있다.
또한 세계 최대 규모의 도서관 네트웍인 OCLC의 등장은 따로 말을 하지 않아도 익히 알고들
있을 것이다. 최기 OCLC는 64개국의 26000개의 도서관 정보를 제공하였다.
이 시기에 데이타데이타베이스 시스템이 처음 등장하였으며, 이러한 제품들은 계층모델과
네트웍 모델을 기반으로 하였었다. 후에 이러한 데이타베이스들은 관계형, 개체형등으로
발전을 거듭하게 된다.
데이타베이스와 검색엔진의 차이는 다음과 같이 요약할 수 있다.
데이타베이스 : Data 관점, 관리중심, 결정구조, SQL->MIS로 발전
검색엔진 : Information 관점, 검색 중심, 비정형 구조, 자유검색
초기의 정보검색은 인공지능의 한 분야로 인식되어져 오다가 이 시기에 인공지능 분야에서
분리되었다. 이시기에 AI에 대한 무용론이 대두되고 IR분야는 고속성장을 맞게 된다. 그러나
최근에는 다시 AI와 IR이 접목을 시도하는 경향이 있다. 그리고 단어(워드)에 대한 처리방식
접근이 보편화 되었다.
4. 성숙기(1980년대)
본격적인 전문 검색엔진이 등장하였다. 당시 시대적 상황으로는 컴퓨터의 성능이 비약적으로
향상되었으며, 저렴한 가격대, CD-ROM의 등장등으로 하드웨어적인 요건이 대폭 향상되었으며
원문 검색에 대한 사용자의 요구가 점점 증대하게 되었다. 이러한 상황에서 전문 검색엔진의
등장은 당연한 결과이며, 도서관 위주의 검색 기술이 지속적으로 발달하였다.
5. 그후(1990년대~현재)
시대적인 구분으로는 1945~1989년까지를 구분해 보았다. IT 기술적인 구분으로는 www의 출현
전과 후(1990년 초반)로 구분하기도 한다. WWW의 출현은 정보검색 측면에서는 새로운 시대를
여는 계기가 되었으며 이로 인해 정보검색 시스템들이 일반 사용자들에 아주 쉽고 빠르게
접근할 수 있게 되었다.
이 시대에 현재 사용하고 있는 대부분의 상용 검색엔진들이 출현하였으며 WWW를 통한 거대
검색포탈들이 속속 생겨나게 되었다.
OS: Microsoft Windows 2000 5.00.2195 Service Pack 3
MySQL: 4.0.7-gamma-nt
CPU: x86 Family 6 Model 8 Stepping 10
RAM: 512MB
작성자: 강명규(kang@dbakorea.pe.kr)
FULLTEXT search
fulltext검색은 쉬운 말로 자연어 검색(natural language search)이다.
FULLTEXT 인덱스는 MyISAM table type을 가진 테이블에서만 지원되고,
CHAR, VARCHAR, TEXT column type을 가진 컬럼에서만 생성될 수 있다.
char는 언급되어 있으나, 직접 확인하진 못했으므로 함 해보기 바란다.
Feature Version
Basic FULLTEXT searching 3.23.23
Configurable parameters 4.0.0
Boolean searches 4.0.1
Phrase searches 4.0.2
Server variables
길이가 ft_min_word_len ~ ft_max_word_len 의 범위에 있는 것들만 검색 대상이 됨.
ft_min_word_len : (디폴트:4)
ft_max_word_len : (디폴트:254)
서버변수 변경
1. C:\WINNT\my.ini변경후 서버 restart(UNIX: /etc/my.cnf)
[mysqld]
set-variable = ft_min_word_len=5
2. 기존 fulltext인덱스 변경
REPAIR TABLE 테이블명 USE_FRM;
FULLTEXT 인덱스는 테이블 생성후, 대량의 데이터를 로드한 다음에 생성해주는 것이 좋다.
이 방식은 fulltext인덱스만이 아닌 다른 인덱스에도 동일하게 적용된다.
CREATE TABLE articles (
id INT UNSIGNED AUTO_INCREMENT NOT NULL PRIMARY KEY,
title VARCHAR(200),
body TEXT,
FULLTEXT (title,body)
);
INSERT INTO articles VALUES
(0,'MySQL Tutorial', 'DBMS stands for DataBase ...'),
(0,'How To Use MySQL Efficiently', 'After you went through a ...'),
(0,'Optimising MySQL','In this tutorial we will show ...'),
(0,'1001 MySQL Tricks','1. Never run mysqld as root. 2. ...'),
(0,'MySQL vs. YourSQL', 'In the following database comparison ...'),
(0,'MySQL Security', 'When configured properly, MySQL ...');
mysql> select * from articles;
+----+------------------------------+------------------------------------------+
| id | title | body |
+----+------------------------------+------------------------------------------+
| 1 | MySQL Tutorial | DBMS stands for DataBase ... |
| 2 | How To Use MySQL Efficiently | After you went through a ... |
| 3 | Optimising MySQL | In this tutorial we will show ... |
| 4 | 1001 MySQL Tricks | 1. Never run mysqld as root. 2. ... |
| 5 | MySQL vs. YourSQL | In the following database comparison ... |
| 6 | MySQL Security | When configured properly, MySQL ... |
+----+------------------------------+------------------------------------------+
6 rows in set (0.00 sec)
match에는 검색될 컬럼(들)을 적고, against에는 검색할 단어를 적는다.
match에 컬럼순서는 상관없고, against는 대소문자 관계없이 검색된다.
mysql> SELECT * FROM articles WHERE MATCH (title,body) AGAINST ('database');
+----+-------------------+------------------------------------------+
| id | title | body |
+----+-------------------+------------------------------------------+
| 5 | MySQL vs. YourSQL | In the following database comparison ... |
| 1 | MySQL Tutorial | DBMS stands for DataBase ... |
+----+-------------------+------------------------------------------+
2 rows in set (0.00 sec)
검색된 결과는 Relevance values 라는 값에 의해 정렬되는데 이것은 검색결과의 정확도를 의미한다고 보면 되겠다.
0의 값은 아무런 관련이 없다는 뜻이고, 계산기준은 다음과 같다.
row내에 단어의 수, 해당 row내의 unique한 단어수, collection내의 총단어수, 특정 단어를 포함하는 문서(rows)의 수.
번역하긴 했는데 정확히 무슨 말이라는 건지.. --;
위의 결과에 대해 Relevance values를 알아보면 다음과 같다.
id=5가 가장 큰 값이므로, 위에서 제일 처음에 표시 되었음을 알 수 있다. 0은 관련없는 것들이므로 검색결과에서
제외되었음도 봐두자.
mysql> SELECT id, MATCH (title,body) AGAINST ('database') from articles;
+----+-----------------------------------------+
| id | MATCH (title,body) AGAINST ('database') |
+----+-----------------------------------------+
| 1 | 0.65545834044456 |
| 2 | 0 |
| 3 | 0 |
| 4 | 0 |
| 5 | 0.66266459031789 |
| 6 | 0 |
+----+-----------------------------------------+
6 rows in set (0.00 sec)
검색에 사용되는 단어는 문자,숫자,', _ 이다.
검색에서 제외되는 단어(stopword)는 너무 짧은 단어(디폴트로 3단어이하, 서버변수 ft_min_word_len에서 지정)
이거나, stopword list에 포함된 단어들(the,..)이다.
자주 사용되는 단어나 문법적인 관계에 쓰이는 단어는 검색시 비중이 낮고,
드물게 사용되는 단어(용어, 학술어, ...)는 높은 비중을 가진다. 이 비중(weight)은 Relevance계산시 이용된다.
mysql> SELECT * FROM articles WHERE MATCH (title,body) AGAINST ('MySQL');
Empty set (0.00 sec)
분명히 mysql이라는 단어가 존재함에도 불구하고, 위의 질의는 아무런 결과를 리턴하지 않는다.
이유는 MySQL이라는 단어가 너무 많이 존재하기 때문이다. 검색어가 rows에 반이 넘게 존재하면,
stopword로 취급된다.(50% threshold)
4.0.1이상부터는 in boolean mode 를 사용하면 50% threshold가 적용되지 않으며 다음과 같이 검색결과를 얻을 수 있다.
boolean mode에서는 FULLTEXT인덱스가 걸린 컬럼이 아니더라도 검색할 수 있다. 하지만 느려진다.
또한, 검색결과는 Relevance values에 의한 정렬이 이루어지지 않는다.
mysql> SELECT * FROM articles WHERE MATCH (title,body) AGAINST ('MySQL' IN BOOLEAN MODE);
+----+------------------------------+------------------------------------------+
| id | title | body |
+----+------------------------------+------------------------------------------+
| 1 | MySQL Tutorial | DBMS stands for DataBase ... |
| 2 | How To Use MySQL Efficiently | After you went through a ... |
| 3 | Optimising MySQL | In this tutorial we will show ... |
| 4 | 1001 MySQL Tricks | 1. Never run mysqld as root. 2. ... |
| 5 | MySQL vs. YourSQL | In the following database comparison ... |
| 6 | MySQL Security | When configured properly, MySQL ... |
+----+------------------------------+------------------------------------------+
6 rows in set (0.00 sec)
boolean mode에서는, 검색에서 제외할 단어는 -로, 검색에 포함될 단어는 +로 지정할 수도 있다.
mysql> SELECT * FROM articles WHERE MATCH (title,body) AGAINST ('+mysql -tutorial' in boolean mode);
+----+------------------------------+------------------------------------------+
| id | title | body |
+----+------------------------------+------------------------------------------+
| 2 | How To Use MySQL Efficiently | After you went through a ... |
| 4 | 1001 MySQL Tricks | 1. Never run mysqld as root. 2. ... |
| 5 | MySQL vs. YourSQL | In the following database comparison ... |
| 6 | MySQL Security | When configured properly, MySQL ... |
+----+------------------------------+------------------------------------------+
4 rows in set (0.00 sec)
+,- 와 더불어 다음의 operator도 사용할 수 있다.
+ : 검색시 반드시 포함될 단어
- : 검색시 제외될 단어
< : 단어의 검색능력에 대한 기여도(contribution)를 감소시킴
> : 단어의 검색능력에 대한 기여도(contribution)를 감소시킴
(): 검색 단어들을 subexpressions으로 그룹화시킴
~ : negative 오퍼레이터로 작용. 검색능력에 대한 기여도를 음수로 만듬.
-와 유사하지만 제외되지는 않음. noise word를 의미할때 사용될 수 있다.
* : 일반적인 유닉스 쉘상의 기능과 동일(truncation operator)
" : ""로 쌓인 순서대로 있는 것만 검색됨.
예)
apple banana
find rows that contain at least one of these words.
+apple +juice
... both words.
+apple macintosh
... word ``apple'', but rank it higher if it also contain ``macintosh''.
+apple -macintosh
... word ``apple'' but not ``macintosh''.
+apple +(>pie ... ``apple'' and ``pie'', or ``apple'' and ``strudel'' (in any order), but rank ``apple pie'' higher than ``apple strudel''.
apple*
... ``apple'', ``apples'', ``applesauce'', and ``applet''.
"some words"
... ``some words of wisdom'', but not ``some noise words''.
웹 로봇을 개발하자!
1. 개요
검색엔진에서 말하는 로봇이란 다음과 같이 정의할 수 있다.
컴퓨터를 사용하여 주기적, 비 주기적으로 데이타를 능동적으로 수집하는 자동화된 프로그램.
여기서 "수많은 정보"들은 단순한 HTML문서가 될 수도 있고, XML, 워드문서, 이미지, 멀티미디어 정보, DB 데이타등도 포함된다. "주기적, 비주기적"이란 말은 로봇이 특정 대상을 지속적으로 감시하면서 데이타를 수집할 수도 있고, 그렇지 않을 수도 있다는 것이다. "능동적으로 수집"한다는 의미는 어떤 정보로부터 새로운 정보를 얻어내어 연관된 다른 정보를 스스로 찾아다닌다는 것을 말한다.
한가지 예를 들면, 매체사로부터 뉴스기사를 전송받아 DB에 저장하는 데몬이 있다고 하자. 이러한 녀석도 데이타를 수집하기 위한 장치임에 분명하나 로봇이라 부르지 않는다. 이유는 매체로부터 전송된 데이타를 수동적으로 받는 입장이며, 새롭게 받은 데이타에서 추가적인 정보를 유추해 내어 새로운 정보를 찾아내지도 않는다. 물론 로봇도 새로운 정보를 찾지 않고 이미 입력된 몇몇의 시드만을 사용하여 데이타를 수집하도록 할 수 있다. 그렇더라도 수집의 주체인 로봇 자체가 능동적으로 해당 데이타를 찾아가서 전송받게 된다는 것이 위의 예와는 차이라 볼 수 있다.
IE와 같은 웹브라우져도 넓은 의미에서는 로봇이라 볼 수 있다. 보통은 agent라는 용어를 쓰기도 하지만 브라우져 또한 로봇과 다를게 없다.
위 의미에 맞춰 생각해보면 이해할 수 있으리라 본다.
위 의미를 좀더 확장하여 웹로봇을 정의하면 다음과 같이 말할 수 있겠다.
인터넷상에 존재하는 수많은 정보들을 주기적 또는 비 주기적으로 수집하는 자동화된 프로그램.
위 정의의 의미는 로봇은 로봇인데 특정한 DB에 직접 접속하여 정보를 수집하는 것이 아니라 인터넷을 사용하여 인터넷 상에 존재하는 정보를 수집하는 로봇을 웹로봇이라고 보겠다는 것이다.
얼마전 필자는 로봇과 크롤러, 에이전트의 차이점에 대한 질문을 받은 적이 있다. 솔직히 세분하자면 용어를 사용한 사람들의 말을 직접 들어 봐야 할 것이다. 그러나 일반적인 통념상 로봇, 크롤러, 에이전트, 게더러 등등은 동일한 말이라 봐도 무방할 것이다. 단지 세분화 한다면 인터넷의 데이타를 수집하는 것은 웹로봇, 웹크롤러 등등으로 말하고 DB정보를 수집하는 것을 DB 로봇, DB 크롤러등으로 명명하는 것이 보통이다.
* 다음은 "효율적인 웹 로봇의 설계 및 구현에 관한 연구" 1997. 심해청 학위논문에서 발취한 내용이다. 웹로봇의 필요성에 대한 간략한 설명이라고 보면 되겠다.
하루가 다르게 변하는 정보화 사회에서 인터넷이라는 거대한 공간 속에서 노아의 홍수와 같은 엄청난 정보가 넘쳐나고 있다. 이러한 정보의 홍수 속에서 사용자가 원하는 정보를 찾는다는 것은 모래사장에서 바늘 찾기 보다 더 어렵다. 검색도구는 이렇게 찾기 힘든 정보를 쉽게 찾을 수 있도록 도와주는데 큰 도움을 주고 있으며 그 위치는 하루가 다르게 높아가고 있다. 그래서 인터넷 상에는 많은 검색 도구들이 등장하고 있다. 이러한 검색 도구들은 수동, 또는 웹로봇을 이용하여 자동으로 정보를 수집하는데 지금은 거의 웹 로봇을 사용하고 있다.
그러나 대부분 상업적인 목적으로 인하여 그 기술이나 특징에 대해 공개되지 않아 검색 도구의 특징을 보고 어림잡을 뿐이다. 검색 도구들은 보통 정보를 수집하기 위한 웹 로봇(Web Robot, Robot agent)과 수집되 자료에서 정보를 검색하는 검색엔진 부로 이루어져 있다.
검색엔진부는 정보검색이라는 분야로서 많은 연구가 이루어져 있으나 웹로봇은 그다지 맣은 연구가 이루어지지 않았다. 또한 이러한 웹로봇은 쉽게 작성할 수 있다는 이유로 아주 작은 부분으로 취급되어 지기도 한다. 그러나 검색엔진부는 수집된 자료가 있어야만 수행되어질 수 있으며 수집된 자료가 빈약할 경우 당연히 서비스의 질이 떨어지게 된다. 그러므로 웹 로봇의 위치는 아주 중요한 위치에 있는 것이다.
* 웹로봇의 구성요소
웹로봇에는 HTML 파서, HTTP 프로토콜, 소켓, 쓰래드, 대용량 데이타 저장 구조 등이 필요하다.
HTML 파서는 html안에서 새로운 url을 추출하여 반복적인 데이타 수집을 하기 위해 필요하다. 웹로봇용으로 쉽게 파서를 구현하려면 strstr함수를 사용하여 href만 찾아내어 문자열을 짤라내어 버리면 된다.
html 구조 자체가 간단하다 하더라도 초보자가 html 파서를 제작하는 것은 조금 버거운 일일 수 있다. 그래서 많은 프로그래머들이 공개된 소스나 모듈들을 많이 사용하고 있다.
그러나 이 강의에서는 html 파서를 직접 제작할 것이다. 누누히 강조하지만 원리를 모르는 상태에서 있는 모듈을 쓰기만 하는 프로그래머는 프로그래머가 아니다. 단지 코더일 뿐이다.
HTTP 프로토콜은 웹로봇 자체가 인터넷의 정보를 수집하는 기능이기 때문에 반드시 필요한 것이다. 이 프로토콜도 아주 잘 만들어진 오픈소스나 모듈들이 많이 있다. 그러나 만들것이다. ^_^;
소켓은 HTTP프로토콜 자체가 tcp/ip기반으로 동작하는 프로토콜이므로 반드시 필요한 부분이다. tcp/ip에 대해서는 본 강의 범위를 넘어서게 되므로 관련 책자를 참고하기 바란다. 이 강의에서는 소켓라이브러의 사용법과 멀티 쓰래딩 시의 타임아웃 처리에 대해 집중적으로 다룰 것이다.
쓰래드는 고속 처리를 위해서는 반드시 사용해야 할 구조이다. 웹로봇의 특성상 수천만건의 데이타를 빠른 시일안에 수집하기 위해서는 단일 쓰래드로는 무리가 있다. 만일 단일 쓰래드로 로봇을 만든다면 하루종일 데이타를 수집해도 10000~30000개의 문서를 수집하기도 힘들 것이다.
대용량 데이타 저장구조는 소량의 데이타를 수집할 목적의 로봇이라면 필요치 않다. 그러나 웹로봇의 경우는 앞서말한 모든 기술적 이슈보다도 오히려 큰 문제로 대두된다. 웹로봇 수행시간에서 가장 많은 시간을 소모하는 것이 url을 저장하고 관리하는 부분이다.
보통 천만개의 문서를 수집한다면 처리해야 할 url의 개수는 적개는 수억에서 많게는 수십, 수백억개의 url이 될 수 있다. 이는 개수 뿐만이 아니라 용량에도 아주 많은 영향을 받게 된다.
참고로 대량의 데이타를 처리할 경우는 DB를 사용하지 않기를 권한다.
조금 복잡해 보이기는 하지만 차근차근 훓어 보면 그리 복잡한 구조가 아닙니다.
왼쫀 아래에 보면 dic(사전)들이 있습니다. 이것은 형태소분석기에서 사용하는 사전으로 색인시에 사용했던 사전들과 동일한 구조로 되어 있는 것이 바람직합니다. 물론 서비스 구성에 따라 형태소분석기 세팅 자체를 서로 다르게 할 수도 있습니다. 바로 옆에 있는 시소러스 사전은 별도로 동작하게 할 수도 있으나 대부분 형태소 분석기에서 사전과 같이 처리하는 것이 일반적인 예입니다. 이런 시소러스사전류는 검색시 입력되는 질의를 확장한다거나 할 경우 많이 사용됩니다.
여기서 질의를 확장한다라는 의미는 뭘까요? 쇼핑몰 검색을 예로 봅시다. 어떤 구매자가 나이키의 조깅화를 구입하려 하는데 갑자기 조깅화란 단어가 떠오르지 않는다면 어떤식으로 질의를 입력 할까요? 보통 나이키, 아니면 운동화 정도로 우선 검색을 할 것입니다. 이때 운동화라는 개념을 좀더 확장하여 조깅화, 런닝화, 축구화, 등등의 키워드들을 추가하여 검색하게 된다면 보다 쉽게 최종 결과에 도달할 수 있을 것입니다. 단, 부적절한 질의확장은 검색성능이나 결과 개수에 악영향을 미칠 수 있으므로 많은 연구가 필요할 것입니다. 당연히 시소러스 사전 자체도 서비스에 맞게 잘 구성되어 있어야 합니다.
다음으로.. 바로옆에 있는 index db는 색인기가 만들어 놓은 색인 정보들입니다. 이전 강좌에서 설명했던 내용이니 확인해 보시면 될 것이구요.. 다른것 하나는 term cluster dic인데 검색 엔진의 기본기능이 아닌 관계로 넘어가겠습니다. ^_^;
사용자가 검색질의 엔진에 던지게 되면 방식은 여러가지가 있습니다. 물론 서비스를 구성하는 것에 따라 방법이 달라지게 되구요. 많이 쓰이는 것들은 인터넷 검색엔진들이 되겠지요. 보통 CGI를 통해 질의를 받아서 CGI가 엔진으로 전달하고 결과를 받게 됩니다.
엔진에서 클라이언트 API를 제공하거 어떤 프로토콜을 제공해 준다면 윈도용 어플리케이션에서도 결과를 받아볼 수 있겠지요. 어차피 소켓통신을 하는 데몬이기에 프로토콜만 알게 되면 어떠한 응용 프로그램에서도 엔진과 바로 맞붙어서 데이타를 주고 받을 수 있습니다.(당연하겠지요?) 그래서 이런 경우에는 client api, activeX 콘트롤, 일반 APPs, 관리도구 등에서 다양하게 접속하여 엔진의 결과를 받을 수 있습니다.
그러나 검색포탈이나 SI업체들의 검색엔진은 프로토콜을 공개하지 않습니다. 이유는 당연하겠지요. 네이버가 검색 프로토콜을 공개한다면 하루에도 수십번 해킹을 당할 수 있을 것입니다. 하지만 검색엔진을 직접 개발하는 한 그룹내에서는 이런한 프로토콜을 공개하는 것이 개발시 도움이 될 수 있습니다.
아무튼, 클라이언트에서 입력된 검색질의는 엔진에서 받아들이게 되면 맨 처음 질의분석기(Query Analayzer)라는 녀석이 받아들입니다. 그래서 유효한 검색질의인지, 유효하다면 엔진이 이해할 수 있는 방식으로 검색질의를 파싱한 후 어떤식으로 검색을 수행할지, 어떤 필드에서 검색을 할지, 키워드를 확장할지 등등을 결정하게 됩니다.
결정이 되면 바로 연산기(calculator)로 파싱된 질의를 전달하여 질의에 대한 연산을 수행합니다. 이때 연산기는 자연어처리모듈, 논리연산 처리모듈, 숫자처리 모듈들을 내장하여 검색옵션에 맞게 결과를 계산하게 됩니다.
연산기가 계산대상이 되는 데이타를 먼저 로딩하기 위해 파싱된 텀별로 index DB의 데이타를 읽기 위해 Retriever에게 질의를 던지게 되면 Retriever는 필요한 정보들을 index DB에서 로딩하여 연산기로 전달해 줍니다.
연산기가 모든 연산을 마치게 되면 결과는 순위화된 문서들의 일련번호와 문서들의 랭킹점수등이 남게 됩니다. 이러한 내용들을 Stream Generator로 전달하게되고 Stream Generator는 최종 사용자가 확인할 수 있는 결과(제목, 본문, URL, 기타 부가정보등등)를 만들어서 다시 질의분석기 에게 돌려주게 됩니다.
그러면 질의분석기는 정해진 프로토콜에 맞게 Stream을 정리하여 클라이언트에 전달하게 되고 최종 검색결과를 클라이언트에서 마음대로 조작한 후 보여지게 됩니다.
그림에서 오른쪽에 Summary Server와 Log Server가 있습니다. 후자는 일반검색엔진과는 별 상관이 없는 부분입니다. Summary Server는 보통 검색엔진 내에 요약정보를 따로 두는 경우가 많습니다. 그러나 대용량 데이타일 경우는 요약정보가 하나의 서버에 같이 존재하게 되면 Disk I/O문제도 발생할 수 있으며 여러가지 성능에 안좋은 영향을 미칠 수 있으므로 위와 같이 요약서버 자체를 분리하여 구성할 수도 있습니다.
이상 간단한 검색기 구조였습니다.
위부터 아래로 훑어 내려가면 되겠네요.
우선 색인 대상 데이타로 HTML, DB, W/P용 문서들, 기타 등등 Text-base의 모든 데이타는 색인 대상이 될 수 있습니다. 이러한 데이타를 검색엔진(특히 색인기)이 인지하려면 각각의 포맷을 알야아 할 것입니다. 그래야 필요한 정보를 추출할 수 있겠지요.
어제는 그러한 부분은 Dumper라고 간략히 말씀드렸읍니다. 이녀석을 오늘은 좀 다른말로 표현해보지요. 여기서는 Document Recognizer(문서 인식기)라고 표현하였습니다.
물론 인터넷 어디를 뒤져봐도 이런 용어를 찾기 쉽지 않을 거구요. ^^;
이녀석의 역할을 각각의 문서 포맷별로 필터를 가지고 있어서 해당 문서를 정확히 분석하여 F-TXT를 생성하는데 있습니다. 여기서 F-TXT는 검색엔진이 이해할 수 있는 형식화된 텍스트 문서입니다. 만일 색인기가 F-TXT형식으로 XML을 사용하겠다면 색인기는 XML파서만 있으면 되겠지요? 이런 경우라면 Document Recognizer는 각각의 문서들을 분석하여 XML로 재구성한 후 저장해 둘 것입니다.
일반적인 엔진들은 Document Recognizer를 필요에 의해서 간단한 프로그램을 작성하기도 합니다. F-TXT의 형식은 정해질 지라도 검색 대상 문서들의 포맷을 모두 지원하지 못하기 때문에 서비스를 구성할 때 간단한 프로그램으로 색인 대상 데이타를 F-TXT로 변환합니다. 결국 색인기는 F-TXT라는 형식만 인식하는 구조로 작성하고 Document Recognizer를 서비스 개발자가 직접 작성하게 하면 아주 유연한 엔진이 될 수 있을 것입니다.
다음은 F-TXT의 구성 예입니다.
DOCID : 1
TITLE : 정보검색시스템이란 무엇인가.
BODY : 정보검색이란... 어쩌구저쩌구.. 지화자 좋구나....
DATE : 20040520 130222
SIZE : 3428
URL :http://내도메인/data/ir.html
위 예는 간단한 예일 뿐입니다. 엔진 구성하는 사람의 마음이죠. ^^;
F-TXT가 만들어 지면 F-TXT 파서는 퍼블리슁이 필요할 경우 HTML Generator에게 파싱된 데이타를 전달하여 서비스 페이지를 만들게 됩니다. 또한 index Generator에게도 파싱된 데이타를 전달하여 실제 색인을 하도록 도와줍니다. 결국 핵심이 되는 것은 index Generator로서 이 녀석이 모든 색인DB를 생성하고 화일들을 관리하게 되지요.
Index Generator는 형태소분석기를 내장합니다. 물론 형태소 분석기는 여러가지 사전을 가지고 있어서 이런 사전정보와 경험정보, 규칙들을 사용하여 형태소 분석을 수행합니다. 형태소분석기를 사용하는 이유는 이전 강좌에서 간단히 말씀드렸던것 같네요.. 다시 말하자면 한국어 특성을 고려한 색인어를 추출하기 위함입니다. 물론 형태소분석기가 없더라도 색인어는 추출할 수 있습니다. 또한 어떤 경우는 형태소분석기가 오히려 색인어를 제대로 추출하지 못하는 경우도 있습니다. 그러나 여기서 보여드리는 색인구조는 국내의 엔진들이 일반적으로 사용하는 구조를 말씀드리는 것이구요. 아무튼.. 색인기는 형태소분석기를 통해 색인어를 추출하고 추출된 색인어를 기반으로 역화일을 생성합니다. 그리고 최종 요약정보도 생성하고 색인 과정을 마치게 됩니다. 이때 생성되는 화일들이 mapping table, term(keyword) trie, posting file, summary file 등입니다. 여기서 term trie와 posting화일을 역화일구조로 작성하게 됩니다.
위의 F-TXT 예를 기초로.. 검색서비스를 구성할 때 title에서만 검색, body에서만 검색, 날짜구간 검색 등의 검색서비스를 구축할 수 있을 것입니다. 이때 title, body, 날짜등은 별도의 역화일로 구성하면 의미상 명확할 뿐 아니라 검색효율을 상당히 높일 수 있습니다. 이유는 필터링을 할 필요가 없기 때문인데요.. 이렇게 구성하게 될 때 사용자가 title에서만 검색하는 명령을 내리게 되면 엔진에서는 title 필드에 해당하는 역화일을 찾아갈 수 있어야 합니다. 이런 부분을(title은 몇번째 역화일이다 라고 하는) 명시하는 것이 mapping table입니다.
term(keyword) trie는 index Generator가 생성한 모든 term(keyword)들을 트리형태로 표현하고 있는 색인 정보 입니다. 엔진마다 b-tree, b+ tree, trie, p tree등 다양한 방법을 사용합니다. 성격에 맞는 자료구조를 사용하면 되겠네요.. term trie는 posting file의 offset을 가지고 있어서 어떤 term이 나타난 문서들의 목록을 posting화일로 찾아가 구할 수 있도록 합니다.
posting화일은 문서들의 목록을 가지는 화일입니다. 단순히 문서번호를 나열해 둔 화일로서 term-trie에서 이 화일을 참조하여 문서목록을 가져옵니다. 여기서 문서목록이란 쉽게 생각하면 검색결과 목록이 될 수 있습니다.
summary file은 요약화일로서 검색결과를 화면에 보여줄 대 화면에 출력 가능한 데이타들을 모아둔 화일입니다. 쉽게 구성한다면 F-TXT를 그대로 사용해도 무방하겠지요.
그외의 모듈들은 사실 반드시 필요한 모듈들은 아닙니다. 필요에 의해 만들어 둘수도 있는 모듈들이라 설명은 하지 않겠습니다.
이상 간단한 색인기 구조였습니다.
검색 기법
다음은 BELKIN, NICHOLAS J.and CROFT, W. BRUCE,"Retrival Techniques," ARIST, 22(1987), PP. 109-145 에서 발취한 내용들이다.
BELKIN, NICHOLAS J.and CROFT, W. BRUCE등에 의해 제안된 검색기법의 분류방법
+-- Exact match
+-- Partial match --+-- Individual --+--- Structure-based
+-- Network +--- Feature-based
1. Exact match techniques(완전일치 기법)
검색된 도큐먼트들의 표현(representation)이 질문의 표현과 완전하게 일치된 것만 검색하는 방식이다. 초창기 대규모 검색시스템들에서 대부분 사용하던 방식이다. 이런 방법의 적용 예로는 불리언 검색, 전문검색, 스트링검색등이 있다. 단점으로는 다음과 같은 것들이 지적되어 왔다.
1) 이용자의 질의에 부분적으로 일치되는 경우의 텍스트들이 그 유용성에도 불구하고 검색에서 누락되는 예가 많다.
2) 검색된 텍스트들에 대한 적절성의 순위를 정하지 못한다.
3) 질문 및 텍스트 내에 존재하는 상호관련성이 있는 중요개념들을 전혀 고려하지 않는다.
4) 질문의 논리적 형성과정이 까다롭다.
5) 이용자의 질의 표현과 텍스트의 표현 비교가 오직 동일어휘로만 한정되어 있다.
이러한 단점에도 불구하고 초창기 많이 쓰이게 된 이유는 다음과 같다.
1) 검색기법을 변경하는데 드는 비용이 너무 많기 때문에 비경제적이다.
2) "exact match"기법이외의 대체기법들을 아직까지 대규모 시스템 환경에서 운영(테스트)해 본적이 없다.
3) 그러한 대체 기법들 조차도 실험적인 시스템 환경에서 테스트해 본 결과 그다지 만족스러운 것이 아니었다.
4) 이용자의 정보요구나 질의를 표현하는데 있어서 블리안 기법이 비교적 우수하다고 볼 수 있다.
그러나 현재 진보된 검색시스템들을 보게되면 위의 3,4번에 대한 이유가 무색해 진다. 현재 사용되고 있는 대부분의 상용 검색엔진들은 경험적으로나 이론적으로나 위의 3,4번에 대한 경우가 잘못된 생각임을 증명하고 있다.
2. Partial match techniques(부분일치 기법)
검색된 도큐먼트들의 표현이 질문의 표현과 부분적으로 일치된 경우의 것들로 함께 검색하는 방식이다. 여기서 Individual 방법은 이용자 질의를 각각의 개별 도큐먼트들과 비교 하는 방식을 말하며 Network 방법은 이용자 질의를 개별 도큐먼트들의 표현과 비교하 는 것이 아니라 개별 도큐먼트들 및 이와 관련된 다른 도큐먼트들과의 관계성 에 중점을 두어 작성되는 표현들과 비교한 검색기법이다. 이러한 네트웍 검색기법 에서는 개별 도큐먼트들의 내용에만 전적으로 의존하여 검색이 이루어지기 보 다는 이들과 관련을 맺고 있는 네트웍 기법으로는 cluster에 근거한 검색기법 과 Browsing기법 및 Spreading activation기법이 있다.
2.1 Individual, Feature-based
이용자의 질의 및 도큐먼트들의 표현방식 을 "색인어"와 같은 일련의 특징들로 표현하는 방식 --> 이러한 일련의 Features(특징)들은 각각 가중치로 표현될 수 있으며, text내에서 나오는 보다 복잡한 현상들을 표현하기에 적합하다. 이러한 feature-based기법에는 다시 Formal mode(여기에 해당되는 기법으로, Vector space model, 확률모델, fuzzy set model 등이 있다)과 Ad-hoc model이 있다.
이러한 범주의 기법들은 이용자의 질의를, 일련의 특징들 혹은 색인어들로 나타내는 도큐먼트 표현과 비교하는 방식을 취하고 있다. 이때의 도큐먼트 표현물들은 수작업이나 자동색인의 방식으로 도큐먼트의 텍스트 상으로 부터 추출되어지며, 마찬가지로 이용자 질의용어 역시 자연어로 표현된 질문으로 부터 직접 추출되거나, 색인어휘상의 용어를 사용하기도 한다.
여기에서 "feature"로 채택되는 요소들은, 단어나 어근, 구 혹은 개념들로서 이들과 관련된 가중치(weighte)값을 지니게 된다. 이러한 가중치들은, 그러한 각 요소들이 한 도큐먼트에 출현하는 빈도수나 혹은 이의 역 빈도수에 의하여 측정될 수 있다. 이러한 가중치의 표현방법이나 사용방법 및 계산방법 등은 각 시스템이 채택하고 있는 검색기법에 따라 다를 수가 있다.
(Formal) ==> Vector space model, probabilistic model, fuzzy set model.
2.1.1 Vector space model(벡터 공간 모델)
벡터공간 모델 상에서 각 도큐먼트들과 질문자들은 n차원 공간속의 벡터들로 취급되며, 이때 각 차원들은 색인용어들로 표현된다.
이 기법에 의한 검색절차는 다음과 같다.
1) 용어의 가중치는 정규화된 도큐먼트내의 빈도(tf)와 이의 역빈도수를 조합하여 계 산한다.
2) "낮은 식별치"(poor discriminatin value)의 값을 지닌 용어들은 시소러스내의 저 빈도용어들로 대치되며 구의 경우 고빈도 용어들로 대체된다.
3) 각 도큐먼트들은 이용자 질문에 대해서 그 유사성의 순위별로 출력되며, 이러한 과정은 "코사인"상관도(cosine correlation)에 의해 계산된다(벡터 공간내에서 이 용자의 질의에 가장 근접해 있는 도큐먼트들을 직관적으로 검색해 낸다)
2.1.2 Probabilistic model(확률모델)
확률모델은 지금까지의 검색기술에 새로운 방법론을 제시한 것으로서, 그 기술적 기반은 위의 벡터공간 모델로 부터 나온 것이다. 이 모델의 기본적인 목적은 이용자의 질의에 대한 적절성의 고확률순으로 도큐먼트의 순위를 정하여 검색하는 것이다. 즉, 각각의 도큐먼트를 구성하는 용어의 가중치가 "1"혹은 "0"의 값을 가질 수 있고 또한 이러한 각각의 용어들은 다른 용어들에 대해서 독립성을 지녔다고 가정하여 각 도큐먼트들의 순위를 정하는 방법이다.
2.1.3 Fuzzy set(퍼지 집합 이론)
이것은 겁색기법상으로 볼 때 블리언 질문기법과 도큐먼트 순위 매김기법을 통합한 기법이나 벡터공간 모델에 기초한 확장된 블리언 검색기법과 비교해 볼 때, 이러한 통합에는 한계가 있음이 드러났다.
2.1.4 Ad hoc(애드 혹 모델)
이 모델의 기본은 질의 용어군과 도큐먼트 용어군과의 겹침(over-lap)의 정도를 측정하여 그 유사성의 정도에 의하여 문헌을 검색하는 기법이다.
2.2 Individual, Structure-Based Techniques(개별적, 구조기반 기술)
이러한 범주에 드는 검색모델의 특징은 이용자 질의나 도큐먼트의 내용을, 색인어 등의 방식이 아닌 좀 더 복잡한 구조적 형태(structure)로 표현하여 이를 비교하는 방식이다. 이러한 검색기술은 특히, 특정한 전문주제분야에 적용되는 것이 적절하다.
2.2.1 Logic(논리모델)
도큐먼트의 텍스트가 담고있는 핵심적인 정보는 몇개의 짧은 문장으로 표현될 수 있으며, 이러한 문장들은 일정한 논리식으로 표현이 가능하다. 이와 마찬가지로 이용자의 질의도 논리식에 의한 표현이 가능하며, 이러한 질의는 논리식과 연계된 추론법칙에 의해서 그 해답이 가능하다.
예) 도큐먼트의 주제내용.
"If a company sells computer, it is financially viable".
==> 논리식으로 표현
==> (for all(x) (if (sells x computer) (viable x)))
이때 이용자의 질문(viable?)의 경우 "forward chaming"으로 해답이 가능하다. 이러한 모델의 가장 커다란 어려움은 각 텍스트들을 논리식으로 전환하는 작업인데, 현재는 수작업으로 하고 있다.
2.2.2 Graph(그래프 모델)
이 모델은 그래프 형태의 표현방법을 이용한 검색기법이다. 즉, 그래프 형태의 표현방법은 노드들과 이러한 노드들간의 edges(links)들로 이루어져 있는데, 이러한 노드들과 edges들은 주로 자연어 처리과정을 통해서 얻어지는 의미망(semantic nets), 혹은 의미프레임(semantic frames)으로 표현된다. 검색기법은 질의어의 그래프 구조와 도큐먼트의 그래프 구조를 서로 비교하여 그 유사성에 의거하여 문헌을 검색하거나 그 순위를 정하는 방식이다.
2.3 Network(네트웍 모델)
2.3.1 Cluster(클러스터 모델)
클러스터란, 내용이 유사한 일련의 도큐먼트군을 의미한다. 이것은 SMART프로젝트에 채택된 검색기법으로서, 클러스터 계층구조(CLUSTER HIERACHY)에 의한 것이었다.
* 클러스터 계층구조 --> 전체의 도큐먼트들을 몇개의 클러스터들로 나눈후에 각각의 클러스트들을 또다시 작은 클러스터들로 나누는 반복된 작업구조.
검색방법은 이용자의 질의내용을 최상위의 클러스터로 부터 최하위의 클러스터들 까지 하향식으로 비교하여 그 유사성의 큰 것부터 차례대로 검색해 내는 방식.
2.3.2 Browsing(브라우징 기법)
각각의 도큐먼트, 색인용어, 서지적 정보들을 시스템상에서 노드와 컨넥터들로 표현된 네트웍 구조로 만들 수 있다면, 이 때, 이용자는 이러한 네트웍을 훌터나가면서(Browsing) 필요한 도큐먼트들을 검색하는 기법.
이러한 Browsing기법에서 주목할 사항은 검색기법상 이용자 질문식의 형성(query formulation)에는 중점을 덜 두는 반면에, 이용자로 하여금 Browsing과정 중에서, 즉각적인 피드백을 강조하는 시스템이다.
I R 시스템의 예
노드(node) --> 도큐먼트, 색인어, 주제영역지식, 저자, 저널명.
링크(links) --> 색인정보, 시소러스 정보, 인접노드정보, 인용, 저자사항.
2.3.3 Spreding activation(스프래딩 액티베이션 모델)
위의 Browsing기법과 유사한 모델
네트웍 상에서 이용자의 질문에 해당되는, 어느 한 부분의 노드(색인어 혹은 도큐먼트) 및 이와 관련된 또 다른 노드들만 활성화(activate)시켜 가면서 최종 도큐먼트를 검색해 내는 방식. --> 예를들어 이용자의 질문에 의해서 어느 한 색인어가 선택되어 졌을 때, 이 색인어와 연결된 도큐먼트들 및 관련 색인들 역시 함께 활성화시키게 되는 방식.
2.4 Feedback Methods(피드백 기법)
이 기법은, 원래 "Feature-based"기법에서 발전되어 온 것으로서 현재는 모든 검색기법에서 응용되고 있다. 이 기법의 핵심은, 질의 용어에 대한 기준치를 검색도중에 수정해 가면서 최적의 도큐먼트들을 검색해 내는 방식이다. 이러한 가중치의 수정은, 적합한 것으로 판단된 도큐먼트들 속에 포함된 색인어들의 빈도수에 의해서 결정된다. 10-20%.
Relative Performance of Retrieval Techniques(검색기법의 상호성능 비교)
(Comparation Performance Studies)
1) 전반적으로 완전일치(exact match)기법보다는 부분일치(paricial-match)기법에 의 한 검색 결과가 더우수한 것으로 나타났다.
2) Feature-based기법 중에서는 특히 색인어에 대한 가중치 부여 기법을 사용한 확률 모델 기법이 가장 우수한 것으로 조사되었으며, 이때 용어의 가중치를 주는 방식 에 따라 그 검색성능이 크게 달라졌음이 밝혀졌다.
3) 클러스터 검색기법의 경우 "individual feature-based"검색에 버금가는 성능을 지녔으며, 특히 다른 검색기법들에 비해서, 높은 정확율을 가져온 것으로 나타났다. 따라서 클러스터 기법은 "individual feature-based"모델을 대체할 수 있는 좋은 기법이다.
정보검색시스템의 구성요소
1. 정보검색시스템이란?
정보 수요자가 필요하다고 예측되는 정보나 데이터를 미리 수집, 가공, 처리하여 찾기 쉬은 형태로 축적해 놓은 데이터 베이스로부터 요구에 적합한 정보를 신속하게 찾아내어 정보 요구자에게 제공하는 시스템을 말한다.
2. 배경학문
자료구조론 (Speed & Memory Trade-off)
데이터베이스론 (DB Indexing)
검색알고리즘
AI의 Search, NLP, Story understanding Algorithm
ES의 Inferencing
3. 구성요소
웹로봇
웹상에 존재하는 문서들을 가져오기 위해서 웹의 하이퍼텍스트 구조를 자동적으로 추적하여 참조되어지는 모든 문서들을 재귀적으로 검색하는 프로그램을 말한다. 여기서 '재귀적으로'라는 의미는 어떤 명시된 트래버스 알고리즘으로 유한하게 정의되어지는 것이 아님을 주목하라. 비록 로봇이 문서 선택을 위해 몇몇의 발견적인 학습법을 허락한다거나 방문하기 위한 문서의 순서를 정한다거나 하더라도 여전히 로봇이다.
일반적인 웹브라우저는 로봇이 아니다. 왜냐하면 그것들은 인간에 의해 수행되어진다. 그리조 참조되어지는 문서들을 자동적으로 수집하지 않는다.
크롤러(crawler), 스파이더(spider), 개더러(gatherer), 웸(worms), 안츠(ants) 등 다양한 이름으로 불리우지만 일반적인 명칭으로는 로봇이라 칭하는 비율이 높은듯 하다.
로봇을 얘기하면서 빼 놓을 수 없는 것이 로봇 배제 표준(robot exclusion standard)이다. 봇은 상당히 무책임한 프로그램이 될 수 있으며, 심한 경우는 웸바이러스와 같은 행동을 보일 수 있다. 필자의 경우 회사에서 로봇을 구동시키던 도중 국내의 유명 쇼핑몰의 DB를 죽여버린 경우가 있었다. 다행히 관용을 베풀어 주셔서 조용히 넘어갈 수 있었지만 돌이켜 보면 무척이나 위험한 상황이었다. 이처럼 잘못 구성된 로봇으로 인해 특정 사이트를 죽여버리거나 망 자체를 마비시킬 수도 있는 것이 로봇이다. 이런 로봇의 위험에서 자신의 웹사이트를 보호하기 위한 표준적인 방법이 로봇 배제 표준이라 생각하면 된다. 하지만 대다수의 로봇들이 이러한 표준을 지켜주는 것이 아니란 것을 명심하라. 독자가 로봇을 로봇을 만들 생각이라면 반드시 이 표준을 지켜주기를 권장한다.
로봇 배제표준에 대한 자세한 설명은 시간이 나는대로 따로 간단한 강좌를 만들겠다.
스토리지
검색엔진에서 사용할 색인용 데이타를 컴퓨터의 저장장치에 기록하여 두는 곳을 말한다. 초창기 상용화된 검색엔진들은 일반적인 DBMS를 사용하여 데이타를 저장하였다. 이는 관리 및 사용이 아주 용이하기 때문에 매우 효과적으로 수행될 수 있었으나 데이타가 대용량화 되어지고 알고리즘이 복잡해 지면서 점차 화일 시스템을 직접 제어하여 데이타를 저장하는 방식을 많이 사용한다. 단순하게는 화일에 필요한 키워드 정보와 포스팅화일 요약화일을 저장하는 방식에서 좀더 성능을 향상시키기 위해 물리적인 계층에서 저장장치(보통 하드디스크)를 제어하여 자체의 검색엔진 전용 화일 시스템을 구축하는 경우도 있다. 몇몇 공개된 소프트웨어 중에서는 검색엔진 전용 색인 DB를 만들어 배포하는 곳도 있다.
검색엔진을 구축하다보면 용도에 따라 Read-only 시스템으로 구축하는 경우와 read-write 시스템으로 구현하는 경우가 있다. 전자의 경우는 화일 시스템을 구성하는 것이 무척이나 간단한 문제이지만 후자일 경우는 아주 심각해진다. 허나 후자와 같은 시스템을 요구하는 업체들의 비중이 점점 높아지는 추세이며 업계에서는 이런 부분에 많은 투자를 하고 있는 시점이다.
검색엔진에서 사용되는 기본적인 스토리지의 구성은 보통 3단계로 구성되며, 이는 텀리스트, 포스팅 화일, 요약화일로 구성된다.
색인기
웹로봇을 통해 수집된 문서들을 빠르고 정확하게 검색하기 위해 문서의 중요 키워드를 추출하고 이러한 키워드들의 상관관계나 문서들의 상관관계를 정의하여 스토리지에 저장하는 프로그램이다. 키워드를 추출하기 위해 형태소분석기나 스테머등을 사용하거나 또는 n-gram 방식을 사용하기도 한다. read-write시스템의 경우는 색인기와 검색기가 하나의 시스템으로 구성되기 때문에 임계영역에 대한 문제가 대두된다. 다양한 랭킹 알고리즘에 의해 색인기의 모양은 달라지게 되면 알고리즘의 복잡도와 추출되는 색인어의 양에 의해 색인 속도에 많은 영향을 주게 되며, 이러한 색인 속도는 색인기의 전체 성능을 평가하는 기준이 되기도 한다. 스토리지는 색인기의 일부분으로 구성될 수 있으며 결국 스토리지의 구조는 검색 모델(또는 랭킹 알고리즘)에 의해 결정되어진다.
형태소분석기
형태소 분석이란 여러 형태소들의 묶음이 표층 형태로 나타나는 하나의 어절로부터 의미를 갖는 최소 단위인 각 형태소를 분석해는 내는 것으로 정의된다.(강승식) 문서의 핵심 키워드를 추출하는 기본적인 시스템이다.
검색엔진에서는 보통 형태소분석기의 모든 기능을 사용하지 않고 색인어 추출만 하기위해 특정 형태소만 취하는 경우가 대부분이다. 초기 정보검색에서는 색인어로 적합한 형태소는 명사로 국한하였다. 허나 발전을 거듭하면서 현재는 각 형태소의 구조적인 관계 및 의미관계까지 고려한 색인어를 추출하기도 하며, 이러한 방식은 자연어 검색의 기본이 된다.
스테머
보통 어근 추출용으로 많이 사용되었으며 영어권 언어에 대해서 많이 적용된다. 언어적 특성상 한국어와 같은 교착어는 어미변화와 활용형들이 아주 심한 편이어서 단순한 스테밍 알고리즘만으로 처리하기에는 문제점이 있기 때문에 한국어는 형태소분석기를 주로 사용한다. 영어같은 경우 몇가지의 간단한 룰만 적용하여 스테머를 구성할 수 있기 때문에 속도가 빠르고 효율적인 시스템을 구성할 수 있다.
검색기
사용자가 입력한 검색 질의를 색인기가 생성하여 둔 스토리지에서 정의된 검색 모델(랭킹 알고리즘)에 의해 가장 유사한 문서를 추출하여 검색하여 주는 기능이다. 질의 분석기가 별도로 내장되어 있어야 하며 특성상 대량의 정보를 빠른 시간안에 주어진 알고리즘으로 계산해 내는 능력이 필요하다. 순위화를 위해 랭커를 가지고 있으며 보다 빠른 검색을 위 캐쉬를 사용하기도 한다.
브로커
검색엔진에서 사용하는 컬렉션은 다양한 여러 종류로 구성될 수 있다. 이러한 다양한 컬렉션에 대해 하나의 질의로 검색을 할 경우 어느 컬렉션을 검색할지 최종 검색된 컬렉션별 결과들을 어떻게 취합할지에 대한 문제가 발생하게 된다. 이러한 문제를 해결해 주는 것이 브로커이다. 입력된 질의를 분석하여 검색할 대상을 찾고 각 컬렉션에서 결과를 검색한 후 이에 대한 최종 결과를 취합하여 전달해 주는 역할을 하게된다. 포탈 사이트의 통합검색 CGI도 넓은 의미에서 브로커라 할 수 있겠다.
요약기
문서의 핵심이 되는 내용을 간결한 문장으로 축약하여 주는 기능이다. 검색된 문서의 모든 내용을 보여주기에는 그 양이 너무 많기 때문에 검색자의 편의를 위해 잘 정제된 요약 내용을 보여줄 필요가 있다. 경우에 따라서는 검색기에 이런 요약기능을 부여하기도 하며 별도의 서버로 구축될 수도 있다. 자동요약 분야는 아직도 많이 연구가 되어지고 있는 분야이다.
각종 필터
다양한 포맷의 문서들에서 텍스트 정보를 추출하기 위한 기능이다. doc 화일 같은 경우 binary로 구성되어 있기 때문에 실제 text정보를 추출해 주는 doc 필터가 필요하다. 마찮가지고 html문서도 그대로 색인시 html tag도 색인이 되어질 수 있으므로 html parser를 통해 필터링을 걸쳐 text정보만을 색인하게 된다. 이런식으로 text-based 검색엔진에서는 다양한 문서들에 대한 검색 서비스를 하고자 할 경우 각각의 문서 포맷에 맞는 개별적인 필터가 있어야만 한다.
랭커
검색 결과에 대한 순위를 매겨주는 기능이다. 검색 모델 및 랭킹 알고리즘에 맞게 구성되어지는 것이 보통이며 검색기의 일 부분으로 동작하게 된다. 주된 기능은 질의에 대한 각 문서들의 연관성을 수치화 하는 기능과 결과 정렬 기능이다. 실제 검색 속도에 가장 영향을 많이 주는 부분은 포스팅화일을 스토리지에서 메모리로 로딩하는 과정과 이 랭커에서 랭킹을 하는 두 부분이다.
질의분석기
사용자가 입력한 비 정규적인 질의를 파싱하여 검색에 적합하도록 정의된 정규화된 질의 문법으로 변환하는 기능이다. 입력된 질의는 대다수 내부적인 연산에 적합하게 구성되지 않는다. 이를 최대한 연산하기에 적절한 문법으로 변환하기 위한 필수 과정이다. 분석기는 때때로 형태소분석기나 기타 토큰 분리기 등을 포함하고 있어서 질의중에 꼭 필요한 키워드만 추출할 수 있도록 하기도 한다. 논리연산을 위해서 정의된 기호들을 연산자로 대치하기도 하고 질의에 대한 파스트리를 생성하기도 한다. 또한 주어진 컬렉션들 중에 어디에서 검색할 것인가를 명확히 표현해 주기도 한다.
파서
문자열 파서가 대부분이다. 경우에 따라서는 오토마타, 형태소분석기, 기타 토큰분리기 등을 사용한다. 색인기에서 색인어 추출을 위해 사용하기도 하며 검색기에 포함되어 있는 질의 분석기에서 질의를 분석하기 위해서 사용하기도 한다.
오토마타
유한오토마타를 사용하여 주어진 질의나 문서를 파싱하기 위해 사용한다.
컬렉션
검색 대상이 되는 집합을 말한다. 웹문서 검색일 경우 로봇이 수집한 HTML문서등이 하나의 컬렉션이 될 수 있다. 다양한 조건 및 여러 필드 검색을 지원하기 위해 컬렉션은 여러개로 나뉘어 질 수 있으며 웹문서하나도 여러개의 컬렉션으로 쪼개어 구성시킬 수 있다. 예를 들어 www.yahoo.co.kr 하위의 문서 중에 '꾸러기'라는 키워드로 검색하고자 할 경우, 웹문서들의 text부분을 모아서 하나의 컬렉션으로 구성하고, url부분을 모아서 다른 하나의 컬렉션으로 구성한 후 두개의 컬렉션중에 url은 url 컬렉션에서 찾고, 키워드는 text 컬렉션에서 찾은 후 두 결과를 and 연산을 통해 최종 결과를 산출한다. 이런식으로 데이타 성격이 다른 여러개의 집합들을 개별 컬렉션으로 구성하여 다양한 연산을 통해 복잡하면서도 잘 정의된 검색 결과를 계산할 수 있다.
DB
색인기가 생성한 색인 정보들을 저장할 DB를 말한다. 일반적인 상용 RDB를 사용하여 색인 DB를 구성할 수도 있으며 속도를 위해 파일 시스템을 제어하여 별도의 화일시스템으로 구성할 수도 있다. 컬렉션의 크기와 종류가 작을 경우는 상용 RDB를 사용하는 것이 사용하기에 아주 편리하다. 그러나 대용량 컬렉션일 경우는 파일 시스템을 직접 제어하는 것이 성능상 더 효율적일 경우가 많다. 검색엔진 전용으로 연구되어진 DB들이 몇몇 대학의 연구소를 중심으로 발표되어 있긴 하나 상용으로 적용된 사례가 많지 않다. 버클리 DB를 사용하여 동적 색인을 가능케 한 검색엔진들이 발표되어 있긴 하나 성능이 만족할 만 한지는 의문이다.
프리뷰어
검색된 페이지를 직접 방문하지 않고 검색엔진 자체에 저장되어 있는 문서를 사용하여 엔진 자체에서 미리보기 형식으로 보여주는 기능이다. 웹로봇이 문서를 수집할 당시에 살아 있던 링크라 하더라도 검색하는 시점에서는 이미 삭제되어 버린 문서일 수도 있다. 또는 속도가 느려서 실제 페이지를 방문할 때 브라우져를 통해 보기가 만만찮을 경우도 있다. 이런 경우 엔진에서 저장하고 있는 데이타를 사용하여 미리보기 형식으로 데이타를 보여주어 사용자의 편의를 도모할 수 있다.
중복제거기
최근 검색엔진들의 비약적인 발전으로 인해 검색 결과에서 중복되는 문서들이 나타나는 경우는 드물다. 실제 엔진 내부에는 중복된 내용을 가지는 문서들이 상당수 존재하는 것이 일반적인 현상이며, 이러한 중복 문서를 제거하기 위해 별도의 중복 제거기가 필요하다. 크게 3부분에서 중복문서를 제거시킬 수 있으며, 첫째로 로봇에서 문서를 수집하는 시점 또는 수집후에 모든 문서들을 비교해서 중복 문서를 제거할 수 있다. 둘째로 색인 시점에서 색인과 동시에 중복되는 문서를 제거시킬 수 있으며, 마지막으로 검색한 결과에 대해서 검색기에서 검사하여 결과를 조절하는 방식으로 제거시킬 수 있다. 구글이나 네이버에서는 마지막 방법까지 사용하여 중복문서를 제거한다.
이러한 방식 때문에 실제 검색 결과와 마지막에 보여지는 개수에 차이가 보여지기도 한다.
역화일
파일 시스템 또는 데이터베이스 등과 같이 대량의 자료가 관리되는 곳에서 보다 빠르게 자료를 검색하기 위하여 각각의 자료에 대한 색인이 구성되어 있는 파일을 지칭하는 용어. 이러한 파일에는 각각의 데이터 레코드에 대한 키 값과 이러한 키 값에 의하여 지칭되는 레코드의 위치가 하나의 쌍을 이루고 있다. 키워드를 빠르게 찾기 위해 B+tree나 B-tree, trie, 페트리샤트리 등을 사용한다.
* 검색엔진의 역사
우리가 많이 사용하고 있는 검색엔진들은 과연 얼마나 오래 된 것들일까? 최근의 폭발적인
인터넷 사용자 증가와 활성화된 많은 검색엔진 제공 사이트들로 인해 이제는 검색엔진이란
단어 자체를 모르는 사람들은 거의 없을 것이다. 그러나 검색엔진 자체의 역사에 대해
관심있게 살펴본 사람은 아마도 관련업계 사람들이나 직접적인 개발자 정도가 아닐까 한다.
요즘 한참 인기가 있는 지식검색들을 유심히 지켜보면 현 시점의 대다수 사용자들이 무엇을
원하고 있는지, 요즘의 추세는 어떤지를 간접적으로나마 파악할 수 가 있다. 이는 대량의
사용자 지식이 축적된 결과로 인한 많은 부산물 중의 하나이다. 지식검색에 대한 얘기를 하려
하는 것은 아니고... ^_^; 이러한 지식검색에서 조차도 검색엔진 자체의 역사에 대한 질문은
찾아보기 힘든다. 대부분 인기있는 검색엔진의 역사정도만을 질문하는 정도이다.
일반 사용자들에게는 사실 이러한 문제가 별로 관심사가 아니기 때문에 이런 현상이 나타
나는 것으로 보여진다. 하지만 검색엔진의 개발자들이라면 한번쯤은 이 부분에 대한 자료를
찾아본 적은 있을 것이다.
각설하고..
의외로 검색엔진의 역사는 상당히 길다고 볼 수 있다. 문헌정보학 적인 측면에서 본다면
컴퓨터가 출현하기 훨씬 이전부터 기본적인 개념들은 있었던 것으로 보여진다. 전산학적인
측면에서 보면 컴퓨터가 출현하면서 바로 정보검색의 역사도 시작했다고 봐도 과언은 아닐
것이다.
정보검색(IR, Information Retrieval)이란 말은 처음 1945년 Vannervar Bush의 논문에서
처음 제시되었다. 그 후 1950년대 초반 1세대 컴퓨터의 등장 시기에 미국에서 사용되었다.
이 때부터 본격적인 정보검색의 역사가 시작된다고 보면 무리가 없을 것이다.
박민우님께서 정리한 내용에 의하면 정보검색의 역사를 요람기, 유년기, 성년기, 성숙기의
4단계로 구분해 잘 정리해 놓았다. 아쉽게도 현재의 시기에 대한 단계를 설정하지 않은 것이
있긴 하지만..
각 시기별 세부 내용을 살펴보자.
1. 요람기(1945~1955)
정보검색이란 용어가 처음 사용되었다. 이 때를 검색엔진의 태동기라 말할 수 있으며
이 때에 이미 기계번역에 대한 최초의 제안이 제시되었다. 중요한 인물들로는 1949년도의
Warren Weaver, Andrew D.Booth등이 있으며, 이때에 정보검색과 기계번역에 대한 모든
아이디어가 제시되었다. 이러한 이론들은 계속 발전되어가다 60년대에 이르러서 시스템으로
구축되는 계기가 되었다.
2. 유년기(1960년대)
위대한 경험의 시대라고 표현이 되어 있는 것만으로도 이 시대가 상당히 다양한 연구 및
개발이 있었다는 것을 미루어 짐작할 수 있을 것이다. 현재 거론되고 있는 대부분의 검색
모델들이 이 시대에 정립되었다. 또한 대용량 정보검색 시스템의 초기 모델이 제시되었다.
Free-Text Indexing 기법이 보편화 되었으며, 정보검색 시스템의 평가 기준이 완성되었다.
1966년 Cyril Cleverdon은 재현율, 정확율 기준을 마련하였다. 1968년 Gerard Salton은
다국어 검색기법을 제시하였으며, Relevance feedback 등의 신기술 검색기법이 태동되었다.
또한 BRS라는 대용량 정보검색 시스템이 구현되었다.
3. 성년기(1970년대)
전자문서의 시대로 표현될 수 있다. 이 기간에 워드프로세서의 등장으로 인해 처리해야 할
문서의 수와 양이 비약적으로 증가되었다. 하드웨어적으로는 디스크드라이브가 처음 발표
되었으며(당시 1M당 2000달러정도) 이러한 제반 요건들은 대용량 검색시스템들의 상용화를
자연스럽게 이끌게 되었다. 이때 상용화된 검색시스템으로 Dialog, Orbit, BRS등이 있다.
또한 세계 최대 규모의 도서관 네트웍인 OCLC의 등장은 따로 말을 하지 않아도 익히 알고들
있을 것이다. 최기 OCLC는 64개국의 26000개의 도서관 정보를 제공하였다.
이 시기에 데이타데이타베이스 시스템이 처음 등장하였으며, 이러한 제품들은 계층모델과
네트웍 모델을 기반으로 하였었다. 후에 이러한 데이타베이스들은 관계형, 개체형등으로
발전을 거듭하게 된다.
데이타베이스와 검색엔진의 차이는 다음과 같이 요약할 수 있다.
데이타베이스 : Data 관점, 관리중심, 결정구조, SQL->MIS로 발전
검색엔진 : Information 관점, 검색 중심, 비정형 구조, 자유검색
초기의 정보검색은 인공지능의 한 분야로 인식되어져 오다가 이 시기에 인공지능 분야에서
분리되었다. 이시기에 AI에 대한 무용론이 대두되고 IR분야는 고속성장을 맞게 된다. 그러나
최근에는 다시 AI와 IR이 접목을 시도하는 경향이 있다. 그리고 단어(워드)에 대한 처리방식
접근이 보편화 되었다.
4. 성숙기(1980년대)
본격적인 전문 검색엔진이 등장하였다. 당시 시대적 상황으로는 컴퓨터의 성능이 비약적으로
향상되었으며, 저렴한 가격대, CD-ROM의 등장등으로 하드웨어적인 요건이 대폭 향상되었으며
원문 검색에 대한 사용자의 요구가 점점 증대하게 되었다. 이러한 상황에서 전문 검색엔진의
등장은 당연한 결과이며, 도서관 위주의 검색 기술이 지속적으로 발달하였다.
5. 그후(1990년대~현재)
시대적인 구분으로는 1945~1989년까지를 구분해 보았다. IT 기술적인 구분으로는 www의 출현
전과 후(1990년 초반)로 구분하기도 한다. WWW의 출현은 정보검색 측면에서는 새로운 시대를
여는 계기가 되었으며 이로 인해 정보검색 시스템들이 일반 사용자들에 아주 쉽고 빠르게
접근할 수 있게 되었다.
이 시대에 현재 사용하고 있는 대부분의 상용 검색엔진들이 출현하였으며 WWW를 통한 거대
검색포탈들이 속속 생겨나게 되었다.
OS: Microsoft Windows 2000 5.00.2195 Service Pack 3
MySQL: 4.0.7-gamma-nt
CPU: x86 Family 6 Model 8 Stepping 10
RAM: 512MB
작성자: 강명규(kang@dbakorea.pe.kr)
FULLTEXT search
fulltext검색은 쉬운 말로 자연어 검색(natural language search)이다.
FULLTEXT 인덱스는 MyISAM table type을 가진 테이블에서만 지원되고,
CHAR, VARCHAR, TEXT column type을 가진 컬럼에서만 생성될 수 있다.
char는 언급되어 있으나, 직접 확인하진 못했으므로 함 해보기 바란다.
Feature Version
Basic FULLTEXT searching 3.23.23
Configurable parameters 4.0.0
Boolean searches 4.0.1
Phrase searches 4.0.2
Server variables
길이가 ft_min_word_len ~ ft_max_word_len 의 범위에 있는 것들만 검색 대상이 됨.
ft_min_word_len : (디폴트:4)
ft_max_word_len : (디폴트:254)
서버변수 변경
1. C:\WINNT\my.ini변경후 서버 restart(UNIX: /etc/my.cnf)
[mysqld]
set-variable = ft_min_word_len=5
2. 기존 fulltext인덱스 변경
REPAIR TABLE 테이블명 USE_FRM;
FULLTEXT 인덱스는 테이블 생성후, 대량의 데이터를 로드한 다음에 생성해주는 것이 좋다.
이 방식은 fulltext인덱스만이 아닌 다른 인덱스에도 동일하게 적용된다.
CREATE TABLE articles (
id INT UNSIGNED AUTO_INCREMENT NOT NULL PRIMARY KEY,
title VARCHAR(200),
body TEXT,
FULLTEXT (title,body)
);
INSERT INTO articles VALUES
(0,'MySQL Tutorial', 'DBMS stands for DataBase ...'),
(0,'How To Use MySQL Efficiently', 'After you went through a ...'),
(0,'Optimising MySQL','In this tutorial we will show ...'),
(0,'1001 MySQL Tricks','1. Never run mysqld as root. 2. ...'),
(0,'MySQL vs. YourSQL', 'In the following database comparison ...'),
(0,'MySQL Security', 'When configured properly, MySQL ...');
mysql> select * from articles;
+----+------------------------------+------------------------------------------+
| id | title | body |
+----+------------------------------+------------------------------------------+
| 1 | MySQL Tutorial | DBMS stands for DataBase ... |
| 2 | How To Use MySQL Efficiently | After you went through a ... |
| 3 | Optimising MySQL | In this tutorial we will show ... |
| 4 | 1001 MySQL Tricks | 1. Never run mysqld as root. 2. ... |
| 5 | MySQL vs. YourSQL | In the following database comparison ... |
| 6 | MySQL Security | When configured properly, MySQL ... |
+----+------------------------------+------------------------------------------+
6 rows in set (0.00 sec)
match에는 검색될 컬럼(들)을 적고, against에는 검색할 단어를 적는다.
match에 컬럼순서는 상관없고, against는 대소문자 관계없이 검색된다.
mysql> SELECT * FROM articles WHERE MATCH (title,body) AGAINST ('database');
+----+-------------------+------------------------------------------+
| id | title | body |
+----+-------------------+------------------------------------------+
| 5 | MySQL vs. YourSQL | In the following database comparison ... |
| 1 | MySQL Tutorial | DBMS stands for DataBase ... |
+----+-------------------+------------------------------------------+
2 rows in set (0.00 sec)
검색된 결과는 Relevance values 라는 값에 의해 정렬되는데 이것은 검색결과의 정확도를 의미한다고 보면 되겠다.
0의 값은 아무런 관련이 없다는 뜻이고, 계산기준은 다음과 같다.
row내에 단어의 수, 해당 row내의 unique한 단어수, collection내의 총단어수, 특정 단어를 포함하는 문서(rows)의 수.
번역하긴 했는데 정확히 무슨 말이라는 건지.. --;
위의 결과에 대해 Relevance values를 알아보면 다음과 같다.
id=5가 가장 큰 값이므로, 위에서 제일 처음에 표시 되었음을 알 수 있다. 0은 관련없는 것들이므로 검색결과에서
제외되었음도 봐두자.
mysql> SELECT id, MATCH (title,body) AGAINST ('database') from articles;
+----+-----------------------------------------+
| id | MATCH (title,body) AGAINST ('database') |
+----+-----------------------------------------+
| 1 | 0.65545834044456 |
| 2 | 0 |
| 3 | 0 |
| 4 | 0 |
| 5 | 0.66266459031789 |
| 6 | 0 |
+----+-----------------------------------------+
6 rows in set (0.00 sec)
검색에 사용되는 단어는 문자,숫자,', _ 이다.
검색에서 제외되는 단어(stopword)는 너무 짧은 단어(디폴트로 3단어이하, 서버변수 ft_min_word_len에서 지정)
이거나, stopword list에 포함된 단어들(the,..)이다.
자주 사용되는 단어나 문법적인 관계에 쓰이는 단어는 검색시 비중이 낮고,
드물게 사용되는 단어(용어, 학술어, ...)는 높은 비중을 가진다. 이 비중(weight)은 Relevance계산시 이용된다.
mysql> SELECT * FROM articles WHERE MATCH (title,body) AGAINST ('MySQL');
Empty set (0.00 sec)
분명히 mysql이라는 단어가 존재함에도 불구하고, 위의 질의는 아무런 결과를 리턴하지 않는다.
이유는 MySQL이라는 단어가 너무 많이 존재하기 때문이다. 검색어가 rows에 반이 넘게 존재하면,
stopword로 취급된다.(50% threshold)
4.0.1이상부터는 in boolean mode 를 사용하면 50% threshold가 적용되지 않으며 다음과 같이 검색결과를 얻을 수 있다.
boolean mode에서는 FULLTEXT인덱스가 걸린 컬럼이 아니더라도 검색할 수 있다. 하지만 느려진다.
또한, 검색결과는 Relevance values에 의한 정렬이 이루어지지 않는다.
mysql> SELECT * FROM articles WHERE MATCH (title,body) AGAINST ('MySQL' IN BOOLEAN MODE);
+----+------------------------------+------------------------------------------+
| id | title | body |
+----+------------------------------+------------------------------------------+
| 1 | MySQL Tutorial | DBMS stands for DataBase ... |
| 2 | How To Use MySQL Efficiently | After you went through a ... |
| 3 | Optimising MySQL | In this tutorial we will show ... |
| 4 | 1001 MySQL Tricks | 1. Never run mysqld as root. 2. ... |
| 5 | MySQL vs. YourSQL | In the following database comparison ... |
| 6 | MySQL Security | When configured properly, MySQL ... |
+----+------------------------------+------------------------------------------+
6 rows in set (0.00 sec)
boolean mode에서는, 검색에서 제외할 단어는 -로, 검색에 포함될 단어는 +로 지정할 수도 있다.
mysql> SELECT * FROM articles WHERE MATCH (title,body) AGAINST ('+mysql -tutorial' in boolean mode);
+----+------------------------------+------------------------------------------+
| id | title | body |
+----+------------------------------+------------------------------------------+
| 2 | How To Use MySQL Efficiently | After you went through a ... |
| 4 | 1001 MySQL Tricks | 1. Never run mysqld as root. 2. ... |
| 5 | MySQL vs. YourSQL | In the following database comparison ... |
| 6 | MySQL Security | When configured properly, MySQL ... |
+----+------------------------------+------------------------------------------+
4 rows in set (0.00 sec)
+,- 와 더불어 다음의 operator도 사용할 수 있다.
+ : 검색시 반드시 포함될 단어
- : 검색시 제외될 단어
< : 단어의 검색능력에 대한 기여도(contribution)를 감소시킴
> : 단어의 검색능력에 대한 기여도(contribution)를 감소시킴
(): 검색 단어들을 subexpressions으로 그룹화시킴
~ : negative 오퍼레이터로 작용. 검색능력에 대한 기여도를 음수로 만듬.
-와 유사하지만 제외되지는 않음. noise word를 의미할때 사용될 수 있다.
* : 일반적인 유닉스 쉘상의 기능과 동일(truncation operator)
" : ""로 쌓인 순서대로 있는 것만 검색됨.
예)
apple banana
find rows that contain at least one of these words.
+apple +juice
... both words.
+apple macintosh
... word ``apple'', but rank it higher if it also contain ``macintosh''.
+apple -macintosh
... word ``apple'' but not ``macintosh''.
+apple +(>pie ... ``apple'' and ``pie'', or ``apple'' and ``strudel'' (in any order), but rank ``apple pie'' higher than ``apple strudel''.
apple*
... ``apple'', ``apples'', ``applesauce'', and ``applet''.
"some words"
... ``some words of wisdom'', but not ``some noise words''.
댓글목록
등록된 댓글이 없습니다.