제6장 웹 검색 엔진

2013. 11. 08

가천대학교 IT대학 컴퓨터미디어융합학과

Information Retrieval

제6장 웹 검색 엔진

6.1 소개

6.2 웹 검색 기법 6.3 웹검색 엔진 구조

6.4 사례연구: Google, Naver, Nutch

Why Web Search Engine?

Web Search Engine is power.

웹에는 매우 많은 정보가 있다.

모든 정보는 웹에 있다. Why?

약 100억 개 사이트,,,

정보가 너무 많아서 꼭 필요한 정보를 찾는 것이 과제,,

홍수가 날 때의 식수난과 같아,,

6.1 개요

인터넷 영역의 확장

산업 교육

의료

문화 군사

World Wide

Web

과학 오락

비정부

관광 환경

종교

예술

…

5

6.1 개요

웹 정보검색 ^의 정의

- 웹 사이트에서 원하는 정보를 가져오는 것.

- 인터넷 공간에 존재하는 다양한 형태의 자료들 중에서 원하는 정보를 찾는 과정.

- 인터넷에 산재한 정보를 미리 수집하고 체계적으로 저장한 후,

사용자가 원하는 정보를 찾아주는 데이터베이스 관리 시 스템.

6.1 개요

새로운 환경 변화

_{구 분 내 역}

인터넷 다양한 분야의 사이트들이 온라인으로 연결되어 정보 교환

분산처리 다운사이징에 의하여 다수의 서버들이 정보와 업무를 나누어 처리

병렬처리 처리율과 소요시간 향상을 위하여 다수의 처리기와 장비로 자료 처리

멀티미디어 문자 이외에 소리, 영상, 동영상 등의 다양한 정보 형태를 처리

6.1 개요

인터넷 정보의 특징

구분 내 역

1 분산되어 있으며 방대한 수량 2 비체계적이고 이질적

3 비 신뢰적인 정보 포함

4 최근 자료가 주류

6.1 개요

인터넷web 정보검색의 특성

구분 내 역

1 웹 사이트 수와 용량의 증가

2 정보검색을 위한 단어 선정 곤란

3 검색 결과가 너무 많아서 정확한 정보를 식별하기 곤란

4 사용자 수준에 맞는 내용 검색 곤란

6.1 개요

웹 정보검색의 중요성

내 역 비 고

변화 주도 웹에 의한 정보 교류와 의사소통이 사회 변화 주도

사업 규모 웹 정보검색은 수십억 달러 이상의 사업

광고,마케팅 인터넷은 광고와 마케팅의 새로운 기반

지적 재산권 등록상표와 지적재산법의 경계를 파괴

신규 사업 기술적 도전이 끝없이 계속

6.2 웹 검색 기법

웹 검색 기능의 분산

WWW

질의

요약 정보

색인 검색

URL 전달 URL 선택

정보 수집 색인 구축 검색 / 순위화 정보 요구

정보 검색

Crawler

정보 검색

6.2 웹 검색 기법

웹 정보검색 을 위한 기술

작 업 작 업 내 역 대표 기술

정보 수집 웹 사이트에서 유용한 정보를 수집 지능형 에이전트 기술

색인 구축 수집된 자료로 색인 데이터베이스 구축 색인 구축 기술

질의 처리 색인을 검색하고 결과를 순위대로 출력 문서 검색/순위화 기술

6.2 웹 검색 기법

웹 검색 엔진에서 색인의 역할

색인

대학 경가대학교 대학 경원대학교

대학

? 경기대학교

경원대학교

노인대학 URL

6.2 웹 검색 기법 웹 정보검색의 발전

세 대 세대별 특징 검색 사이트 비 고

1세대 디렉토리 검색 Yahoo

2세대 1세대 로봇 검색 Altavista, Hotbot, Excite 키워드 검색

2.5세대 디렉토리 + 로봇 검색 Naver, Daum, Paran

3세대 2세대 로봇 검색 Google

