웹문서 검색엔진 기술의 핵심 II - Indexing 방법론 > php

출처 : http://www.sarangnamu.net/

안녕하세요...^^
 
웹문서 검색엔진 기술에 관심이 많은 사람입니다.
 
Indexing 방법론에 관해서 많은 의견을 나누고 싶습니다.
 
좋은 조언 부탁드리겠습니다. 
 
--------------------------------------------------------------------------------
 
데이타베이스의 테이블의 경우 크게 나누면 다음의 2개로 구성됩니다.(실제
로는 전체 용량의 감소과 검색 속도의 향상을 위해서 구조가 더 복잡하지만
여기서는 단순화해서 설명하겠습니다)
 
- kw_table: 각 웹문서로부터 뽑아낸 키워드가 저장되어 있는 테이블입니다.
일종의 역인덱스 파일이라고 할 수 있죠. 각 키워드는 자신이 속한 웹문서의
번호와 함께 저장되어 있습니다.
 
- html_table: 원래의 웹문서가 저장되어 있습니다.
 
 
----------------------
현재 이런 구조에서 단일어 검색의 경우는 보통 0.2초 이하에 결과가 나옵니
다. 아마 지금보다 데이타가 더 많다고 해도 결과는 비슷하리라 생각합니다.
그런데 문제는 and 검색의 경우입니다. 현재 and 검색의 경우는 보통 1초에서
5초까지 걸립니다. 물론 이것도 결과 갯수를 500개로 제한을 걸어둔 상태입니
다. and 검색의 경우는 다음의 두가지 방법을 시도해 봤습니다.
 
 
 
1) kw_table에서 교집합을 구하는 방법 - 예를 들어서 '게임 정보' 라는 검
색어를 사용하여 검색을 하는 경우 먼저 kw_table에서 '게임'에 해당하는
웹문서의 번호를 구하고 다시 kw_table에서 '정보'에 해당하는 웹문서의 번
호를 구한 다음 이것들의 교집합을 구하는 것입니다. 하나의 sql 문으로 표
현하자면 다음과 같은 형식이 되겠죠.
 
 
 
select html_idx, count(*) cnt from kw_table where kw in('게임', '정보')
group by html_idx having cnt = 2 limit 0, 15;
 
 
 
그러나 이 경우는 일단 group by 에서 많은 부하가 걸리고 해당되는 row의
갯수를 구하기 위해서 모든 row를 가져와야 하는 문제가 있어서 포기했습니
다.
 
 
 
2) kw_table로부터 임시 테이블을 만들고 이것을 join하여 순차검색을 하는
방법 - 예를 들어서 '게임 정보' 라는 검색어를 사용할 경우 먼저 '게임'에
해당하는 웹문서 번호를 임시 테이블로 만들고 이것을 다시 html_table과
join을 한 다음 '정보'라는 키워드가 들어있는 row를 순차검색으로 뽑아
냅니다. 실제 sql 문은 다음과 같은 형태가 되겠죠.
 
 
 
create temporary table tmp(html_idx int) select html_idx from kw_table
where kw = '게임';
 
select * from html_table a, tmp b where a.html_idx = b.html_idx
and kw like '%정보%';
 
 
 
사실 현재는 이 방법을 사용하고 있습니다. 순차검색을 하기는 하지만 mysql
의 경우 게시판에서 내용검색을 한다고 해도 pc급 서버에서도 1만개 정도의
게시물은 1초 이하로 검색이 완료되기에 순차검색을 한다고 해도 별 무리는 없
다고 봅니다. 현재는 처음 kw_table에서 가져오는 tmp 테이블의 데이타를 500
개로 제한하고 있습니다. 그러니 현재로서는 최대 500개를 join하고 순차검색을
하는 형태입니다.
 
 
 
실제로 이 방식의 경우는 group by에 의한 교집합을 구하는 방식보다 빠르고
전체 row 갯수를 구하기 위해 일단 모든 row를 가져와야하는 불합리한 점도
없지만 임시 테이블 생성과 join에서 부하가 걸리더군요. 임시 테이블의 경우는
in-memory 테이블이라서 부하가 걸리지 않으리라 생각했는데 의외로 시간을
소모하는 경우가 있더군요. 그리고 join의 경우는 대부분의 시간을 잡아먹는 속
도저하의 주범이죠. 제 생각에는 join의 경우는 데이타의 분포형태와도 관련이
있는 것 같습니다. 아마 하드드라이브의 헤드가 움직이는 범위가 클 수록 join에
서의 속도저하가 심해지지 않나 싶습니다.
 
 
 
