[정보] 아주 심플한 검색엔진의 원리

아주 심플한 검색엔진의 원리 관련 자료입니다.

내용 참고 하시기 바랍니다.

 

 

Soma search from DaeMyung Kang

 

1. 아주 심플한 검색엔진의 원리 강대명 (CHARSYAM@NAVER.COM)
 2.  고백!!! 실제로 검색엔진 관련 일을 해본 것은, 학교 연구실 이 검색엔진 만드는 연구실이라, 거기서 알바를 해 본 것 밖에 없습니다. 그리고 개인적으로 조금 공부해본 것들 뿐이에요. 즉 상당한 “구라” 가 섞여 있을 수 있습니다.
3.  주제 검색엔진의 동작 원리 이해하기
4.  왜? 검색엔진이 필요한 경우??? 어떤 정보를 Ranking에 맞춰서 가져올 필요성. “파이썬”&”KOREA” 라는 단어를 가진 문서를 가져오고 싶다면?
5.  검색엔진이 필요하다면? Elastic Search 쓰세요. Solr 쓰세요.
6.  괜히 만드는 것 보다 위에 것들 쓰시는 게 훨씬 좋습니다.
7.  그런데 왜? 그냥 재미로… 재미난 자료를 보고 나니 나도 정리해보고 싶어서…
8.  김종민님의 데놀 발표 https://www.slideshare.net/kjmorc/ss- 80803233  이것만 보셔도 됩니다. 제껀 “구라” 버전
9.  검색엔진의 구성 요소-학술적 색인 과정 질의 과정
10.  색인 과정-학술적 Data Source Web, File, E-Mail Data Store 색인 생성 변환 획득 Index
 11.  질의 과정 - 학술적 User Data Store 랭킹 평가 User Interaction Index Log Data
 12.  검색엔진의 구성 요소 색인 과정 크롤링 + 역인덱스 구성 질의 과정 인덱스로 찾기 + 랭킹
13.  크롤링 #0 웹 페이지의 수집 Requests module r = requests.get(‘http://www.naver.com’)
14.  크롤링 #1 해야할 질문들!!! – 비기술적  크롤링을 해도되나요? robots.txt  구글 검색봇이 우리 서버를 공격해요.
15.  크롤링 #2  Simple Idea Redis List Crawling Loop BLPOP
 16.  크롤링 #3 페이지를 가져왔으면? 링크 추출 Meaningful params의 추출 인코딩 변경 텍스트 추출(태그 제거)
