M.S. Student at Korea Univ.
TODAY 13 TOTAL 19,274
검색엔진의 구조(Architecture of a Search Engine)
검색 엔진의 구조
Architecture of a Search Engine


"While your first question may be the most pertinent, you may or may not realize it is also the most irrelevant .”
The Architect, Matrix Reloaded

  • 검색엔진 구조
    • 3 parts : software components, interfaces, relationships
    • 2개의 필요조건
      • effectiveness(효과성) :  검색 결과의 품질. most relevant set of documnet
      • efficiency (효율성) : response time, throughtput

  • Indexing Process(색인 처리)
    • Text acquisition(텍스트 획득)
    • Text transformation(텍스트 변환)
    • Index Creation(색인 구축)
  • Query process(질의 처리)
    • User interaction(사용자 상호작용)
    • Ranking(순위 부여)
    • Evaluation(평가)


  • Indexing Process
    • Text Acquisition : 문서를 저장, 크롤링함으로 구축
    • Text transformation : 문서를 indext terms or features로 변환한다
    • Index creation(색인 구축) :
      • create data structures to support fast searching
      • efficiently updated
      • Inverted indexes(역색인구조) : most common form

(색인구조가 이미 만들어져있다고 가정)
  • Query Process
    • User interaction 
      • creation and refinement of query
      • display of results (snippets : 문서의 일부분, 키워드가 포함되어 있는 부분, 그 문서를 요약, 맨 처음 부분 등. ranking, bold, etc)
    • Ranking
      • uses query and indexes to generate ranked list of documnets
      • based on retrieval model
    • Evaluation
      • effectiveness and efficiency
      • effectiveness depends on retrieval model
      • efficinecy depends on indexes
      • offline activity



  • Text Acquistion 1. Crawler
    • Many types - web(link), enterprise, desktop
    • Web crawler
      • coverage & freshness
      • site search
      • Topical or focused crawlers for vertical search
    • Document crawler

  • Text Acquistion 2. Feed
    • A mechanism for accessing real-time streams of document
    • Web feed(or news fee) is a data format used for providing users with frequently updated content
    • Search engine도 받아봄
    • ex) RSS

  • Text Acquistion 3. Conversion
    • consistent text plus metadata format
    • convert text encoding

  • Text Acquistion 4. Document data store
    • metadata, links, anchor text
    • Provides fast access(검색 결과 제공 등)
    • a simpler and more efficient storage system is uesd



  • Text Transformation 1. Parser (여러 부분으로 나누는 것)
    • recognize structural elements
    • Tokenizer recognizes "words" (capitalization, hyphens, apostrophes, non-alpha characters separators
    • if Markup languages, use syntax

  • Text Transformation 2. Stopping & Stemming
    • Stopping(불용어 제거) : common words
      • 색인어로서 가치가 없다.
    • Stemming(형태소 분석) 
      • benefits vary for different languages

  • Text Transformation 3. Link analysis
    • popularity and authority 
      • ex) PageRank : incoming link가 많은 페이지를 랭크한다.

  • Text Transformation 4. Information Extraction & Classifier
    • Information Extraction
      • named entity recognizer
    • Classifier
      • assign labels
      • Clustering without predefined categories



  • Index Creation 1.Documnet Statistics
    • counts and positions of words
    • Used in ranking algorithm

  • Index Creation 2. Weighting
    • computes weights for index terms(상대적으로)
    • 문서 내에서 상대적인 중요도
    • tf : term frequency
    • idf : inverse documnet frequency(적을수록 좋으니까 inverse로 곱함)

  • Index Creation 3. Inversion & Index Distribution
    • Inversion
      • Core of indexing process
      • 문서-색인어 => 색인어-문서로 변환
      • 불용어를 제외한 사전에 있는 모든 단어
      • Must also handle updates
    • Index Distribution
      • Essential for fast query processing
      • both indexing and query processing can be done in parallel



  • User Interaction 1. Query input
  • User Interaction 2. Query transformation
    • Spell checking, query suggestion
    • query expansion, relevance feedback
  • User Interaction 3. Results output

  • Ranking
    • Scoring : å qidi
      • qi, di가 의미하는 것이 뭔지.
      • qi는 쿼리에 있는 텀 웨이트
      • 다양한 ranking algorithm 존재함. Vector space model
    • Performance Optimization(성능 최적화)
      • Term-at-a time과 document를 비교
      • Safe vs unsafe 비교
    • Distrivution(분산)
      • 검색엔진에 관련된 이야기. 쿼리를 쪼개서 처리할 수도 있음.
      • Caching



  • Evaluation
    • Logging
      • 사용자가 어떤 쿼리를 날렸느냐
      • 어떤 결과를 제시했더니 몇 번째 문서를 클릭했더라
      • dwell time 등 여러 가지를 기록한다.
    • Ranking analysis (순위 분석 : 효과성)
    • Performance analysis(성능 분석 : 효율성)



출처 : W.BruceCroft DonaldMetzler TrevorStrohman
Search Engines
Information Retrieval in Practice


0  Comments,   0  Trackbacks
댓글 쓰기

티스토리 툴바