검색 맛보기

검색 엔진이 어떻게 동작하는지 아주 간단하게 공부해봤습니다.

• ElasticSearch를 이용해서 기능을 개발하면서 개인적으로 흥미가 생겨 공부하게 되었습니다.

---

0. 공부할 자료

Introduction to Information Retrieval
 

GPT의 추천!

• https://nlp.stanford.edu/IR-book/pdf/irbookonlinereading.pdf
• 스탠포드 대학교에서 만든 정보 검색 분야의 유명한 교과서입니다

정보 검색 분야에서 자주 나오는 용어

- Term: 문서 안에 나오는 단어(토큰)
- Document: 검색 대상이 되는 하나의 문서(게시글, 뉴스 글 등)
- Collection, Corpus: 검색 대상이 되는 문서의 전체 집합
- Information need: 사용자가 진정으로 찾고 싶어하는 정보
- query: 사용자가 검색창에 입력하는 문자열
- relevance: 얼마나 잘 부합하는지
- effectiveness: 검색 품질을 평가하는 지표
    - precision: 검색된 문서 중에서 사용자가 찾고 싶어하는 문서의 비율
    - recall: 사용자가 찾고 싶어하는 문서 중에서 검색된 문서의 비율
- dictionary - vocabulary(lexicon): 전체 컬렉션에 존재하는 term들의 중복이 제거된 집합
- inverted list - postings, postings list: term과 document id를 맵핑하여 특정 term에 대해서 문서를 빨리 찾을 수 있는 구조
 

1. Grepping

가장 단순한 검색 방식으로 모든 문서들(collection)을 스캔하면서 주어진 쿼리를 만족하는 문서를 찾는 방식입니다.
 
한계: 시간복잡도가 O(N)이라서 문서가 많아질수록 검색 속도가 느려짐
 
MySQL, PostgreSQL  과 같은 RDBMS에서 제공하는 LIKE 쿼리와 비슷하다고 이해하면 될 것 같습니다.

+++
LIKE 쿼리도 name LIKE 'kim%' 와 같이 prefix가 고정되어 있는 형태라면 인덱스를 탈 수 있습니다

2. Term-Document Matrix

각 문서에 어떤 단어가 있는지 인덱싱 하는 방식으로 벡터로 문서와 단어 간의 관계를 관리할 수 있습니다.

	문서1	문서2	문서3
Apple	1	0	1
Banana	1	1	0
Cat	1	0	0
Dog	0	1	1
Egg	0	1	1

 
한계: 문서가 많아질수록 vocabulary가 커져서 불필요한 용량을 낭비하게 됨

+++
대부분 0으로 채워지는 sparse한 행렬
 

3. Inverted Index

각 term 별로 포함되어 있는 document id를 관리하는 방식

Apple  -> [문서1, 문서3]
Banana -> [문서1, 문서2]
Cat    -> [문서1]
Dog    -> [문서2, 문서3]
Egg    -> [문서2, 문서3]

 
 많은 검색 엔진이 inverted index를 효율적으로 다룰 수 있습니다.

4. MySQL full text index

RDBMS도 inverted index 기능을 제공합니다.

full text index를 설정하면 텍스트로 inverted index가 생성됩니다.
거기에 ngram 플러그인을 추가로 설정한다면 부분 문자열로 검색하는 것도 가능하게 됩니다.

5. Elasticsearch

Lucene 기반의 검색 엔진으로 RDBMS보다 훨씬 풍부한 검색 기능을 제공합니다.

- Lucene은 Java 기반 텍스트 검색 라이브러리입니다.
- 저수준의 인덱싱, 검색, 파일 저장 등의 기능을 제공하고 있어서 Elasticseaech는 이를 활용해서 고수준의 검색 관련 기능을 제공해줍니다.


inverted index는 물론 vector 기반 검색도 지원하며 Tokenizer, Filter를 비롯한 Analyzer도 있습니다.
- Analyzer: Tokenizer + Filter 조합으로 텍스트를 검색 가능한 토큰화해주는 파이프라인입니다.
    - Tokenizer: 텍스트를 토큰 단위로 잘라줍니다. 띄어쓰기를 기준으로  자를지, 특정 기호를 기준으로 자를지, 형태소 기준으로 자를지 등 다양한 기준으로 토큰화 할 수 있습니다.
    - Filter: Tokenizer가 잘라준 토큰을 전처리해줍니다. 영어라면 소문자화, 관사처럼 의미가 적은 불용어 제거 등

Analyzer를 이용하면 저장되는 문서의 각 필드들을 원하는 방식으로 인덱싱 할 수 있고, 검색 쿼리도 토큰화 하여 인덱싱 된 값들과 비교해서 문서를 찾아줍니다.