17.  크롤링 #4 같은 페이지를 재방문해야 할까? 재방문 하지 않아야 한다면? 어떻게 기록을 해둘까? 재방문 해야 한다면? 몇일마다?
18.  크롤링 #5 저장을 해야하나? 어디에 저장할 것인가? 분산 파일 시스템? 구글이 이럴려고 BigTable 만듬.(Hbase, Cassandra or column oriented storage) DB? 어떤 데이터를 저장해야 하나? 원본?, 변환해서?
19.  크롤링 #6  Simple Idea Queue Crawling Loop 방문할 주소 Storage 방문 시간/주기 크롤링 데이터
20.  색인 #0 다음 문서들을 색인(Indexing)한다면? The bright blue butterfly hangs on the breeze It's best to forget the great sky and to retire from every wind Under blue sky, in bright sunlight, one need not search around
 21.  색인 #1 - tokenizing 먼저 단어별로 나눈다. DOC1 The bright blue butterfly hangs on the breeze DOC2 It’s to best retire to from forget every the wind. great sky and DOC3 Under not blue search sky around. in bright sunlight one need
 22.  색인 #2 - 변환 특수문자 제거 DOC1 The bright blue butterfly hangs on the breeze DOC2 It’s to best retire to from forget every the wind great sky and DOC3 Under not blue search sky around in bright sunlight one need
 23.  색인 #3 – 역인덱스 문서 -> 단어 에서 단어 -> 문서로 변환 단어 문서 단어 문서 단어 문서 단어 문서 The 1 It’s 2 to 2 in 3 bright 1 best 2 retire 2 bright 3 blue 1 to 2 from 2 sunlight 3 butterfly 1 forget 2 every 2 one 3 hangs 1 the 2 wind 2 need 3 on 1 great 2 Under 3 not 3 the 1 sky 2 blue 3 search 3 breeze 1 and 2 sky 3 around 3
 24.  색인 #4 – 같은 단어 합치기 같은 단어를 합치기 위해서 어떻게 해야 할까? 단어 문서 단어 문서 단어 문서 단어 문서 The 1 It’s 2 to 2 in 3 bright 1 best 2 retire 2 bright 3 blue 1 to 2 from 2 sunlight 3 butterfly 1 forget 2 every 2 one 3 hangs 1 the 2 wind 2 need 3 on 1 great 2 Under 3 not 3 the 1 sky 2 blue 3 search 3 breeze 1 and 2 sky 3 around 3
 25.  색인 #4-1 – 대소문자 변환 대문자를 소문자로. 단어 문서 단어 문서 단어 문서 단어 문서 the 1 it’s 2 to 2 in 3 bright 1 best 2 retire 2 bright 3 blue 1 to 2 from 2 sunlight 3 butterfly 1 forget 2 every 2 one 3 hangs 1 the 2 wind 2 need 3 on 1 great 2 under 3 not 3 the 1 sky 2 blue 3 search 3 breeze 1 and 2 sky 3 around 3
 26.  색인 #4-2 – 정렬 다음 처리를 위해서 정렬도 하게됨 단어 문서 단어 문서 단어 문서 단어 문서 and 2 butterfly 1 need 3 sunlight 3 around 3 every 2 not 3 the 1 best 2 forget 2 on 1 the 1 blue 1 from 2 one 3 the 2 blue 3 great 2 retire 2 to 2 breeze 1 hangs 1 search 3 to 2 bright 1 in 3 sky 2 under 3 bright 3 it’s 2 sky 3 wind 2
 27.  색인 #4-3 – 불용어 제거 너무 흔해서 안 쓰는걸 지우자. 검색어로의 가치가 없음 a not and on around one every the for to from under in … it … it’s …
28.  색인 #4-4 – 불용어 제거 안쓰는 단어 삭제 단어 문서 단어 문서 단어 문서 단어 문서 butterfly 1 need 3 sunlight 3 best 2 forget 2 blue 1 blue 3 great 2 retire 2 breeze 1 hangs 1 search 3 bright 1 sky 2 bright 3 sky 3 wind 2
 29.  색인 #4-5 – 불용어 제거 단어 문서 단어 문서 단어 문서 best 2 great 2 wind 2 blue 1 hangs 1 blue 3 need 3 breeze 1 retire 2 bright 1 search 3 bright 3 sky 2 butterfly 1 sky 3 forget 2 sunlight 3
 30.  색인 #4-6 – Stemming 동사를 원형으로 -> 어간/어미를 분리해서 어간만 남기는(~s, ~es, ~ed, ~ing 등등등 제거) 단어 문서 단어 문서 단어 문서 best 2 great 2 wind 2 blue 1 hang 1 blue 3 need 3 breeze 1 retire 2 bright 1 search 3 bright 3 sky 2 butterfly 1 sky 3 forget 2 sunlight 3
 31.  색인 #4-7 – 합치기 단어 문서 단어 문서 단어 문서 best 2 great 2 wind 2 blue 1,3 hang 1 need 3 breeze 1 retire 2 bright 1,3 search 3 sky 2,3 butterfly 1 forget 2 sunlight 3
 32.  색인 #4-8 – 합치기 단어 문서 단어 문서 best 2 need 3 blue 1,3 retire 2 breeze 1 search 3 bright 1,3 sky 2,3 butterfly 1 sunlight 3 forget 2 wind 2 great 2 hang 1
 33.  색인 #5
 34.  색인 #6 영어는 좀 쉬운데, 한국어는?  형태소 분석기로 분해된 단어만 저장  오픈소스 한국어 형태소 분석기(python 지원, 사전기반) 은전한닢 프로젝트(mecab 기반) Konlpy Komoran
 35.  색인 #7 N그램  형태소 분석은 색인되지 않는 단어가 있을 수도 있고, 띄워쓰기가 되지 않았을 때 분석이 힘듬.  N그램 방식은 언어정보를 몰라도 가능한 방법 그 대신 구릴 수 있음.
