Database Applications - 멀티미디어 데이터베이스 – 제6장 텍스트 색인과 검색

Size: px

Start display at page:

Download "Database Applications - 멀티미디어 데이터베이스 – 제6장 텍스트 색인과 검색"

원중 시
5 years ago
Views:

1 情報檢索 Information Retrieval 가천대학교 IT 대학 컴퓨터미디어융합학과

2 목차 6.1 소개 6.2 웹검색기법 6.3 웹검색엔진구조 6.4 사례연구 : Google, Naver, Nutch 익힘문제

3 Why Web Search Engine? Web Search Engine is power. 웹에는매우많은정보가있다. 모든정보는웹에있다. Why? 약 100억개사이트,,, 정보가너무많아서꼭필요한정보를찾는것이과제,, 홍수가날때의식수난과같아,, 3

4 6.1 개요 인터넷영역의확장 종교 비정부 교육 산업 예술 과학 World Wide Web 오락 의료 관광 환경 문화 행정 정치 군사 4

5 6.1 개요 웹정보검색의정의 - 웹사이트에서원하는정보를가져오는것. - 인터넷공간에존재하는다양한형태의자료들중에서원하는정보를찾는과정. - 인터넷에산재한정보를미리수집하고체계적으로저장한후, 사용자가원하는정보를찾아주는데이터베이스관리시스템. 5

6 6.1 개요 새로운환경변화 구분 인터넷 내역 다양한분야의사이트들이온라인으로연결되어정보교환 분산처리 다운사이징에의하여다수의서버들이정보와업무를나누어처리 병렬처리 처리율과소요시간향상을위하여다수의처리기와장비로자료처리 멀티미디어 문자이외에소리, 영상, 동영상등의다양한정보형태를처리 지능형 인공지능에이전트를이용하여분산작업처리 6

7 6.1 개요 인터넷정보의특징 구분 내역 1 분산되어있으며방대한수량 2 비체계적이고이질적 3 비신뢰적인정보포함 4 최근자료가주류 7

8 6.1 개요 인터넷 web 정보검색의특성 구분 내역 1 웹사이트수와용량의증가 2 정보검색을위한단어선정곤란 3 검색결과가너무많아서정확한정보를식별하기곤란 4 사용자수준에맞는내용검색곤란 8

9 6.1 개요 웹정보검색의중요성 내역 비고 변화주도 웹에의한정보교류와의사소통이사회변화주도 사업규모광고, 마케팅지적재산권신규사업문화욕구 웹정보검색은수십억달러이상의사업인터넷은광고와마케팅의새로운기반등록상표와지적재산법의경계를파괴기술적도전이끝없이계속경제성장에따르는문화적욕구의증대 9

10 6.2 웹검색기법 웹검색기능의분산 정보수집색인구축검색 / 순위화 정보요구정보검색 Crawler 색인검색 질의 WWW 요약정보 URL 전달 정보검색 URL 선택 인터넷 색인서버 검색서버 사용자 10

11 6.2 웹검색기법 웹정보검색을위한기술 작업작업내역대표기술 정보수집웹사이트에서유용한정보를수집 지능형에이전트기술 색인구축수집된자료로색인데이터베이스구축색인구축기술 질의처리색인을검색하고결과를순위대로출력문서검색 / 순위화기술 11

12 6.2 웹검색기법 웹검색엔진에서색인의역할 대학? 경기대학교 경원대학교 색인 노인대학 대학 경가대학교 URL 대학 경원대학교 URL 대학대학 노인대학승가대학 URL URL 승가대학 12

13 6.2 웹검색기법웹정보검색의발전 세대세대별특징검색사이트비고 1 세대디렉토리검색 Yahoo 2 세대 1 세대로봇검색 Altavista, Hotbot, Excite 키워드검색 2.5 세대디렉토리 + 로봇검색 Naver, Daum, Paran 3 세대 2 세대로봇검색 Google 4 세대 3 세대로봇검색 Hakia, Qrobo, SearchMe 지식검색엔진 13

14 6.2 웹검색기법정보검색방식의분류 검색방법에의한분류디렉토리검색키워드검색메타형검색 정보형태에따른분류서지검색 ( 요약문 ) 전문검색사실검색 14

15 6.2 웹검색기법정보검색방식의분류 순위화기법 IR 알고리즘용어빈도, 용어인접성, 용어위치, 역문헌빈도수 BackLinks 사이트인용횟수에따라순위부여. 구글이선도인기도알고리즘사이트방문빈도수에따라순위화혼합방식기존방식 + Backlinks 15

