검색 엔진 1 - 구성 요소

IR 그룹의 하얀 눈길 님께서 작성하신 글입니다.

원문은 여기를 누르시면 볼 수 있습니다.

1주일에 한번씩 올리려 한 것이 개인적인 사유로 많이 늦어지고 있습니다.(핑계지요 )
이번에 올릴 글을 작성하다 보니 글이 길어지는 것 같아 두 부분으로 나누었습니다.
뒷부분은 별도 제목으로 하여 따로 올리려 합니다.
두서없이 정리한 것이라 내용이 역시 부실하군요.

============================================================================
정보검색시스템의 구성요소

1. 정보검색시스템이란?
정보 수요자가 필요하다고 예측되는 정보나 데이터를 미리 수집, 가공, 처리하여 찾기 쉬은 형태로 축적해 놓은 데이터 베이스로부터 요구에 적합한 정보를 신속하게 찾아내어 정보 요구자에게 제공하는 시스템을 말한다.

2. 배경학문
자료구조론 (Speed & Memory Trade-off)
데이터베이스론 (DB Indexing)
검색알고리즘
AI의 Search, NLP, Story understanding Algorithm
ES의 Inferencing

3. 구성요소
3.1) 웹로봇
웹상에 존재하는 문서들을 가져오기 위해서 웹의 하이퍼텍스트 구조를 자동적으로 추적하여 참조되어지는 모든 문서들을 재귀적으로 검색하는 프로그램을 말한다. 여기서 '재귀적으로'라는 의미는 어떤 명시된 트래버스 알고리즘으로 유한하게 정의되어지는 것이 아님을 주목하라. 비록 로봇이 문서 선택을 위해 몇몇의 발견적인 학습법을 허락한다거나 방문하기 위한 문서의 순서를 정한다거나 하더라도 여전히 로봇이다. 일반적인 웹브라우저는 로봇이 아니다. 왜냐하면 그것들은 인간에 의해 수행되어진다. 그리조 참조되어지는 문서들을 자동적으로 수집하지 않는다. 크롤러(crawler), 스파이더(spider), 개더러(gatherer), 웸(worms), 안츠(ants) 등 다양한 이름으로 불리우지만 일반적인 명칭으로는 로봇이라 칭하는 비율이 높은듯 하다. 로봇을 얘기하면서 빼 놓을 수 없는 것이 로봇 배제 표준(robot exclusion standard)이다. 봇은 상당히 무책임한 프로그램이 될 수 있으며, 심한 경우는 웸바이러스와 같은 행동을 보일 수 있다. 필자의 경우 회사에서 로봇을 구동시키던 도중 국내의 유명 쇼핑몰의 DB를 죽여버린 경우가 있었다. 다행히 관용을 베풀어 주셔서 조용히 넘어갈 수 있었지만 돌이켜 보면 무척이나 위험한 상황이었다. 이처럼 잘못 구성된 로봇으로 인해 특정 사이트를 죽여버리거나 망 자체를 마비시킬 수도 있는 것이 로봇이다. 이런 로봇의 위험에서 자신의 웹사이트를 보호하기 위한 표준적인 방법이 로봇 배제 표준이라 생각하면 된다. 하지만 대다수의 로봇들이 이러한 표준을 지켜주는 것이 아니란 것을 명심하라. 독자가 로봇을 만들 생각이라면 반드시 이 표준을 지켜주기를 권장한다. 로봇 배제표준에 대한 자세한 설명은 시간이 나는대로 따로 간단한 강좌를 만들겠다.