4세대 3세대 로봇 검색 Hakia, Qrobo, SearchMe 지식 검색 엔진

6.2 웹 검색 기법 정보검색 방식의 분류

검색 방법에 의한 분류

키워드 검색 메타형 검색

정보형태에 따른 분류

6.2 웹 검색 기법 정보검색 방식의 분류

순위화 기법 IR 알고리즘

용어 빈도, 용어 인접성, 용어 위치, 역문헌빈도수

BackLinks

사이트 인용 횟수에 따라 순위 부여. 구글이 선도

인기도 알고리즘

사이트 방문 빈도수에 따라 순위화

혼합방식

6.2 웹 검색 기법 검색 방식의 분류

분 류 특 징

주제별 검색 특정 주제별로 각 페이지를 분류하여 검 색

단어별 검색

일반 검색 단어를 입력하여 원하는 정보 검색 자연어 일반 문장으로 검색

메타 여러 검색 방식을 이용하여 검색

기타 전문 검색 특수 영역의 자료를 검색

6.2 웹 검색 기법 정보검색 방식의 분류

주요 엔진 형태의 비교

구분 디렉토리 키워드

자료 수집 사람 로봇

자료 내용 간단한 목록 정보 홈페이지 내용

장점

정선된 정보 많은 정보/큰 DB 주제별 분류 실제 내용(페이지 별) 적은 오류 자동 갱신

단점

작은 DB 기계적 주제 분류 간단한 목록 기계적 우선순위

갱신 작업 많은 오류

6.3 검색 엔진 구조

An Overview

6.3 검색 엔진 구조

웹검색 엔진 Web Search Engnie

정의:

- 웹 사이트에서 정보를 찾아주는 프로그램.

- 웹 사이트에 저장되어 있는 정보를 검색하는 프로그램.

- 웹에 있는 텍스트로 색인을 만들고 색인을 이용하여 질의에 응답하는 프로그램.

- 웹 사이트에 산재한 정보 중에서 간략한 정보(키워드 주소, 요약)만을 수집하고 사용자가 원하는 정보를 찾아주는 소프 트웨어.

6.3 검색 엔진 구조

검색 엔진의 구성 요소 Spider: corpus 구축

웹 사이트들을 방문하여 정보 수집

Catalog/Indexer : 역색인 생성

수집된 정보로 색인 구축: 다양한 정책

Search Engine: 질의 결과 서비스

Front end: 질의 재설정, 단어 스테밍, 대문자, 최적화,,

6.3 검색 엔진 구조

웹 검색 엔진의 특성

번호 구 분 내 역

1 품질 자료 미 편집: 누구나 자료 입력 가능, 2 정보 형태 다양한 분야의 여러 종류의 자료

3 사용자 다양한 분야의 다양한 수준 (초보자, 일반인, 전문가)

4 규모 수 억 번의 검색과 수십억 개의 문서

6.3 검색 엔진 구조

웹 검색 질의의 특성

번호 구 분 내 역

1 질의 크기 짧다:

한 개 또는 두 개 또는 세 개의 단어로 구성

2 크기 증가 초기 검색 이래 약 1.7배 증가

3 사용자 기대 가장 원하는 결과가 첫 번째 줄에 나타나기

6.3 검색 엔진 구조

검색 엔진의 주요 기능

기 능 주요 처리 내역 프로그램/저장소

자료 수집 웹 사이트에서 정보를 수집하여 검색 사 이트로 전송. Repository에 저장.

Crawler /텍스트 DB 용어 추출 웹 로봇이 보내주는 정보에서 용어를 추

출하고 정리 Indexer

/Index DB 용어 저장 추출된 용어를 색인 데이터베이스에 저

장

사용자 검색 사용자 질의를 데이터베이스 질의로 변

환하고 실행 Searcher

/temp DB

순위 알고리 원하는 정보와 가장 유사한 순서대로 정

자료 수집

색인 구축 IR System

Documents Index Database

색인 검색 색인 구축

사용자 질의