그리고 and 검색에서 제한을 거는 것 자체에는 문제가 없다고 봅니다. 제가 알
기로는 대부분의 검색엔진이 and 검색의 대상을 어떤 형태로든 제한을 하고 있
습니다. 제가 생각하기에는 현재 사용하고 있는 방식으로도 제한의 갯수를 1만
개까지 늘릴 수 있다면 아무런 문제가 없다고 봅니다. 하지만 현재 500개의 제한
으로도 충분한 속도가 나오지 않기 때문에 고민 중이죠.
 
 
 
아무튼 여기까지가 제가 현재 검색엔진을 개발하면서 겪고 있는 문제점입니
다.
 
 
----------------------
현재 제가 생각하는 해결 방식은 일단 하드를 scsi로 교체하여 하드드라이브
를 읽는 속도를 높이는 것과 ram을 늘리고 일부 테이블을 ram에 올리는 것입
니다. 모든 테이블을 램으로 올릴 수는 없겠지만 join시에 속도저하의 주범이
되는 테이블을 램으로 올리는 것은 가능합니다. 이것으로 속도를 상당한 정도
로 향상시킬 수 있다고 생각은 합니다. 
 
 
 
아무튼 현재 제가 생각하는 방식은 하드웨어의 성능을 높이는 방향입니다. 그
러나 이외에 제가 생각해낸 데이타 구조나 쿼리의 방법이 완전히 틀린 것은 아닐
까하는 생각도 하고 있습니다. 그래서 이런 경우에서 작업을 해보신 분들의 조언
을 구합니다. 요즘 저의 생각은 다음의 4가지로 표현할 수 있습니다.
 
 
 
1) 역인덱스 구조에서의 AND 검색시에 임시 테이블이나 join을 쓰지 않고 처리할
 
수 있는 방법이 있을까요?
 
 
 
2) 만약 현재의 db구조를 유지한다면 어떤 형태로 쿼리를 구성하는 것이 최선
일까요?
 
 
 
3) mysql로는 무리가 있으니 다른 데이타베이스로 교체하는 것이 옳을까요?
 
 
 
4) 아니면 데이타베이스를 사용하는 것 부터가 무리이니 차라리 파일 시스템으
로 가야 할까요?
 
 
 
저와 비슷한 경험을 갖고 계신 분들이 계시다면 고견을 들려주시면 감사하겠
습니다.
 
 
 
이 글에 대한 댓글이 총 4건 있습니다.
저는 예전 DSN의 게시판 검색 알고리즘을 참고해서 쇼핑몰의 상품 검색을 만들었습니다.
(지금의 DSN ?게시판 검색 알고리즘은 개편하면서 바뀐 것으로 알고 있습니다.)
 
Temporary 테이블은 만들 때, TYPE=Heap 과 같이 적어 주어야만 메모리에 테이블이 생기게 됩니다. Heap 테이블로 안 만들면, Disk 상에 테이블이 생성되죠. 이때는 max_heap_size 인가. 하는 변수의 크기 보다 큰 테이블이 생성되면 에러가 생기므로 변수를 미리 늘려 주세요.
 
저도 AND 연산 시에 JOIN을 걸긴 하는데, 님과는 약간 다릅니다.
 
'스타 게임 정보' 라고 검색을 햇으면, '스타', '게임', '정보'로 3개의 임시 테이블을 생성합니다.
 
create temporary table tmp1(html_idx int, INDEX(html_idx)) type=heap select html_idx from kw_table where kw = '스타';
create temporary table tmp2(html_idx int, INDEX(html_idx)) type=heap select html_idx from kw_table where kw = '게임';
create temporary table tmp3(html_idx int, INDEX(html_idx)) type=heap select html_idx from kw_table where kw = '정보';
 
이렇게 한 후에, tmp1, tmp2, tmp3 를 html_idx로 조인 겁니다.
 
html_idx에 INDEX가 걸려 있으므로 속도는 무지 빠릅니다.
아마 테스트 해 보시면, 마음에 드는 속도가 나올 것으로 예상됩니다.
상품 수십만 개로 테스트했을 때, Pen III 500에서도 0.5 이하이었던 것으로 기억하고 있습니다.
 
결과가 나오면 알려 주시면 감사~
 
허정수(wertyu)님이 2003-10-10 12:45:48에 작성한 댓글입니다.먼저 답변 감사드립니다. 지금까지 답변하신 분 중 문제를 제대로
파악하신 분은 허정수님 뿐인듯 합니다. ^^;
 
 
 
