검색엔진의 이해

소프트웨어 마에스트로 오우택 멘토님 수업
디테일한 내용들은 따로 검색하도록 하자.

용어

• 쿼리 Q(“”)
• Document : 하나의 (웹)페이지.
• Collection : 도큐먼트의 집합
• IR : Information Retrieval, 정보 검색.
• Terms : 단어
• Index
• Log : 수학의 로그. 로그의 특성을 검색엔진에서 활용한다 (노멀라이징)
• Measure
• Word Count : 검색엔진에서 가장 많이 하는 작업. 가장 쉬운 문서 계량화 방법.

일반적인 검색 과정

• Web Spidering : 웹 스파이더를 돌려서 컬랙션을 만든다
• Indexing : 검색을 위한 인덱싱
• Searching : 쿼리가 들어오면 쿼리 엔진을 돌려서 결과를 리턴.

Web Spidering

웹 크롤러

크롤링 - 파싱 - 저장
큐 / 스케줄러

크롤러의 고민들

• 최신성 유지, Deadlink 검출
• 복잡한 html 문서에서 컨텐츠 찾기 : 휴리스틱 + 머신 러닝
  • 해당 사이트에서 보일러플레이트1가 아닌 계속 바뀌는 부분을 학습 -> 컨텐츠!
    컨텐츠 내에서 타이틀/본문 등의 구분은 길이로 한다.
    방법중 하나!
• 우선순위 정하기
• 트래픽 관리 - 중복 URL 피하기. 네트워크 이용이 곧 돈이므로 줄여야 한다!
• Robots.txt2 규약 지키기
• 효율적 분산 저장
• 문서 형식 변환 : 크롤링 하는 웹 문서들의 형식이 다양하다. pdf, 워드, 한글 등등…

Text Extraction

• 문서 구조 분석
• 문장 부호 및 공백 등 불필요한 문자 제거
• 문장 및 형태소 분석 : 문장의 조사, 품사 등을 분석한다. 컬랙션에 따라 형태소 분석도 조금씩 달라짐.
• stopword 제거 : stopword란 전치사, 관사, 조사 등 주제색인어로서 의미가 없는 단어들이다. 즉 검색할 때 무시함.
• stemming : 어간3 추출
  • 보다, 보니 보고 -> 보-
  • 먹다 먹니 먹고 -> 먹-
  • stemmer, stemming, stemmed -> stem
  • fishing, fished, fisher -> fish
  • argue, argued, arguing, argus -> argu(단어의 원형과 일치하지 않는 경우)
• 동의어 처리 : 오토 + 수작업. 사전 구축을 해야한다. 램프, 렘프, lamp 뭐 이런것들.
• 색인 생성

Indexing

Inverted Index

TF-IDF. 텀 프리퀀시와 도큐먼트 프리퀀시.

인덱싱 과정의 어려움

• 컬렉션이 너무 큼
  • 클라우드 컴퓨팅 -> 참조하는 값들이 여기저기 퍼져있다
  • 스케줄링
  • etc…
• 형태소 분석기 : 신조어가 자꾸 나온다
• 인덱스 업데이트는 얼마나 자주 해야 하는가?

Searching

Matching Process

Q(“blue sky”) : 인버티드 인덱스를 활용, 각 워드가 어느 도큐먼트에서 나왔는지 찾는다.
-> 그럼으로써 쿼리-도큐먼트간 연관성을 계산할 수 있다.
매칭!

Retrieval Model

매칭과 비슷하지만 이건 연관도가 높은 걸 찾는 작업

• Boolean Model
• Vector Space Model
• Vector Model
• Probability Model
• Language Model

Ranking

Relevance Score로 정렬.

• Relevance Score = {Similarity, Quality, Recency …}
• Recency : 시간에 따라 점수가 낮아져야 한다. 감쇄 곡선 사용. 서비스, 컬렉션에 따라 감쇄 곡선이 달라진다.
• Champion List : 명확한 답을 제시하는 term.

Result Display

검색엔진을 써 보면 타이틀도 뽑아서 보여주고, 검색한 키워드도 하이라이팅 해서 보여주고, 관련된 부분도 보여준다. 이러한 작업.

• Passage 추출
• Keyword Highlighting
• Collection Ranking : 네이버에서 검색해 보면 검색어에 따라 노출되는 컬랙션이 다름.
• Preview & Thumbnails : UX. 유저의 불필요한 클릭을 줄여준다.