검색 결과

검색 서버

역색인 생성

DocIds 자료

(중복 수집

제거, 자료 분류) 자료 저장소

Inverted index

crawl

web

(a) 웹 검색 엔진의 자료 흐름

사용자 질의

검색 엔진

6.3 검색 엔진 구조

Web Search Engine의 구조와 기능

6.3 검색 엔진 구조

Web Search Engine 구조

정보수집부(외부) + 정보탐색부 (내부)

World Wide

Web Query

Web search engine

Searcher

Crawler

Indexer

Crawler

Crawler Result

Repository

Search Ranking

1

2 3

6.3 검색 엔진 구조

Web Crawler의 정보 수집 방법

- 알려진 사이트부터 검색을 시작한다.

- 정보들을 기록한다.

- 각 사이트로부터 링크를 따라서 사이트를 순회한다.

- 새로운 사이트에서 발견된 정보를 기록한다.

- 앞의 동작을 주기적으로 반복한다.

6.3 검색 엔진 구조

Web Crawler의 정보 수집 알고리즘

Insert a set of known sites on a queue Repeat

큐에서 첫 페이지 추출

이 페이지가 전혀 처리되지 않았다면 다음 루틴을 수행한 다

이 페이지에서 발견된 정보를 기록한다

- 단어의 위치와 밖으로 나가는 링크 큐의 현재 페이지 위에 각 링크를 추가 입력한다 이 페이지가 처리된 것을 기록한다

Until

6.3 검색 엔진 구조

역색인 구축

문서 1: A DBMS contains simple tied records.

문서 2: Each record is simply linked by linking names.

불용어 제거  어간 추출  용어 목록 작성  용어 목록 정 렬

용어 목록 ^{용어 DBMS contain simple tie record record simple link link name}

문서# 1 1 1 1 1 2 2 2 2 2

6.3 검색 엔진 구조

역색인 구축

용어 빈도수 목록

어휘 목록(lexicon)

용어 contain DBMS link link name record record simple simple tie

문서# 1 1 2 2 2 1 2 1 2 1

빈도수 1 1 2 2 1 1 1 1 1 1

용어 contain DBMS link name record simple tie

문서 수 1 1 1 1 2 2 1

전체 빈도수 1 1 2 1 2 2 1

6.3 검색 엔진 구조

역색인 파일 구조

용어 문

서#

빈도 수 contain 1 1

DBMS 1 1

link 2 2

name 2 1

record 1 2 record 2 2 simple 1 2 simple 2 2

용어 문서

수

전체 빈도수 contain 1 1

DBMS 1 1

link 1 2

name 1 1

record 2 2 simple 2 2

tie 1 1

link 2 2

문 서#

빈도 수

1 1

1 1

2 2

1 1

2 1

1 1

2 1

2 1

2 1

Dictionary/Lexicon

Postings ptr

Doc 1

Doc 2 문서

용어 빈도수 파일 어휘목록 집합

ptr

31

6.3 검색 엔진 구조

Web Crawler

- 탐색을 시작하는 곳에서 root URL의 종합적인 집합으로 시 작

- 이들 페이지의 모든 링크들을 순환적으로 추적하여 부수적 인 페이지들을 찾는다.

- 새로 찾은 모든 페이지들을 역 색인에 색인화한다.

- 사용자들에게 색인화할 페이지들을 직접 제출하도록 허용.

- 시간 소모형 작업: 중복을 회피해야 - 다수의 open-source 가능

- 페이지 소유자의 규칙에 따라야

6.3 검색 엔진 구조

Web Crawler의 탐색 전략

BFS, DFS - BFS:

전 단계의 모든 노드들의 주소를 기억해야 -DFS:

깊이를 따라 한 노드의 주소만 기억

6.3 검색 엔진 구조

Web search engine의 전형적인 구조

Repository

검색 Server Indexer

Parser

형태소분석기

Stemmer

Inverted Index

질의분석기

World Wide

Web Filter