지금으로서는 인덱싱 테이블을 하나 추가할 것을 고려 중입니다. 기
존의 인덱싱 테이블은 웹문서의 랭킹에 의해서 소팅이 되어 있습니
다. 그래서 join시에 html_table에서 순서대로 데이타를 읽어오지 못
하게 되고 결과적으로 하드디스크의 헤드의 이동거리가 커지는 것 같
습니다. 그래서 html_idx로 소팅한 인덱스 테이블을 하나 추가하고
AND 검색시에는 이 테이블을 이용하는 방법을 생각 중입니다. 실제로
테스트를 해 본 결과는 2배 이상 빠른 것 같더군요.
 
 
 
아무튼 허정수님이 알려주신 방법도 현재 테스트 중입니다. 그런데
약간 궁금한 점이 있어서 질문을 드립니다.
 
 
 
먼저 답변 내용의 쿼리문은 에러가 떨어져서 2개의 쿼리로 바꾸었습니다.
 
 
 
create temporary table tmp(html_idx mediumint, index(html_idx)) type=heap;
insert into tmp select html_idx from kw_table where kw = '게임';
 
 
 
create temporary table tmp2(html_idx mediumint, index(html_idx)) type=heap;
insert into tmp select html_idx from kw_table where kw = '정보';
 
 
 
이렇게 하면 tmp와 tmp2라는 테이블이 만들어집니다. 그런데 여기서
어떤 방식으로 join을 하나요? 아래와 같은 형태는 아닐테고 말입니다.
 
 
 
select count(*) from tmp, tmp2 where tmp.html_idx = tmp2.html_idx;
select* from tmp, tmp2 where tmp.html_idx = tmp2.html_idx;
 
 
 
이것도 역시 2개의 테이블에서 교집합을 구해야 할 것 같은데 한수 지도
를 부탁합니다.
 
 
 
그리고 궁금한 점은 heap 테이블에도 인덱스가 걸리나요? 저는 테이블
구조가 해시라고 해서 인덱스가 필요 없는 줄 알았는데 제가 잘못 알고
있었나 봅니다.
 
jinyedge님이 2003-10-10 14:21:56에 작성한 댓글입니다.
이 댓글은 2003-10-10 14:51:30에 마지막으로 수정되었습니다. [⊙][X]아.예. 제가 jinyedge님께서 사용하신 SQL문을 copy&paste하다가 그랬네요 ^^
 
정확한 것은
 
 
 
??????????????? $query_format = "CREATE TEMPORARY TABLE product_fti_%d type=heap
??????????????????????? SELECT product_no FROM product_fti
??????????????????????? WHERE keyword LIKE '%s%%'";
 
 
 
이런 식입니다.(%d 부분을 보시며 알겠지만, 단어 수 만큼 loop돕니다)
 
회사에서 사용하는 소스의 일부입니다. CREATE TABLE 후에, CREATE INDEX로 인덱스를 생성하고 있습니다.
 
HEAP에서도 인덱스는 물론 걸리구요.
 
임시 테이블간 교집합은 junyedge님께서 생각하시는 방법입니다. 테이블끼리 모두 조인시키죠. INDEX를 타기 때문에 속도는 빠릅니다.
 
그리고, 
 
 
 
select count(*) from tmp, tmp2 where tmp.html_idx = tmp2.html_idx;
select* from tmp, tmp2 where tmp.html_idx = tmp2.html_idx;
 
 
 
이렇게 하실 필요는 없구요.
 
먼저, JOIN의 결과를 HEAP 테이블에 INSERT를 시키면(CREATE TABLE .... SELECT ... ), 나중에 결과 테이블에서 COUNT(*)만 하면 중복 쿼리를 없앨 수 있습니다. ^^
 
앞에서 말씀 드린 데로 위 방법은 DSN 게시판 검색 소스를 보고 카피한 것이죠.
 
허정수(wertyu)님이 2003-10-10 15:23:13에 작성한 댓글입니다.허정수님의 방법을 테스트해 보기는 했는데..
 
아직은 잘 모르겠습니다.
 
limit 를 3000개 이하로 하며 확실히 빠르기는 한 것 같은데
 
5000개 정도로 늘리면 임시 테이블 생성에서 시간을 많이
 
잡아 먹네요.
 
어쩌면 하드드라이브를 사용하는 것 같기도 하고...
 
max_heap_table_size를 64M로 늘리기는 했는데...
 
어쩌면 그 이상이 필요한지도 모르겠네요.
 