16 6.2 웹검색기법검색방식의분류 분류주제별검색일반검색단어별자연어검색메타기타전문검색 특징 특정주제별로각페이지를분류하여검색 단어를입력하여원하는정보검색 일반문장으로검색 여러검색방식을이용하여검색 특수영역의자료를검색 16

17 6.2 웹검색기법정보검색방식의분류 주요엔진형태의비교 구분 디렉토리 키워드 자료수집 사람 로봇 자료내용간단한목록정보홈페이지내용 장점 단점 정선된정보 많은정보 / 큰 DB 주제별분류 실제내용 ( 페이지별 ) 적은오류 자동갱신 작은 DB 기계적주제분류 간단한목록 기계적우선순위 갱신작업 많은오류 17

18 6.3 검색엔진구조 An Overview 18

19 6.3 검색엔진구조 웹검색엔진 Web Search Engnie 정의 : - 웹사이트에서정보를찾아주는프로그램. - 웹사이트에저장되어있는정보를검색하는프로그램. - 웹에있는텍스트로색인을만들고색인을이용하여질의에응답하는프로그램. - 웹사이트에산재한정보중에서간략한정보 ( 키워드주소, 요약 ) 만을수집하고사용자가원하는정보를찾아주는소프트웨어. 19

20 6.3 검색엔진구조 검색엔진의구성요소 Spider: corpus 구축웹사이트들을방문하여정보수집 Catalog/Indexer : 역색인생성수집된정보로색인구축 : 다양한정책 Search Engine: 질의결과서비스 Front end: 질의재설정, 단어스테밍, 대문자, 최적화,, Back end: 정합문서탐색및결과순위화 20

21 6.3 검색엔진구조 웹검색엔진의특성 번호구분내역 1 품질자료미편집 : 누구나자료입력가능, 2 정보형태다양한분야의여러종류의자료 3 사용자 다양한분야의다양한수준 ( 초보자, 일반인, 전문가 ) 4 규모수억번의검색과수십억개의문서 21

22 6.3 검색엔진구조 웹검색질의의특성 번호구분내역 1 질의크기 짧다 : 한개또는두개또는세개의단어로구성 2 크기증가초기검색이래약 1.7 배증가 3 사용자기대가장원하는결과가첫번째줄에나타나기 22

23 6.3 검색엔진구조 검색엔진의주요기능 기능주요처리내역프로그램 / 저장소 자료수집 용어추출 용어저장 사용자검색 순위알고리즘 웹사이트에서정보를수집하여검색사이트로전송. Repository 에저장. 웹로봇이보내주는정보에서용어를추출하고정리추출된용어를색인데이터베이스에저장사용자질의를데이터베이스질의로변환하고실행원하는정보와가장유사한순서대로정렬하는프로그램 Crawler / 텍스트 DB Indexer /Index DB Searcher /temp DB 23

24 6.3 검색엔진구조 DocIds Web Search Engine 의 구조와기능 사용자질의 자료저장소 역색인생성 자료수집 ( 중복제거, 자료분류 ) crawl web 검색결과 검색서버 Inverted index (a) 웹검색엔진의자료흐름 색인검색 검색엔진 색인구축 사용자질의 검색결과 IR System Index Database Documents Corpus 자료수집 색인구축 검색서버색인서버자료서버 검색프론트엔드 검색백엔드 Internet (b) 검색엔진의두가지기능 24

25 6.3 검색엔진구조 Web Search Engine 구조정보수집부 ( 외부 ) + 정보탐색부 ( 내부 ) Web search engine Query Result Searcher Search 3 Repository 1 Crawler World Wide Web Crawler Ranking Indexer 2 Crawler Index database 25

26 6.3 검색엔진구조 Web Crawler의정보수집방법 - 알려진사이트부터검색을시작한다. - 정보들을기록한다. - 각사이트로부터링크를따라서사이트를순회한다. - 새로운사이트에서발견된정보를기록한다. - 앞의동작을주기적으로반복한다. 26

27 6.3 검색엔진구조 Web Crawler 의정보수집알고리즘 Insert a set of known sites on a queue Repeat 큐에서첫페이지추출이페이지가전혀처리되지않았다면다음루틴을수행한다이페이지에서발견된정보를기록한다 - 단어의위치와밖으로나가는링크큐의현재페이지위에각링크를추가입력한다이페이지가처리된것을기록한다 Until 27

28 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 문서 # 용어목록정렬 용어 contain DBMS link link name record record simple simple tie 문서 #

