우연히 주소를 잘못치고 들어간 곳이 낯뜨거운 성인사이트 거나 불법 파일공유 사이트, 도메인 장사하는 사이트 였던 기억이 가끔 있는데요. 이런 사이트가 검색결과에 등장하면 안되겠죠. 이런 스펨사이트를 걸러내는 방법에는 여러가지가 있지만 그 중에 한가지가 링크를 가지고 분석하는 방법 입니다.


사이트간의 링크를 그림처럼 그려놓고 찾아보면 변방에 자기들끼리 모여있는 그룹을 볼 수 있습니다. 어떤 경우 몇몇 사이트들 끼리 수만개 이상 링크를 교환해서 가지는 경우도 있습니다. 이 경우 대부분의 경우 스펨사이트들 입니다. 요즘 나오는 검색엔진들은 이런 기초적인 스펨은 대부분 걸러버리기 때문에 요즘에도 이런 방법으로 검색랭킹을 올리려는 시도는 별로 없지만, 그래도 꽤 남아 있습니다.

목표는 위그림의 빨간색 표시들을 찾는 겁니다. 이런 사이트를 찾으려면 어떻게 해야 할까요?

먼저 수많은 웹페이지로 부터 링크를 찾는 과정이 필요 합니다. 그리고 각 사이트간의 연결을 찾기 위하여 링크를 추상화 시켜야 겠죠. 제 경우 '링크 URL'의 'HOST' 부분만 찾아서 사용했습니다. 그럼 아래 그림과 같은 연결을 찾을 수 있습니다.


이 데이터(HostMap)를 기준으로 Rank 점수를 계산 했습니다. 각 Host마다 초기 10점의 점수를 가지고 있고, Outlink 갯수 만큼 나누어 주었습니다. 이런 방식으로 10번 이상 여러번 돌리면, 링크를 받는 Host는 점점 점수가 올라가게 됩니다. 페이지랭크와 비슷한 방법이죠. 여기에서 WhiteList(원래 유명한 믿을만한 사이트들)를 뺍니다.

이런방식으로 어느정도 상위분포를 잘라보면 별로 유명하지도 않으면서 지들끼리 수만개 이상 링크를 교환하는 스펨사이트가 나타나게 됩니다. 물론 국내외 검색엔진들은 이것보다 더 정교하고 똑똑한 방법을 사용합니다. 그리고 스펨사이트에는 여러가지 유형이 있는데 링크스펨은 그 중 한가지일 뿐이죠. ^^

1998년 경에 쓰여진 Mirror, Mirror on the Web: A Study of Host Pairs with Replicated Content라는 논문을 읽어 보았다.

미러사이트는 네트웍 트래픽을 줄이기 위하여 다른 컴퓨터 서버를 복사해 놓은 웹사이트 또는 컴퓨터 파일서버를 말하는데, 중복페이지가 존재하는 것과 다르게 미러사이트는 원사이트의 정확한 복제품을 말한다.

보통 다운로드 사이트의 경우 트래픽을 분산 시키기 위하여 미러사이트 들을 사용하는데, 논문에서 다루고 있는 내용은 미러로 운영되는 웹사이트를 구분하기 위한 방법을 말한다.여기에는 kangcom.com 이나 wowbook.com 처럼 같은 내용으로 포워딩되는 경우도 포함 될 수 있다.

논문의 아이디어는 여러개의 URL의 Path 유사도를 계산해 봐서 Path가 거의 비슷한 Host 들은 미러사이트라고 판단하는 방법이다. 미러사이트는 정확한 복제품 이므로 Path 구조도 동일하게 된다. 논문에서는 아래와 그림과 같은 방법으로 레벨을 나누어서 실험해 보았다.

 

논문의 결과보다는 실제 내가 실험해 볼 수 있는 URL 집합에 어느정도 효과가 있을지가 더 궁금 했으므로, 테스트를 해 본 결과, 미러사이트를 판단하는 정확도는 비교적 높았으나, 발견해 내는 비율이 좋지 않았다. 이유는 아래와 같았다.

• URL 집합이 각각의 Host 별로 고르게 분포되지 않았다. 예를 들어 Host A 와 Host B는 미러사이트 이지만 Host A의 URL은 10개 Host B의 URL은 1000개가 존재 한다면 비교할 대상은 10개 밖에 안된다.
• 블로그 툴이나 쇼핑몰 툴로 일괄적으로 만들어진 사이트, 각 지방별 정부단체 사이트 등 Path 구조가 거의 동일하고, 컨텐츠 내용도 그림 몇개만 빼고 거의 비슷한 경우는 판단하기가 꽤 힘들다. (정확도를 떨어뜨리는 주요 이유) 이 경우 굉장히 많은 숫자의 Host에서 높은 빈도수로 나오는 몇몇 Path를 제외하면 정확도가 꽤 높아진다.

논문의 내용대로 약간 보정해서 적용하면 정확도는 꽤 괜찮아서, 쓸만한 것 같았다. 그러나 (Host별로 고르지 않은 URL 분포 때문에) 발견해 내는 비율이 떨어지는 문제를 보완하기 위해서, 다른 방법을 병행할 필요가 있는 것 같다.

참고문헌:

Mirror, Mirror on the Web: A Study of Host Pairs with Replicated Content by Krishna Bharat and Andrei Broder

Nutch는 자바로 구현된 오픈소스 검색엔진 입니다. Lucene이 Indexer 와 Searcher로 구성되어 있고, Nutch는 Lucene에 없는 웹검색에 필요한 모든 기본요소를 전부 갖추어서 웹검색 용으로 확장 한 것이라고 보면 될 것 같습니다. 그래서 Nutch는 Lucene 기반의 공개 웹검색 엔진입니다. Nutch는 많은 부분 구글 검색 엔진 구조를 목표로 하고 있습니다.

전체적인 구조는 일반적인 웹검색 시스템의 구조와 비슷한 것 같습니다.

Nutch의 구조는 그림과 같은데, 이걸 지금 제가 알고 있는 웹검색 시스템의 구조로 이해하기 위해서 대충 나누어 보면 아래처럼 나눌 수 있을 것 같습니다.

1. Crawler
   • Nutch는 웹데이터 들을 효과적으로 가져올 수 있는 fetcher 들을 가지고 있습니다. 이를 통해서 목표로 하는 URL 들의 데이터를 수집하고, 이 작업은 목표로 하는 깊이까지 도착하면 멈춥니다.
2. Repository
   • 수집된 웹 데이터 들은 Repository에 저장됩니다. Nutch에서는 특별히 Repository 라는 명칭을 사용하지는 않지만, WebDB와 Segment들이 여기에 해당 한다고 볼 수 있을 것 같습니다.
3. Indexer
   • 수집된 데이터는 Lucene에서 사용 가능한 Index 형식으로 구성되어야 합니다.
4. Searcher
   • 구성된 Index는 Lucene Searcher 에서 사용됩니다.

몇일 뒤에 어떤 고마운 분이 Nutch의 구조나 특징에 대하여 조사 한것을 설명 해 주실텐데 Nutch가 어떻게 생긴건지 전혀 몰라서 간단히 살펴 보았습니다. 이제 어느정도 설명을 들을 만한 최소한의 기본 준비는 한 것 같으니 이제 기다려야 겠군요. ^^

참고문헌:

Introduction to Nutch, Part 1: Crawling by Tom White 2006/01/10 번역본

Introduction to Nutch, Part 2: Searching by Tom White 2006/02/16

Nutch: Open-Source Web Search Software by Doug Cutting(doug@nutch.org) 2004/11/26

Open Source Search by Doug Cutting(cutting@apache.org) 2005/12/05