아무튼 좋은 정보 감사드립니다. 
 
 
[웹문서 검색엔진 기술의 핵심]
 
웹문서 검색엔진 기술에 있어서 핵심적인 부분은 다음의 몇가지로 요약될 수 있다.
1. 인덱싱한 문서의 갯수
현재 한국에서 서비스되고 있는 웹문서 검색엔진들의 경우 인덱싱하고 있는 문서가 보통 1천만에서 4천만개 정도로 추산된다. 이런 점을 고려하면 한국에서 경쟁력있는 웹문서 검색엔진을 서비스하기 위해서는 먼저 1천만개 이상의 웹문서를 인덱싱하는 것이 필수라고 생각된다. 그러나 천만 단위의 웹문서를 인덱싱하기 위해서는 다음과 같은 몇가지의 기술적, 정책적, 비용적 난점이 존재한다.
 
- 문서의 수집속도
1천만개 이상의 웹문서를 인덱싱하려면 우선 매우 빠른 속도로 문서를 수집하고 처리하는 크롤러(Crawler)가 필요하다. 만약 크롤러가 하루에 10만개씩의 문서를 수집한다고 가정하면 1천만개의 문서를 수집하기 위해서는 3개월 이상의 시간을 소모해야 한다. 그러나 전체 인덱싱 과정을 완료하기 위해서 3개월 이상의 시간을 소모한다면, 해당 검색엔진에서 검색되는 정보가 3개월 이전의 것일 수 있다는 점에서 문서의 수집속도가 충분히 빠르다고는 말할 수 없다. 현재 국내에 서비스되는 웹문서 검색엔진 중에서 전체 웹문서를 새로이 수집하고 인덱싱을 하는 풀업데이트 작업의 속도가 가장 빠른 검색엔진은 4천만개 이상의 웹문서를 1개월 이내에 풀업데이트를 한다. 그러므로 국내에서 경쟁력 있는 웹문서 검색엔진을 서비스하려면, 물론 목표로 하는 인덱스의 크기에 따라 다르지만, 보통 하루에 1백만개 이상의 웹문서를 수집할 수 있는 크롤러가 필요하다고 생각된다.
 
- 효율적인 인덱스 구조
현재 대부분의 검색엔진들이 여러가지 이유로 인해서 역인덱스(Inverted-Index) 구조를 사용하고 있는데, 만약 역인덱스 구조를 사용하는 검색엔진이 1천만개의 문서를 저장하고 문서당 평균적으로 100개의 단어를 인덱싱한다면, 전체 인덱스의 데이타 갯수는 약 10억개에 달한다. 이런 크기의 인덱스를 유지하고 검색하려면 데이타의 물리적인 구조 또한 매우 효율적으로 이루어져 있어야 하는데, 구체적으로 말하자면 검색의 경우에는 하드드라이브의 헤드의 움직임을 최소화하는 형태로 데이타의 물리적인 구조가 이루어져 있어야 하며, 새로운 데이타를 입력하는 경우에는 전체 인덱스를 다시 정렬하는 등의 불합리한 과정이 없어야 한다.
 
- 고성능의 하드웨어
웹문서 검색엔진의 경우 다루는 데이타의 크기가 보통 수십기가바이트가 넘으며 대형 검색엔진의 경우에는 테라바이트 급의 데이타를 다루는 경우도 있다. 이런 크기의 데이타를 빠른 시간내에 처리하려면 먼저 입출력 속도가 빠른 대용량의 저장장치가 있어야 하며, 충분한 크기의 메모리와 빠른 속도의 CPU 역시 필요하다. 제아무리 효율적인 인덱스 구조를 사용하더라도 충분한 하드웨어의 지원이 없다면 천만단위의 웹문서를 인덱싱하고 검색하는 것은 거의 불가능하다.
 
- 검색대상의 최소화
웹문서 검색엔진은 인터넷에 존재하는 모든 문서를 인덱싱하는 것을 목표로 할 수는 없다. 현재 한국의 대형 커뮤니티 한곳의 게시판에서 나오는 문서의 갯수만 해도 수백만개에 달하는데, 이런 문서들을 모두 인덱싱한다면 인덱스의 크기는 거의 무한정으로 커질 것이며, 인덱스를 검색하는 속도는 검색엔진으로서의 효용가치가 없는 수준까지 느려질 것이다. 그리고 인덱스의 크기가 커지면 커질수록 인덱스의 유지에도 많은 시간과 노력과 비용이 소모되게 마련이다. 그러므로 검색엔진의 효용성을 크게 훼손하지 않는 범위에서 인덱싱할 문서의 갯수를 최소화할 수 있는 방법이 필요하다. 여기에는 우선 사용자에게 유용한 문서에 관한 내부적인 정책을 세우고 그에 따라서 사용자에게 유용하다고 판단되는 문서만을 인덱싱하는 방법을 사용할 수 있으며 보조적으로 스팸문서, 중복문서, 유사문서, 내용이 없는 문서의 제거 또는 최소화를 하는 방법이 있겠다.
 