크롤러 브

로 커

질의 검색

수집

URL 정보

Searcher

크롤러

크롤러

형태소분석기

6.3 검색 엔진 구조

검색엔진 구성요소(1)

웹검색엔진 interface

Web Robot: 웹 문서 검색

Broker: 다양한 컬렉션을 하나의 질의로 검색하고 취합.

Repository, Collection : 색인용 자료 저장 검색 대상이 되는 집합

Indexer: 색인어 추출, 색인 구축 Parser: 구문분석

Morpheme 형태소분석기: 키워드 추출

6.3 검색 엔진 구조

검색엔진 구성요소(2)

사용자검색 Interface

Query Analyzer: 사용자 질의를 DB 질의로 변환 Parser: 구문분석

Searcher: 검색 모델에 의거하여 유사 문서 추출

Summarizer: 문서 핵심 내용을 간결한 문장으로 축약 Filters: 다양한 형식의 문서들에서 텍스트 추출 목적 Ranker: 검색결과의 순위부여

중복제거기: 검색결과 중에서 중복 제거

Previewer: 웹사이트 방문 이전에 자체 DB에서 미리 보여주기

6.3 검색 엔진 구조

검색 엔진 설계 요건

0: 속도: 대상 서버: 60억 개 URL,

속도: 백만 문서 당 0.5초 이내

3: 용어 가중치: 문서 빈도수 파악 곤란

4: 다양한 문서: 크기로 인하여 벡터 공간 모델은 부적합 5: 색인 갱신: 지속적이어야

6.4 사례연구

6.4.1 검색 엔진 사례 Google

제작자:

Larry Page, Sergey Brin

특징

PageRank: 하이퍼링크의 빈도수로 우선순위 부여 가장 방대한 색인 보유

검색 속도 신속 & 30개 언어로 검색 검색 로봇이 연관성 순으로 검색 동의어 검색

웹 페이지를 캐시에 저장

Links

Anchor

Repository Indexer

Internet Indexer

Crawler

Inverted File URL

Server 문서

정보

compress

sort

pagerank URL Resolver

Forward Index file

6.4 사례연구

Google의 엔진 구조

6.4 사례연구

Google 엔진의 특징

순서 내 역 비 고

1 크롤러 강력한 성능으로 모든 정보 수집 2 분산․병렬처리 병렬처리 서버의 분산 배치

3 색인 정보검색용 전문 색인 구조

4 페이지랭크 앵커 텍스트를 이용한 사이트 평가

6.4 사례연구

Google의 URL 서버

index

검색 서버

index

검색 서버

index

검색 서버

index

검색

서버 index

검색 서버

index

검색 서버

index

검색 서버

index

검색 서버

검색 서버

index

검색 서버

index

검색

index 서버 검색 서버

6.4 사례연구

Google : URL 서버와 크롤

색인의 생성과 역할

구조 해석

단어 처리

링크 처리 단어 정보

문서 정보 링크 정보

링크 정보 문서 정보 단어 정보 색인

Repository

인터넷 크롤러

크롤러

문서 정보 압 크롤러 축 URL

서버

URL (역색인)

6.4 사례연구

Google : 웹 페이지의 구조 해

<html>

<head>

<title>경원대학교 홈페이지</title>

</head>

<body>

<h1>경원대학교</h1>

docID 1

url Http://kyungwon

경원대학교 우리 경원대학교에서는….

title 경원대학교 홈페이지

기타 ...

6.4 사례연구

Google : worldID 생성

경원대학교

우리 경원대학교에서는….

301 101

102 201 101 202 ...

단어 wordID 대학교 101

우리 102

의 201

에서는 202 경원 301

Lexicon

6.4 사례연구

Google : 색인에 등록되는 자료

docID wordID 위치 크기 기타

1 301 0 2

1 101 1 2

1 102 2 2

1 201 3 1

1 101 4 2

6.4 사례연구

Google : 색인의 구조

Barrels