3.2)스토리지
검색엔진에서 사용할 색인용 데이타를 컴퓨터의 저장장치에 기록하여 두는 곳을 말한다. 초창기 상용화된 검색엔진들은 일반적인 DBMS를 사용하여 데이타를 저장하였다. 이는 관리 및 사용이 아주 용이하기 때문에 매우 효과적으로 수행될 수 있었으나 데이타가 대용량화 되어지고 알고리즘이 복잡해 지면서 점차 화일 시스템을 직접 제어하여 데이타를 저장하는 방식을 많이 사용한다. 단순하게는 화일에 필요한 키워드 정보와 포스팅화일 요약화일을 저장하는 방식에서 좀더 성능을 향상시키기 위해 물리적인 계층에서 저장장치(보통 하드디스크)를 제어하여 자체의 검색엔진 전용 화일 시스템을 구축하는 경우도 있다. 몇몇 공개된 소프트웨어 중에서는 검색엔진 전용 색인 DB를 만들어 배포하는 곳도 있다. 검색엔진을 구축하다보면 용도에 따라 Read-only 시스템으로 구축하는 경우와 read-write 시스템으로 구현하는 경우가 있다. 전자의 경우는 화일 시스템을 구성하는 것이 무척이나 간단한 문제이지만 후자일 경우는 아주 심각해진다. 허나 후자와 같은 시스템을 요구하는 업체들의 비중이 점점 높아지는 추세이며 업계에서는 이런 부분에 많은 투자를 하고 있는 시점이다. 검색엔진에서 사용되는 기본적인 스토리지의 구성은 보통 3단계로 구성되며, 이는 텀리스트, 포스팅 화일, 요약화일로 구성된다.

3.3)색인기
웹로봇을 통해 수집된 문서들을 빠르고 정확하게 검색하기 위해 문서의 중요 키워드를 추출하고 이러한 키워드들의 상관관계나 문서들의 상관관계를 정의하여 스토리지에 저장하는 프로그램이다. 키워드를 추출하기 위해 형태소분석기나 스테머등을 사용하거나 또는 n-gram 방식을 사용하기도 한다. read-write시스템의 경우는 색인기와 검색기가 하나의 시스템으로 구성되기 때문에 임계영역에 대한 문제가 대두된다. 다양한 랭킹 알고리즘에 의해 색인기의 모양은 달라지게 되면 알고리즘의 복잡도와 추출되는 색인어의 양에 의해 색인 속도에 많은 영향을 주게 되며, 이러한 색인 속도는 색인기의 전체 성능을 평가하는 기준이 되기도 한다. 스토리지는 색인기의 일부분으로 구성될 수 있으며 결국 스토리지의 구조는 검색 모델(또는 랭킹 알고리즘)에 의해 결정되어진다.

3.4)형태소분석기
형태소 분석이란 여러 형태소들의 묶음이 표층 형태로 나타나는 하나의 어절로부터 의미를 갖는 최소 단위인 각 형태소를 분석해는 내는 것으로 정의된다.(강승식) 문서의 핵심 키워드를 추출하는 기본적인 시스템이다. 검색엔진에서는 보통 형태소분석기의 모든 기능을 사용하지 않고 색인어 추출만 하기위해 특정 형태소만 취하는 경우가 대부분이다. 초기 정보검색에서는 색인어로 적합한 형태소는 명사로 국한하였다. 허나 발전을 거듭하면서 현재는 각 형태소의 구조적인 관계 및 의미관계까지 고려한 색인어를 추출하기도 하며, 이러한 방식은 자연어 검색의 기본이 된다.

3.5)스테머
보통 어근 추출용으로 많이 사용되었으며 영어권 언어에 대해서 많이 적용된다. 언어적 특성상 한국어와 같은 교착어는 어미변화와 활용형들이 아주 심한 편이어서 단순한 스테밍 알고리즘만으로 처리하기에는 문제점이 있기 때문에 한국어는 형태소분석기를 주로 사용한다. 영어같은 경우 몇가지의 간단한 룰만 적용하여 스테머를 구성할 수 있기 때문에 속도가 빠르고 효율적인 시스템을 구성할 수 있다.

3.6)검색기
사용자가 입력한 검색 질의를 색인기가 생성하여 둔 스토리지에서 정의된 검색 모델(랭킹 알고리즘)에 의해 가장 유사한 문서를 추출하여 검색하여 주는 기능이다. 질의 분석기가 별도로 내장되어 있어야 하며 특성상 대량의 정보를 빠른 시간안에 주어진 알고리즘으로 계산해 내는 능력이 필요하다. 순위화를 위해 랭커를 가지고 있으며 보다 빠른 검색을 위 캐쉬를 사용하기도 한다.