2. 정확한 랭킹시스템
현재 서비스되고 있는 대부분의 검색엔진은 기본적으로 사용자가 입력한 검색어와 일치하는 단어를 포함한 문서를 검색한다. 그리고 이런 매칭검색에 의한 검색결과를 내부적인 기준에 의해 결정된 정확도, 또는 중요도에 따라서 다시 정렬을 한 결과를 사용자에게 보여준다. 그런데 웹문서 검색엔진의 경우는 그 특성상 인덱싱하고 있는 문서가 매우 많기 때문에 보통 검색결과가 수만에서 수십만에 달하며, 대형 검색엔진이라면 수백만개의 검색결과를 출력하는 경우도 있다. 그러나 대부분의 경우에 있어서 사용자가 원하는 정보는 검색결과의 극히 일부에 지나지 않는다. 따라서 사용자에게 필요한 정보, 사용자가 원하는 정보를 검색결과의 상위에 출력할 수 있는 기능이 웹문서 검색엔진에서는 매우 중요하다. 실제적인 예를 들자면, 만약 사용자가 한국인이라면 대개의 경우 '야후'라는 단어로 검색을 하는 경우에는 kr.yahoo.com 이 최상위에 출력되는 것을 원할 것이고, '옥션'이라는 단어로 검색을 하는 경우에는 www.auction.co.kr 이 최상위에 출력되는 것을 원할 것이다. 그러나 현재 웹에 존재하는 문서 중에서 '야후', '옥션' 등의 단어를 포함한 문서는 헤아릴 수 없을 정도로 많으며 이들 검색어에 해당하는 웹문서 검색엔진의 검색결과 역시 엄청난 숫자이다. 이렇게 많은 검색결과에서 사용자가 원하는 검색결과인 kr.yahoo.com, www.auction.co.kr 을 최상위에 출력하려면 먼저 사용자에게 중요한 문서의 기준에 관한 올바른 정책과 그 정책을 구현한 랭킹시스템이 필요하다. 이때 랭킹시스템이란 사용자의 의도를 파악하는 인공지능이라는 식의 그 실체가 모호한 허황된 프로그램적 장치가 아니고 웹문서 내부에 존재하는 정보와 외부에 존재하지만 해당 문서와 관련있는 정보를 분석하고 그 정보를 토대로 내부적인 기준에 따라서 각 문서의 랭킹을 산출할 수 있는 일련의 논리적인 체계이다. 정확한 랭킹시스템을 구성하기 위해서는 다음과 같은 점을 고려할 수 있다.
 
 
 
- 검색어의 빈도수
검색어의 빈도수에 따라서 검색결과를 정렬하는 것은 매우 전통적인 방법이며, 대부분의 검색엔진에서 채택하고 있는 방법이다. 이 방법은 웹문서 검색엔진이 신뢰할 수 없는 영역을 검색한다는 점에서 많은 문제점을 갖고 있지만 아직까지도 무시할 수는 없는 방법이다. 실제로 어떤 문서에서 '야후'라는 단어가 많이 발견된다면 이 문서가 야후와 관련이 있다고 생각하는 것이 타당하다. 그러나 현재 인터넷에는 검색어의 빈도수 조작을 시도하는 문서가 많기 때문에 검색어의 빈도수를 랭킹에 반영할 수 있는 경우와 그렇지 않은 경우에 관한 제한을 설정하는 것이 필수이다. 실제로 많은 문서들이 웹문서 검색엔진에서의 랭킹을 조작하기 위해서 문서의 내용과는 아무런 관련이 없는 인기있는 검색어를 제목이나 본문에 나열하는 경우가 있다. 따라서 특정한 단어가 일정 횟수 이상 반복이 되는 경우 랭킹에 반영을 하지 않는다던가 하는 형태의 제한이 필요하다.
 
 
 