Query

모든 유저가 훌륭한 쿼리를 날리는 것은 아니다. 훌륭하지 않은 쿼리에 대해서도 훌륭한 검색결과를 제공해야 한다.

• 자동완성
• 연관검색어
• 실시간 인기검색어
• 오탈자 교정
• 질의 확장 : 한글검색 -> 영어 등 입력하지 않은 결과도 찾아준다
• Query Reformulation

User Feedback

검색엔진을 개선하기 위해서 하는 작업들

• Champion List 구축
• User Behavior & Action
• Clickstream Mining

=> 사용자들이 어떤 페이지를 선택하고, 어떤 페이지를 오래 보고. 또는 어떤건 잘 안누르고. 이런걸 분석한다.

Ranking

랭킹에 대해 좀 더 자세히 살펴보자.

PageRank

구글을 처음 만들 때 링크로 페이지의 점수를 계산했다. 지금은 링크가 많지 않지만 예전에는 검색엔진이 없어서 페이지끼리 전부 링크가 되어 있어서 매우 많았다.

P : 나를 링크하는 페이지 수
R : 나를 링크하는 페이지의 점수
L : 나를 링크하는 페이지의 외부링크 수
내 점수 = PR/L

즉 나를 링크하는 페이지가 많을수록, 그 페이지의 점수가 높을수록 점수가 올라가고 반대로 그 페이지의 외부링크가 많을수록 점수가 떨어진다.

Ranking Features

컨텐츠 퀄리티를 계산.

• 소셜에서는 외부에서 링크한 사람들이 얼마나 영향력이 있는가
• 이 페이지가 얼마나 오래 운영되었는가

등등을 참조.

SEO

Search Engine Optimization : 좋게 말하면 검색엔진 최적화.
정확하게는 검색 순위를 올려주고 돈을 받는 회사들. 즉, 어떻게 하면 검색엔진 상위에 랭크되는가를 분석한다.
랭킹 알고리즘의 품질이란 올바른 내용이 올바른 순위에 나오도록 하는 일. 즉 SEO는 랭킹 알고리즘의 품질에 반하는 일이다. 랭킹 알고리즘은 끝없는 품질과의 싸움.

Edge Rank

이러한 랭킹 알고리즘들은 검색 밖에서도 ‘평가’를 위해 사용한다. 그중에서도 대표적인게 페이스북에서 사용하는 Edge Rank다.

• User Action
  • Share, Comment, Likes, Clicks
• Edge Rank
  • Affinity : 관계 점수. 교류가 없는 친구는 점점 안보인다.
  • Weight : 글의 종류나 유저 액션. 즉 내가 평소에 이미지만 보는가. 어떤 종류의 글을 좋아하는가.
  • Time : Decay Function (감쇄곡선)
• Story Bumping
  • 사용자가 미처 확인하지 못한 친구글 Boost UP!
• Last Actor
  • 최근 친구글 중 인기글 Boost UP!

Evaluation

그럼 검색결과를 어떻게 평가할까? 정답이 없는 문제.

Measure

• Recall & Precision
  • Recall : 나와야 할 문서가 얼마나 나왔는가.
  • Precision : 나온 문서들 중 정확한 문서는 얼마나인가.
    둘다 높은 게 이상적이지만, 현실적으론 Recall이 올라갈수록 Precision이 떨어진다.
• F Measure

TREC

Text REtrieval Conference. 정부 문서 따위의 공식 문서들을 활용한 정답 셋이다. 이걸 활용해서 Measure한다. 문제는 한국어 자료는 없어서 직접 만들어야 한다.

내부 아키텍쳐는?

• B+트리 등을 사용해서 최선의 인덱싱을 한다.
• 서버와 프로그램을 거의 일치시킨다. 즉 하이퍼바이저-OS-프로그램 등의 이런 레이어를 최대한 제거.

---

1. boilerplate. 재사용 가능한 부분을 의미. 일종의 템플릿이라고 생각할 수 있다.↩

2. 사이트 제작자가 사이트 내에서 어떤 URL은 접근해도 되고 어떤 URL은 접근하면 안 되는지 적어 놓은 문서. 강제성은 없지만 지키는게 매너.↩

3. 동사, 형용사, 서술격 주사 등에서 변하지 않는 줄기 부분↩