Full Text Search는 어떻게 동작할까?

📌 Full Text Search (FTS)란

Full Text Search (FTS)는 검색 질의로 들어오는 단어가 언급된 모든 문서를 찾아주는 기능을 의미한다. 검색엔진, 지도, 사전 등 많은 애플리케이션에서 쉽게 찾아볼 수 있다.

💡 검색한 키워드에 대해서는 굵게 혹은 다른 색상으로 표시하여 시각적으로 강조하여 결과를 보여준다.

📌 동작 방식

구글은 수많은 웹페이지들 가운데에서 어떻게 내가 원하는 키워드를 빠르게 찾아줄 수 있을까? 루씬(Lucene)과 같은 FTS library가 어떻게 동작하는지 간략하게 알아보자.

background에서 돌아가는 crawler에 의해 새로운 문서가 추가된다면:

• Tokenizer: 텍스트를 단어 단위로 나눈다
• Filter
  • Lowercasing: 모든 단어를 소문자로 변환하여 대/소문자 구분 없이 검색할 수 있도록 한다 (ex. The -> the)
  • Stopword Removal: 검색에 의미가 없는 일반적인 단어 (ex. the, is, in)를 제거한다
  • Stemming: 단어의 기본 형태를 추출하여 다양한 형태의 단어를 동일하게 처리할 수 있도록 한다 (ex. jumping, jumps -> jump)
• Inverted Index에 저장한다

사용자가 "Brown Fox"로 검색한다면:

• 문서가 추가될 때와 동일하게 tokenizer, filter를 실행시켜 키워드를 전처리한다
  • 결과: ["brown", "fox"]
• 전처리된 키워드를 Inverted Index에서 검색하여 일치하는 문서 목록을 생성한다
  • 결과: [33, 101]
• 검색 결과의 관련성을 기준으로 순위를 매긴다
  • 결과: [101, 33]
• 사용자에게 결과를 리턴한다

💡 검색 결과의 관련성을 기준으로 순위를 매길 때는 다양한 알고리즘과 모델이 사용된다. (ex. TF-IDF, BM25, Vector Space Model)