- 링크의 빈도수
링크의 빈도수를 랭킹에 반영하는 것은 구글의 페이지랭크 알고리즘 이후에 몇몇 검색엔진에서 채택하고 있는 방법인데, 이 방법의 요점은 보다 많이 링크가 되어 있는 사이트가 보다 인기가 있는 사이트라는 것이다. 비록 요즘에 들어서 이런 형태의 알고리즘을 역이용하려는 스팸문서가 많아지기는 했지만 링크의 빈도수의 조작이 검색어의 빈도수 조작보다 어렵다는 점에서, 링크의 빈도수는 아직도 웹문서 검색엔진의 랭킹시스템을 구성하는 데에 있어서 신뢰도가 높은 중요한 요소가 될 수 있다. 그러나 요즘에는 많은 사이트에서 스팸문서를 통해서 링크의 빈도수를 조작하려는 시도를 하기 때문에, 링크의 빈도수를 랭킹에 반영하려면 정당한 링크와 그렇지 않은 링크에 관한 정책을 만들고 이 정책에 따른 제한을 하는 것이 필요하다.
 
 
 
- 링크텍스트의 반영
링크텍스트란 하나의 문서에서 다른 문서를 지칭할 때의 텍스트를 말한다. 즉 kr.yahoo.com 문서의 제목에서 발견되는 '야후' 라는 단어보다 타 사이트에서 kr.yahoo.com 문서를 야후라는 이름으로 링크를 한 경우의 링크텍스트에서 발견되는 '야후'라는 단어가 보다 객관적이라고 판단할 수 있는데, 이 링크텍스트를 저장하고 인덱싱할 수 있다면 랭킹시스템에 매우 중요한 정도로 반영할 수 있을 것이다. 물론 요즘에는 이런 점까지 감안해서 스팸문서가 제작되지만 링크텍스트는 여전히 문서의 내부에서 발견되는 단어보다 신뢰도가 더 높다. 그러나 이런 링크텍스트를 반영하기 위해서는 우선 크롤러에 링크텍스트를 파싱하고 저장할 수 있는 기능이 있어야 하겠다.
 
 
 
- 스팸필터링
웹문서 검색엔진의 개발과 운영을 어렵게 하는 원인은 먼저 검색대상이 너무 많다는 것이며, 그 다음으로는 웹문서 검색엔진이 신뢰할 수 없는 영역을 검색한다는 것이다. 특히 신뢰할 수 없는 영역을 검색한다는 특성은 객관적이고도 신뢰할 수 있는 랭킹시스템을 구성하려는 시도에 가장 큰 난점으로 작용한다. 현재 웹에는 웹문서 검색엔진에서의 랭킹을 조작하기 위해서 갖가지 방법을 동원한 스팸문서가 난무하고 있는데, 요즘의 스팸문서는 날이 갈수록 더 교묘한 방법을 사용하여 랭킹조작을 시도하고 있다. 이런 신뢰할 수 없는 영역을 검색하는 검색엔진이 보다 신뢰할 수 있는 랭킹시스템을 구성하기 위해서는 먼저 스팸문서에 관한 내부적인 정책을 만들고 그 정책에 따른 스팸문서의 필터링을 통해서 웹문서 검색엔진의 검색대상의 신뢰도를 조금이나마 높이는 방법이 있겠다. 그러나 스팸필터링을 지나치게 강력하게 적용하는 경우에는 스팸문서가 아닌 엉뚱한 문서가 검색대상에서 제외되는 결과가 나오므로 적당한 정도의 스팸필터링을 적용하는 것 또한 중요하다.
 
 
 
 
3. 업데이트 속도
웹문서 검색엔진의 개발과 운영을 어렵게 하는 가장 큰 원인은 데이타가 너무 많다는 것이다. 현재 한국에서 경쟁력있는 웹문서 검색엔진을 서비스하려면 먼저 1천만개 이상의 웹문서를 인덱싱해야 한다. 그러나 1천만개 이상의 웹문서를 수집하고 인덱싱 하는 것은 그리 간단한 문제가 아니며 더욱 문제를 어렵게 하는 것은 웹이 계속해서 변화를 하고 있다는 것이다. 웹에서는 매일 수많은 문서가 추가되고, 변경되고, 삭제되고 있다. 그런데 웹문서 검색엔진이 웹의 변화를 즉각적으로 반영하지 못한다면, 많은 경우에 있어서 웹문서 검색엔진의 검색결과와 실제 웹문서의 정보가 일치하지 않을 것이며, 때로는 이미 삭제된 문서가 검색결과에 포함되는 경우도 나올 것이다. 하지만 현실적으로 웹의 변화를 즉각적으로 반영할 수 있는 웹문서 검색엔진을 만드는 것은 불가능한 일이다. 천만 단위의 문서를 수집하고 인덱싱하는 작업이라면 아무리 빠른 시스템을 사용한다고 하더라도 수시간내에 완료할 수는 없는 것이다. 따라서 현실적으로 웹문서 검색엔진은 웹의 변화를 즉각적으로 반영하는 것을 목표로 하기 보다는 인덱스의 업데이트 주기를 최소화하는 것을 목표로 해야 할 것이다. 업데이트 속도라는 축면에서 충분한 경쟁력을 갖춘 웹문서 검색엔진을 개발하기 위해서는 다음과 같은 점들을 고려할 수 있다.
 
 
 