36.  색인 #8 N그램  2-gram(Bigram) 일 경우 “서핑클럽”은 “서핑”, “핑클“, “클럽” 의 두 글자로 구성된 3 단어로 색인을 구성함.  3-gram(trigram) 일 경우 “서핑클럽” 은 “서핑클”, “핑클럽” 의 세 글자로 구성된 2 단어로 색인을 구성함.
37.  색인 #9 – 검색 검색어도 동일한 작업을 진행 best 는 문서2에 존재한다. blue 는 문서1,3에 존재한다. blue & sky 로 검색시는 문서 3에 존재한다. 불용어로 검색하면 결과가 안나옴.
38.  색인 #10 – 질문들 그럼 엄청 많은 문서의 역인덱스를 가진 녀석들은 어떻게 계산해야 할까요? Animal, Apple 같은 단어들은?
39.  랭킹 #0 어떻게 문서의 랭킹을 매길 수 있을까? 어떤 문서가 좋은 문서일까요?
40.  랭킹 #1 좋은 문서 다른 문서들이 많이 링크하고 있고…(PageRank) 특히 다른 좋은 문서들이 링크를 한다면? 자주 업데이트 되면서… 검색어가 해당 문서에서 중요하게 쓰이는…
41.  랭킹 #2 – 위치 정보 blue sky 를 검색한다면, 문서1 과 문서 3 중에 뭐 가 더 적합한 문서일까요? 단어 문서 단어 문서 best 2:10 need 3:300 blue 1:100,3:50 retire 2:100 breeze 1:30 search 3:500 bright 1:50,3:55 sky 2:20,3:55 butterfly 1:20 sunlight 3:400 forget 2:40 wind 2:10 great 2:60 hang 1:400
 42.  랭킹 #3 특정 단어가 해당 문서에서 중요하게 쓰인다는 것을 어떻게 알 수 있을까? TF-IDF
 43.  랭킹 #4 TF-IDF는? 특정 단어가 해당 문서에는 많이 나오는데, 전체 문서들 중 에는 적게 나오면 해당 문서의 핵심어일 가능성이 높다라 고 판단하는 것. TF: Term Frequency 한 문서에서 몇 번이나 해당 단어가 나오는가? DF: Document Frequency 전체 문서에서 몇 개의 문서에서 발견이 되는가?
44.  랭킹 #5  카드뉴스라는 단어가 전체 문서 10개 중에 3개에서 발견  오늘이라는 단어가 전체 문서 10개 중에 9개에서 발견 Log(10/9) = 0.045 임, 즉 많은 문서에서 발견 될수록 값이 적어짐(TF-IDF)의 특성 Keyword URL TF TF*IDF 카드뉴스 DOC1 5 5 * log(10/3) = 5 * 0.52 DOC2 3 3 * log(10/3) = 3 * 0.52 DOC3 10 10 * log(10/3) = 10 * 0.52
 45.  랭킹 #6 – 질문들 기본적으로 TF 와 DF에 영향을 받게 되는데… 그 럼 같은 DF 라면, TF가 높을 수록 점수가 높아지는 데… 다음 중 점수가 높은 문서는? 검색 엔진 검색 엔진 검색 엔진
46.  랭킹 #7 – BM25  TF-IDF가 문서의 길이에 영향을 받으므로, 문서 길의 평 균에 영향을 받도록 개량한 알고리즘 Elastic Search 에서 쓴다고 합니다.
47.  랭킹 #8 – BM25  IDF = 전체 문서에 많이 나타날수록 적은 값을 줌.
48.  랭킹 #9 – BM25  TF = Term Frequency  IDF = 전체 문서에 많이 나타날수록 적은 값을 줌.
49.  랭킹 #10 – BM25  k1, b = 그냥 정한 상수 k1 = tf에 대한 가중치, b = 문서에 대한 가중치  |D| = 문서의 길이  avgdl = 문서의 평균 길이  결론적으로 평균 문서길이 보다 작은 문서에서 매칭될수 록 점수가 높음.
50.  결론 검색엔진 만들어 쓰지말고 그냥 잘 씁시다.
51.  Thank you.