29 6.3 검색엔진구조 역색인구축용어빈도수목록 용어 contain DBMS link link name record record simple simple tie 문서 # 빈도수 어휘목록 (lexicon) 용어 contain DBMS link name record simple tie 문서수 전체빈도수 두테이블로부터포스팅파일구축 29

30 6.3 검색엔진구조 역색인파일구조 용어빈도수파일용어문빈도서 # 수 contain 1 1 DBMS 1 1 어휘목록용어문서전체수빈도수 contain 1 1 DBMS 1 1 ptr Postings 문빈도 ptr 서 # 수 문서집합 Doc 1 link 2 2 link link 2 2 name name 2 1 record 1 2 record 2 2 record 2 2 simple 2 2 tie Doc 2 simple 1 2 simple 2 2 Dictionary/Lexicon tie

31 6.3 검색엔진구조 Web Crawler - 탐색을시작하는곳에서 root URL의종합적인집합으로시작 - 이들페이지의모든링크들을순환적으로추적하여부수적인페이지들을찾는다. - 새로찾은모든페이지들을역색인에색인화한다. - 사용자들에게색인화할페이지들을직접제출하도록허용. - 시간소모형작업 : 중복을회피해야 - 다수의 open-source 가능 - 페이지소유자의규칙에따라야 31

32 6.3 검색엔진구조 Web Crawler의탐색전략 - 주요두전략 BFS, DFS - BFS: 전단계의모든노드들의주소를기억해야 -DFS: 깊이를따라한노드의주소만기억쓰레드상실우려 32

33 6.3 검색엔진구조 Web search engine 의전형적인구조 Indexer 형태소분석기 Parser Stemmer Filter URL 정보 Repository 브로커 크롤러 크롤러 크롤러 수집 검색 World Wide Web Inverted Index 형태소분석기 Searcher 질의분석기 검색 Server 질의 중복제거기 Ranker Parser 요약기 결과 사용자 33

34 6.3 검색엔진구조검색엔진구성요소 (1) 웹검색엔진 interface Web Robot: 웹문서검색 Broker: 다양한컬렉션을하나의질의로검색하고취합. Repository, Collection : 색인용자료저장검색대상이되는집합 Indexer: 색인어추출, 색인구축 Parser: 구문분석 Morpheme 형태소분석기 : 키워드추출 Stemmer: 어근추출 Database: Index, Inverted File 34

35 6.3 검색엔진구조검색엔진구성요소 (2) 사용자검색 Interface Query Analyzer: 사용자질의를 DB 질의로변환 Parser: 구문분석 Searcher: 검색모델에의거하여유사문서추출 Summarizer: 문서핵심내용을간결한문장으로축약 Filters: 다양한형식의문서들에서텍스트추출목적 Ranker: 검색결과의순위부여중복제거기 : 검색결과중에서중복제거 Previewer: 웹사이트방문이전에자체 DB에서미리보여주기 35

36 6.3 검색엔진구조 검색엔진설계요건 0: 속도 : 대상서버 : 60억개 URL, 속도 : 백만문서당 0.5초이내 1: 방대한어휘. 20억개이상의용어 2: 도메인지식 : 이용곤란 3: 용어가중치 : 문서빈도수파악곤란 4: 다양한문서 : 크기로인하여벡터공간모델은부적합 5: 색인갱신 : 지속적이어야 6: 검색엔진 : 강건해야 36

37 6.4 사례연구 검색엔진사례 Google 제작자 : Larry Page, Sergey Brin 특징 PageRank: 하이퍼링크의빈도수로우선순위부여가장방대한색인보유검색속도신속 & 30개언어로검색검색로봇이연관성순으로검색동의어검색웹페이지를캐시에저장 HTTP의머리글정보를보고약 20개국언어로자동설정 37

38 6.4 사례연구 Google 의엔진구조 문서정보 URL Server Crawler Indexer URL Resolver Anchor compress Indexer Repository Links Internet pagerank Forward Index file sort Inverted File Searcher Web Server Forward index: key 에의한색인 Inverted index: 내용에의한색인 38

39 6.4 사례연구 Google 엔진의특징 순서 내역 비고 1 크롤러 강력한성능으로모든정보수집 2 분산 병렬처리 병렬처리서버의분산배치 3 색인 정보검색용전문색인구조 4 페이지랭크 앵커텍스트를이용한사이트평가 39

40 6.4 사례연구 Google 의 URL 서버 index 검색서버 index 검색서버 index 검색서버 index 검색서버 검색서버 index index 검색서버 검색서버 index 검색서버 index index 검색서버 검색 index 서버 검색서버 index 검색서버 index 40