- 부분 업데이트의 도입
웹문서 검색엔진의 데이타를 업데이트하는 방법으로 가장 단순한 방법은 전체 데이타를 새롭게 수집하고 인덱싱을 하는 풀업데이트이다. 그러나 1천만개 이상의 웹문서를 인덱싱하는 것을 목표로 하는 웹문서 검색엔진이라면, 아무리 빠르고 효율적인 시스템을 사용한다고 하더라도 풀업데이트 방식만으로는 업데이트 속도를 빠르게 하는 것에 한계가 있다. 그리고 풀업데이트를 하는 경우에도, 풀업데이트의 주기가 수일 이내라면 새롭게 수집된 웹문서의 대부분이 기존의 웹문서와 동일한 내용이므로, 웹의 변화를 반영하기 위해서 매번 풀업데이트를 하는 것은 시스템 자원의 낭비인 것이다. 따라서 웹문서 검색엔진의 업데이트 방법으로는 풀업데이트 이외에, 웹에 새롭게 추가되거나 내용이 변경된 문서만을 기존의 인덱스에 추가하거나 변경된 내용을 반영하는 부분 업데이트를 병행하여 사용하는 것이 좋다.
 
 
 
- 부분 업데이트가 가능한 인덱스 구조
원래 인덱스란 보통의 텍스트 자료를 검색이 용이한 구조로 변경을 한 것이며, 대개의 경우에는 여기에 검색속도를 향상시키기 위해서 정렬까지 된 구조이다. 그런데 웹문서 검색엔진의 경우 그 특성상 인덱스의 크기가 매우 크기 마련이다. 1천만개 이상의 웹문서를 인덱싱하는 경우, 물론 각 웹문서 검색엔진의 인덱싱 정책과 인덱스 구조에 따라서 결과가 조금씩 다르겠지만, 보통 그 인덱스의 크기가 수십기가바이트에 달하며 이런 정도 크기의 인덱스를 작성하는 데에는 많은 시간과 노력이 소모된다. 그런데 앞에서 말했다시피 인덱스란 대개의 경우 검색속도를 높이기 위해서 이미 정렬이 된 구조이다. 그리고 이미 정렬이 된 인덱스에 새로운 데이타를 추가 또는 삽입하기 위해서는 엄청난 크기의 데이타를 앞으로 밀고 뒤로 당기는 작업이 필요하다. 이것은 실제에 있어서는 인덱스를 다시 쓰는 작업이 필요하다는 것이다. 그러나 빠른 시간 내에 부분 업데이트가 가능하려면 이런 식으로 인덱스를 지우고 다시 쓴다는 방법은 매우 비효율적이다. 따라서 부분적인 변경을 빠르게 반영할 수 있는 인덱스 구조가 필요한 것이다.
 
 
 
- 부분 업데이트 대상의 최소화
인덱스의 부분적인 업데이트가 가능하다고 하더라도 웹문서 검색엔진이 웹의 추가되거나 변경된 내용을 모두 반영하는 것을 목표로 할 수는 없다. 웹에는 매일 수많은 문서가 추가되고, 변경되고, 삭제되는데 이런 웹의 변화를 무제한적으로 부분 업데이트에 반영한다면 부분 업데이트 대상이 되는 웹문서는 수백만개에 달할 수도 있으며 이것은 부분 업데이트의 속도를 크게 저하시킨다. 따라서 부분 업데이트 대상의 제한을 통해서 부분 업데이트 대상의 최소화를 하는 것이 필요하다. 부분 업데이트 대상의 최소화는 내부적으로 부분 업데이트에 반영할 문서와 그렇지 않은 문서에 관한 정책을 만들고 그 정책에 따라서 특정한 조건에 해당하는 웹문서만을 크롤링하고 인덱싱하는 방법으로 이루어질 수 있다. 보다 실제적인 예를 들자면, 대형 포탈사이트나 뉴스사이트와 같이 대부분의 사용자들에게 인기가 있으며, 매일 많은 정도의 업데이트가 이루어지는 사이트에서 추가되거나 변경되는 문서의 경우에는 부분 업데이트에 반영하는 것이 좋다고 가정할 수 있다. 
 