3.7)브로커
검색엔진에서 사용하는 컬렉션은 다양한 여러 종류로 구성될 수 있다. 이러한 다양한 컬렉션에 대해 하나의 질의로 검색을 할 경우 어느 컬렉션을 검색할지 최종 검색된 컬렉션별 결과들을 어떻게 취합할지에 대한 문제가 발생하게 된다. 이러한 문제를 해결해 주는 것이 브로커이다. 입력된 질의를 분석하여 검색할 대상을 찾고 각 컬렉션에서 결과를 검색한 후 이에 대한 최종 결과를 취합하여 전달해 주는 역할을 하게된다. 포탈 사이트의 통합검색 CGI도 넓은 의미에서 브로커라 할 수 있겠다.

3.8)요약기
문서의 핵심이 되는 내용을 간결한 문장으로 축약하여 주는 기능이다. 검색된 문서의 모든 내용을 보여주기에는 그 양이 너무 많기 때문에 검색자의 편의를 위해 잘 정제된 요약 내용을 보여줄 필요가 있다. 경우에 따라서는 검색기에 이런 요약기능을 부여하기도 하며 별도의 서버로 구축될 수도 있다. 자동요약 분야는 아직도 많이 연구가 되어지고 있는 분야이다.

3.9)각종 필터
다양한 포맷의 문서들에서 텍스트 정보를 추출하기 위한 기능이다. doc 화일 같은 경우 binary로 구성되어 있기 때문에 실제 text정보를 추출해 주는 doc 필터가 필요하다. 또한 html문서도 그대로 색인시 html tag도 색인이 되어질 수 있으므로 html parser를 통해 필터링을 걸쳐 text정보만을 색인하게 된다. 이런식으로 text-based 검색엔진에서는 다양한 문서들에 대한 검색 서비스를 하고자 할 경우 각각의 문서 포맷에 맞는 개별적인 필터가 있어야만 한다.

3.10)랭커
검색 결과에 대한 순위를 매겨주는 기능이다. 검색 모델 및 랭킹 알고리즘에 맞게 구성되어지는 것이 보통이며 검색기의 일 부분으로 동작하게 된다. 주된 기능은 질의에 대한 각 문서들의 연관성을 수치화 하는 기능과 결과 정렬 기능이다. 실제 검색 속도에 가장 영향을 많이 주는 부분은 포스팅화일을 스토리지에서 메모리로 로딩하는 과정과 이 랭커에서 랭킹을 하는 두 부분이다.

3.11)질의분석기
사용자가 입력한 비 정규적인 질의를 파싱하여 검색에 적합하도록 정의된 정규화된 질의 문법으로 변환하는 기능이다. 입력된 질의는 대다수 내부적인 연산에 적합하게 구성되지 않는다. 이를 최대한 연산하기에 적절한 문법으로 변환하기 위한 필수 과정이다. 분석기는 때때로 형태소분석기나 기타 토큰 분리기 등을 포함하고 있어서 질의중에 꼭 필요한 키워드만 추출할 수 있도록 하기도 한다. 논리연산을 위해서 정의된 기호들을 연산자로 대치하기도 하고 질의에 대한 파스트리를 생성하기도 한다. 또한 주어진 컬렉션들 중에 어디에서 검색할 것인가를 명확히 표현해 주기도 한다.

3.12)파서
문자열 파서가 대부분이다. 경우에 따라서는 오토마타, 형태소분석기, 기타 토큰분리기 등을 사용한다. 색인기에서 색인어 추출을 위해 사용하기도 하며 검색기에 포함되어 있는 질의 분석기에서 질의를 분석하기 위해서 사용하기도 한다.

3.13)오토마타
유한오토마타를 사용하여 주어진 질의나 문서를 파싱하기 위해 사용한다.