41 6.4 사례연구 Google : 러 URL 서버와크롤 크롤러 URL 서버 크롤러 인터넷 문서정보 압축 크롤러 색인의생성과역할 구조해석 URL ( 역색인 ) Repository 색인 단어처리 링크처리 링크정보 문서정보 단어정보문서정보링크정보단어정보 저장소 랭킹 색인생성 41

42 6.4 사례연구 Google : 웹페이지의구조해석 <html> <head> <title> 경원대학교홈페이지 </title> </head> <body> <h1> 경원대학교 </h1> docid 1 url 경원대학교 우리경원대학교에서는. title 경원대학교홈페이지 기타... DocIndex URLlist docid url title 기타정보 url docid 42

43 6.4 사례연구 Google : worldid 생성 경원대학교우리경원대학교에서는 Lexicon 단어 wordid 대학교 101 우리 102 의 201 에서는 202 경원

44 6.4 사례연구 Google : 색인에등록되는자료 docid wordid 위치 크기 기타

45 6.4 사례연구 Google : 색인의구조 Barrels docid wordid# 위치 #1 크기 #1 기타 #1 위치 #1 크기 #1 기타 #1 docid wordid# 위치 #1 크기 #1 기타 #1 위치 #1 크기 #1 기타 #1 색인의실제자료 Barrels

46 6.4 사례연구 Google : 역색인의구조 Barrels wordid# docid 위치 #1 크기 #1 기타 #1 위치 #1 크기 #1 기타 #1 wordid# docid 위치 #1 크기 #1 기타 #1 실제자료 위치 #1 크기 #1 기타 #1 Barrels

47 6.4 사례연구 Google 엔진의검색흐름 1: 검색요청 2: 단어 ID 검색 3: 문서 ID 검색 4: 자료정렬 5: 정보추출 6: 결과제공 Lexicon 2 단어 wordid 대학 101 대학? 3 Barrel 역색인 wordid docid 사용자 6 검색서버 4 1. 경기대학교 2. 경원대학교 3. 승가대학 5 docid wordid 1 경원대학교 2 승가대학 docindex 색인.. 47

48 6.4 사례연구 Google : Page Rank 알고리즘 PR( A) = = = T A 30 T T B 30 48

49 6.4 사례연구 Google 의장단점 순서 장점 단점 1 강력한웹로봇 기계적검색 2 수퍼컴퓨터운용 가끔검색되는낡은자료 3 페이지랭크 / 앵커텍스트 검색결과의비분류 4 공정한검색결과 사용자데이터베이스취약 5 완전자동화 저작권침해 6 타사이트와상생 7 무료의고가정보 49

50 6.4 사례연구 검색엔진사례 : Naver 1997년 11월 NHN사에서서비스시작. 삼성SDS의사내벤처로시작. 특징 14 개주제별키워드형검색엔진. 디렉토리와키워드혼합형. Web Crawler 12가지연산자와복합명사분석기능형태소분석기 : 한글 / 한자, 영어처리자연어검색 50

51 6.4 사례연구 Naver 엔진의구조 query Query Processor Repository document Document Loader 사용자 document result query Storage Manager Index Database index document Document Analyzer Nabot (HTML) World Wide Web 51

52 6.4 사례연구 Naver 네이버엔진의특성 순서 내역 비고 1 방대한데이터베이스다양한 DB와사용자참여 2 통합검색 다양한검색분야의통합 3 이슈검색 사용자관심사항반영 52

53 6.4 사례연구 Naver 네이버엔진의장단점 순서 장점 단점 1 다양한데이터베이스 타사이트와상생 2 통합검색 해외진출능력 3 사용자친화형이슈검색 검색결과의공정성 4 편리한데이터베이스 검색결과의부족 53

54 6.4 사례연구 검색엔진사례 : Lucene과 Nutch Lucene: java로만든저수준의문자색인라이브러리와 API Nutch: Lucene을기반으로 java로만든오픈소스검색엔진 Lucene 라이브러리의특징 순서 내역 비고 1 계층화된검색 구절및키워드일치 2 유연한질의 구절이나와일드카드 3 필드-특정질의 title, artist, album 4 정렬필드단위정렬 54

55 6.4 사례연구 Nutch 엔진의자료흐름 Database web 사용자 File System 자료수집 Crawler 직접등록 질의접수 결과제공 Application Index Documents Search Index Lucene Index 색인구축 색인검색 55