[색인기 구조] 
 
우선 색인 대상 데이타로 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를 그대로 사용해도 무방하겠지요.
 
그외의 모듈들은 사실 반드시 필요한 모듈들은 아닙니다. 필요에 의해 만들어 둘수도 있는 모듈들이라 설명은 하지 않겠습니다.
 
이상 간단한 색인기 구조였습니다. 끝.
 
[검색기 구조]
 
아무튼, 클라이언트에서 입력된 검색질의는 엔진에서 받아들이게 되면 맨 처음 질의분석기(Query Analayzer)라는 녀석이 받아들입니다. 그래서 유효한 검색질의인지, 유효하다면 엔진이 이해할 수 있는 방식으로 검색질의를 파싱한 후 어떤식으로 검색을 수행할지, 어떤 필드에서 검색을 할지, 키워드를 확장할지 등등을 결정하게 됩니다. 
 
결정이 되면 바로 연산기(calculator)로 파싱된 질의를 전달하여 질의에 대한 연산을 수행합니다. 이때 연산기는 자연어처리모듈, 논리연산 처리모듈, 숫자처리 모듈들을 내장하여 검색옵션에 맞게 결과를 계산하게 됩니다. 
 
연산기가 계산대상이 되는 데이타를 먼저 로딩하기 위해 파싱된 텀별로 index DB의 데이타를 읽기 위해 Retriever에게 질의를 던지게 되면 Retriever는 필요한 정보들을 index DB에서 로딩하여 연산기로 전달해 줍니다. 
 
연산기가 모든 연산을 마치게 되면 결과는 순위화된 문서들의?일련번호와 문서들의 랭킹점수등이 남게 됩니다. 이러한 내용들을 Stream Generator로 전달하게되고 Stream Generator는 최종 사용자가 확인할 수 있는 결과(제목, 본문, URL, 기타 부가정보등등)를 만들어서 다시 질의분석기 에게 돌려주게 됩니다.
 
그러면 질의분석기는 정해진 프로토콜에 맞게 Stream을 정리하여 클라이언트에 전달하게 되고 최종 검색결과를 클라이언트에서 마음대로 조작한 후 보여지게 됩니다.
 
 
 
 
 
 
 
 정태영 대강 훑어봤는데.. 역인덱스라고 하신 부분은.. fulltext index 라는 이름으로 여러 dbms 에서 구현되어 있습니다 :) 
 
임시테이블을 만들지 않기 자기자신과 left join 등을 하는 방식으로도 할 수 있겠구요.. 
 
더 간단하게는.. mysql 4.1 대로 올린다음에.. 인코딩을 utf8 로 사용하면.. fulltext index 에서 한글도 정상적으로 사용이 가능합니다 :) 그리고.. 구지 join 할 필요없이.. boolean fulltext search 를 하면 될 듯 하군요 ..
 
http://dev.mysql.com/doc/mysql/en/fulltext-search.html
이 링크를 참조해보시면 도움이 될 듯 싶습니다.. 02/07 6:34:23 
211.249.♡.51 
 
 정태영 아 그리고 하나 더.. mysql 등의 dbms 에서는.. sorting 을 위한 버퍼크기보다 큰 테이블을.. sort 하려 할 경우에는.. 외부의 파일을 사용해서 external sort 를 하게 됩니다.. 
 
그렇기 때문에.. /tmp 등 해당 dbms 에서 external sort 를 할 때 사용하는 임시 파일을 만드는 디렉토리를.. 메모리기반파일시스템으로 바꿔주면.. 큰 효과를 볼 수 있을 듯 싶군요.. 02/07 6:38:15 
211.249.♡.51 
 
 나개발자맞아? 태영님 말이 무슨 말인지..이해가/.. ^ ^; 02/07 10:09:21 
210.108.♡.206 
 
 jinyedge 글의 상당부분이 제가 작성한 글이군요.
상당부분이 제가 작성한 글이지만, 결국 제가 쓴 글이냐 하면
그것도 아니고..
난감하군요.
제 의도가 다르게 전달될 가능성이 있으니 제가 작성한 부분은
삭제해 주십시오.
그럼 이만.