docID wordID# 위치 #1 크기 #1 기타 #1 위치 #1 크기 #1 기타 #1 docID wordID# 위치 #1 크기 #1 기타 #1 위치 #1 크기 #1 기타 #1

Barrels

1 101 1 2

4 2

102 2 2

201 3 1

색인의 실제 자료

6.4 사례연구

Google : 역색인의 구조

실제 자료

Barrels

wordID# docID 위치 #1 크기 #1 기타 #1 위치 #1 크기 #1 기타 #1 wordID# docID 위치 #1 크기 #1 기타 #1 위치 #1 크기 #1 기타 #1

Barrels

101 1 1 2

1 4 2

102 1 2 2

검색 서버

docIndex Barrel 단어 wordID

대학 101 Lexicon

wordID docID

101 1

역색인

docID wordID

1 경원대학교

2 승가대학

색인 대학?

1 2

3

4

5 6

1. 경기대학교 2. 경원대학교

..

사용자

6.4 사례연구

Google 엔진의 검색 흐름

1: 검색 요청

2: 단어 ID 검색

3: 문서 ID 검색

4: 자료 정렬

5: 정보 추출

6: 결과 제공

6.4 사례연구

Google : Page Rank 알고리즘

150 30

70 3 50

... 90 1

70 2

) 100