56 6.4 사례연구 검색엔진사례 : Lucene과 Nutch Nutch 엔진의핵심기능 순서 내역 비고 1 구문분석처리 다수의상이한컨텐츠형식 2 색인구축 대용량 3 크롤러정보수집 4 수집콘텐츠관리 상이한프로토콜지원 5 사용자질의처리 순위알고리즘 6 플러그인프레임워크 구문분석, 색인, 질의등의확장 56

57 6.4 사례연구 검색엔진사례 : Lucene과 Nutch Nutch 엔진의특징 순서내역비고 1 Lucene 기반 Java로작성 2 확장성 추가모듈의 plugin 가능 3 로봇기능 크롤러기능이풍부 4 프로그램강건성 Lucene의안전성 5 검색결과 중요한결과를처음으로 6 색인기능대용량 57

58 6.4 사례연구 Nutch 엔진의구조 URLFilter Framework Plugin Framework Crawler (Fetcher) Protocol Framework Parsing Framework Scoring Framework protocolhttp plugin parse-html plugin Web UI Data Store Segments Indexing Framework Query Framework 범례 Component Extension Point CrawlDB URLDB Plugin Framework specialize uses 58

59 6.4 사례연구 기존검색엔진과 Web Search Engine의비교 - 문서분포 : Web: 분산식, 기존 IR: 집중식 - 문서의수, 사용자, 빈도수 : Web > 기존 IR - Web : Dynamic & heterogeneous than IR HTML로구조화, IR: Plain Text - 사용성 : WWW search engine > 기존 IR 59

60 6.4 사례연구 정보검색엔진의순위 세계기호검색엔진, 순 위 1. Google: 76% 2. Yahoo: Baidu: MS: Naver: ebay: ASK 미국검색엔진순위 1. Google: 64.4% 2. Yahoo: Microsoft : ASK: AOL LLC: 2.4% 국내검색엔진순위 1. Naver: 66.65% 2. Daum: Google: Nate: Yahoo: 1.75 by 비즈스프링 ( 구자훈 )

61 6.5 요점정리 웹정보검색 웹사이트에서원하는정보를가져오는것. 인터넷정보의특징 분산, 대량, 비체계적, 이질적자료, 비신뢰적, 최근자료 웹정보검색의중요성 변화주도, 사업규모, 광고마케팅, 지적재산권, 신규사업, 문화욕구 웹검색기능의분산 인터넷, 색인서버, 검색서버, 사용자 웹정보검색을위한기술 정보수집, 색인구축, 질의처리 61

62 6.5 요점정리 웹정보검색의발전세대별발전단계 : 1, 2, 2.5, 3, 4세대웹정보검색엔진의분류주제형, 키워드형, 메타형모음형검색엔진웹검색엔진의주요기능자료수집, 용어추출, 용어저장, 사용자검색, 순위처리역색인의구조색인파일, 포스팅파일, 문서집합 62

63 6.5 요점정리 Google 엔진의특징크롤러, 분산 / 병렬처리, 색인, 페이지랭크 PageRank 알고리즘많이참조되는사이트, 페이지일수록중요하다. Google의장점 강력한웹로봇, 수퍼컴퓨터운용, 페이지랭크 / 앵커텍스트, 공정한검색결과, 완전자동화, 타사이트와상생, 무료의고가정보단점 : 기계적검색, 가끔검색되는낡은자료, 검색결과의비분류, 사용자데이터베이스취약, 저작권침해 63

64 6.5 요점정리 Naver 의장점 다양한데이터베이스, 통합검색, 사용자친화형이슈검색, 편리한데이터베이스 단점 타사이트와상생, 해외진출능력, 검색결과의공정성, 검색결과의부족 Nutch 엔진의특징 Lucene기반, 확장성, 로봇기능, 프로그램강건성, 검색결과, 색인기능 64

65 6.5 익힘문제 두문제를풀어서제출하시오. 65

66 익힘문제주요수식 ) ) ( ) (... ) ( ) ( ) ( ) ( ( ) (1 ) ( n n T C T PR T C T PR T C T PR d d A PR =

인터넷 검색엔진

인터넷 검색엔진 Web Information Retrieval 2001 년 9 월 21 일 국민대학교컴퓨터학부강승식 차례 웹검색엔진 국내외검색엔진 웹의특성및사용자특성 웹검색엔진의 issues Web spider(crawler) Ranking : 문서연관성기법 PageRank, HITS 결론 2 검색엔진개발 ( 국외 ) Lycos : CMU 의연구프로젝트 (1994) Excite