3.14)컬렉션
검색 대상이 되는 집합을 말한다. 웹문서 검색일 경우 로봇이 수집한 HTML문서등이 하나의 컬렉션이 될 수 있다. 다양한 조건 및 여러 필드 검색을 지원하기 위해 컬렉션은 여러개로 나뉘어 질 수 있으며 웹문서하나도 여러개의 컬렉션으로 쪼개어 구성시킬 수 있다. 예를 들어 www.yahoo.co.kr 하위의 문서 중에 '꾸러기'라는 키워드로 검색하고자 할 경우, 웹문서들의 text부분을 모아서 하나의 컬렉션으로 구성하고, url부분을 모아서 다른 하나의 컬렉션으로 구성한 후 두개의 컬렉션중에 url은 url 컬렉션에서 찾고, 키워드는 text 컬렉션에서 찾은 후 두 결과를 and 연산을 통해 최종 결과를 산출한다. 이런식으로 데이타 성격이 다른 여러개의 집합들을 개별 컬렉션으로 구성하여 다양한 연산을 통해 복잡하면서도 잘 정의된 검색 결과를 계산할 수 있다.

3.15)DB
색인기가 생성한 색인 정보들을 저장할 DB를 말한다. 일반적인 상용 RDB를 사용하여 색인 DB를 구성할 수도 있으며 속도를 위해 파일 시스템을 제어하여 별도의 화일시스템으로 구성할 수도 있다. 컬렉션의 크기와 종류가 작을 경우는 상용 RDB를 사용하는 것이 사용하기에 아주 편리하다. 그러나 대용량 컬렉션일 경우는 파일 시스템을 직접 제어하는 것이 성능상 더 효율적일 경우가 많다. 검색엔진 전용으로 연구되어진 DB들이 몇몇 대학의 연구소를 중심으로 발표되어 있긴 하나 상용으로 적용된 사례가 많지 않다. 버클리 DB를 사용하여 동적 색인을 가능케 한 검색엔진들이 발표되어 있긴 하나 성능이 만족할 만 한지는 의문이다.

3.16)프리뷰어
검색된 페이지를 직접 방문하지 않고 검색엔진 자체에 저장되어 있는 문서를 사용하여 엔진 자체에서 미리보기 형식으로 보여주는 기능이다. 웹로봇이 문서를 수집할 당시에 살아 있던 링크라 하더라도 검색하는 시점에서는 이미 삭제되어 버린 문서일 수도 있다. 또는 속도가 느려서 실제 페이지를 방문할 때 브라우져를 통해 보기가 만만찮을 경우도 있다. 이런 경우 엔진에서 저장하고 있는 데이타를 사용하여 미리보기 형식으로 데이타를 보여주어 사용자의 편의를 도모할 수 있다.

3.17)중복제거기
최근 검색엔진들의 비약적인 발전으로 인해 검색 결과에서 중복되는 문서들이 나타나는 경우는 드물다. 실제 엔진 내부에는 중복된 내용을 가지는 문서들이 상당수 존재하는 것이 일반적인 현상이며, 이러한 중복 문서를 제거하기 위해 별도의 중복 제거기가 필요하다. 크게 3부분에서 중복문서를 제거시킬 수 있으며, 첫째로 로봇에서 문서를 수집하는 시점 또는 수집후에 모든 문서들을 비교해서 중복 문서를 제거할 수 있다. 둘째로 색인 시점에서 색인과 동시에 중복되는 문서를 제거시킬 수 있으며, 마지막으로 검색한 결과에 대해서 검색기에서 검사하여 결과를 조절하는 방식으로 제거시킬 수 있다. 구글이나 네이버에서는 마지막 방법까지 사용하여 중복문서를 제거한다. 이러한 방식 때문에 실제 검색 결과와 마지막에 보여지는 개수에 차이가 보여지기도 한다.

3.18)역화일
파일 시스템 또는 데이터베이스 등과 같이 대량의 자료가 관리되는 곳에서 보다 빠르게 자료를 검색하기 위하여 각각의 자료에 대한 색인이 구성되어 있는 파일을 지칭하는 용어. 이러한 파일에는 각각의 데이터 레코드에 대한 키 값과 이러한 키 값에 의하여 지칭되는 레코드의 위치가 하나의 쌍을 이루고 있다. 키워드를 빠르게 찾기 위해 B+tree나 B-tree, trie, 페트리샤트리 등을 사용한다.


=============================================================================
다음 강좌는 검색기법에 대해 간단히 정리하여 보겠습니다.
그럼 좋은 하루 되세요.