(

= + + + = + + =

T₁

T₂

A

100

150 70

50

50 70

100

30 10

30 30

6.4 사례연구

Google의 장단점

순서 장 점 단 점

1 강력한 웹 로봇 기계적 검색

2 수퍼 컴퓨터 운용 가끔 검색되는 낡은 자료 3 페이지 랭크/앵커 텍스트 검색 결과의 비분류

4 공정한 검색 결과 사용자 데이터베이스 취약

5 완전 자동화 저작권 침해

6 타 사이트와 상생

6.4 사례연구

6.4.2 검색 엔진 사례: Naver

1997년 11월 NHN사에서 서비스 시작.

삼성SDS의 사내 벤처로 시작.

특징

14개 주제별 키워드형 검색 엔진.

디렉토리와 키워드 혼합형.

12가지 연산자와 복합명사 분석 기능 형태소 분석기: 한글/한자, 영어 처리 자연어 검색

Web Crawler

6.4 사례연구

Naver 엔진의 구조

index document query

result

document query

document

Document Analyzer Query

Processor

Storage Manager

Index Database

Repository

World Wide

Web Document

Loader

Nabot

(HTML)

사용자

6.4 사례연구

6.4.2 Naver

네이버 엔진의 특성

순서 내 역 비 고

1 방대한 데이터베이스 다양한 DB와 사용자 참여

2 통합 검색 다양한 검색 분야의 통합

3 이슈 검색 사용자 관심 사항 반영

6.4 사례연구

6.4.2 Naver

네이버 엔진의 장단점

순서 장 점 단 점

1 다양한 데이터베이스 타 사이트와 상생 2 통합 검색 해외 진출 능력

3 사용자 친화형 이슈 검색 검색 결과의 공정성

4 편리한 데이터베이스 검색 결과의 부족

6.4 사례 연구

6.4.3 검색 엔진 사례: Lucene과 Nutch

java로 만든 저수준의 문자 색인 라이브러리와 API

Nutch:

Lucene을 기반으로 java로 만든 오픈 소스 검색 엔진

Lucene 라이브러리의 특징

순서 내 역 비 고

1 계층화된 검색 구절 및 키워드 일치

2 유연한 질의 구절이나 와일드카드

6.4 사례 연구

6.4.1 Nutch 엔진의 자료 흐름

질의 접수 결과 제공 File

System

web

Index

사용자

Lucene Application

Index

Documents Search Index 자료 수집

Crawler

직접 등록 Database

6.4 사례 연구

6.4.3 검색 엔진 사례: Lucene과 Nutch Nutch 엔진의 핵심 기능

순서 내 역 비 고

1 구문분석 처리 다수의 상이한 컨텐츠 형식

2 색인 구축 대용량

3 크롤러 정보 수집

4 수집 콘텐츠 관리 상이한 프로토콜 지원

6.4 사례 연구

6.4.3 검색 엔진 사례: Lucene과 Nutch Nutch 엔진의 특징

순서 내 역 비 고

1 Lucene 기반 Java로 작성

2 확장성 추가 모듈의 plugin 가능 3 로봇 기능 크롤러 기능이 풍부

4 프로그램 강건성 Lucene의 안전성

5 검색 결과 중요한 결과를 처음으로

6.4 사례연구

Nutch 엔진의 구조

Plugin Framework

URLFilter Framework

Crawler (Fetcher)

Protocol Framework

Scoring Framework

Parsing Framework

Indexing Framework

parse-html plugin protocol-

http plugin

Web UI Data Store

Component 범례

6.4 사례연구

6.4.3 기존 검색엔진과 Web Search Engine의 비교

Web: 분산식, 기존 IR: 집중식

- 문서의 수, 사용자, 빈도수 :

- Web :

Dynamic & heterogeneous than IR

HTML로 구조화, IR: Plain Text

WWW search engine > 기존 IR

국내 검색엔진 순위

1. Naver: 66.65%

2. Daum: 23.00

3. Google: 4.37

4. Nate: 3.36

5. Yahoo: 1.75

by 비즈스프링(구자훈)

6.4 사례연구

정보검색 엔진의 순위

기호,

미국 검색엔진 순위

1. Google: 64.4%

2. Yahoo: 17.7

3. Microsoft : 11.6

4. ASK: 3.7

5. AOL LLC: 2.4%

세계 검색엔진 순

위

1. Google: 76%

2. Yahoo: 6.9

3. Baidu: 7.9

4. MS: 3.3

5. Naver: 1.5

6. eBay: 1.2

61

6.5 요점 정리

웹 정보검색

웹 사이트에서 원하는 정보를 가져오는 것.

인터넷 정보의 특징

분산, 대량, 비체계적, 이질적 자료, 비신뢰적, 최근 자료

변화주도, 사업규모, 광고 마케팅, 지적 재산권, 신규 사업, 문화 욕구

웹 검색 기능의 분산

인터넷, 색인 서버, 검색 서버, 사용자 웹 정보검색을 위한 기술

정보 수집, 색인 구축, 질의 처리

62

6.5 요점 정리

웹 정보검색의 발전

세대별 발전단계: 1, 2, 2.5, 3, 4세대 웹 정보검색 엔진의 분류

주제형, 키워드형, 메타형 모음형 검색 엔진 웹 검색엔진의 주요 기능

자료 수집, 용어 추출, 용어 저장, 사용자 검색, 순위처리 역 색인의 구조

색인 파일, 포스팅 파일, 문서 집합

6.5 요점 정리

Google 엔진의 특징

크롤러, 분산/병렬처리, 색인, 페이지랭크

PageRank 알고리즘

많이 참조되는 사이트, 페이지일수록 중요하다.

Google의 장점

강력한 웹 로봇, 수퍼 컴퓨터 운용, 페이지 랭크/앵커 텍스트, 공정한 검 색 결과, 완전 자동화, 타 사이트와 상생, 무료의 고가 정보

단점

: 기계적 검색, 가끔 검색되는 낡은 자료, 검색 결과의 비분류, 사용

자 데이터베이스 취약, 저작권 침해

6.5 요점 정리

Naver의 장점

다양한 데이터베이스, 통합 검색, 사용자 친화형 이슈 검색, 편리한 데이 터베이스

단점

타 사이트와 상생, 해외 진출 능력, 검색 결과의 공정성, 검색 결과의 부 족

Nutch 엔진의 특징

Lucene기반, 확장성 , 로봇 기능, 프로그램 강건성, 검색 결과, 색인 기

능

6.5 익힘 문제

두 문제를 풀어서 제출하시오.

6.5 익힘 문제

주요 수식