검색엔진의 원리: 역인덱스와 랭킹

검색엔진이란

검색엔진은 어떤 단어가 들어간 문서를 빠르게 찾고, 관련도 순으로 정렬해 돌려주는 시스템이다. DB의 LIKE '%단어%'는 인덱스를 타지 못해 전체 행을 훑고, 결과의 순서(랭킹)도 정해 주지 않는다. 이 두 가지가 필요해지면 검색엔진을 쓴다.

DB 검색의 한계

이 한계를 넘는 기능(퍼지 검색, 분석기, 점수 조정)을 갖춘 것이 Elasticsearch·OpenSearch·Solr 같은 전용 검색엔진이다.

검색엔진은 직접 만들지 않는다. 색인·질의·랭킹·분산·장애 처리를 모두 구현하는 비용이 크고, 직접 만든 것은 버그가 많다. 서비스에서는 Elasticsearch나 OpenSearch(둘 다 Apache Lucene 기반)를 쓰고, 원리는 튜닝과 문제 해결을 위해 이해한다.

두 과정: 색인과 질의

색인(Indexing)

flowchart LR
  src["데이터 소스(웹·파일·DB)"] --> crawl["수집(크롤링)"] --> raw["원본 저장"]
  crawl --> analyze["분석(토큰화·정규화)"] --> inv["역인덱스"]

질의(Query)

flowchart LR
  q["사용자 질의어"] --> an["같은 분석"] --> lookup["역인덱스 조회"] --> rank["랭킹(점수)"] --> res["결과"]
  log["클릭 로그 등으로 랭킹 평가·개선"] --> rank

질의어도 색인과 똑같은 분석 과정을 거쳐야 한다. 색인할 때 소문자로 바꿨다면 질의어도 소문자로 바꿔야 일치한다.

수집(크롤링)은 대부분 필요 없다. 서비스는 자기 DB를 색인하고, Elasticsearch도 크롤러를 포함하지 않는다. 외부 사이트를 수집할 때의 robots.txt 규칙은 SEO 기초: 크롤링부터 메타 태그까지에 있다.

역인덱스 만들기

일반 인덱스가 "문서 → 단어"라면, 역인덱스(Inverted Index)는 "단어 → 그 단어가 든 문서 목록"이다. 책 뒤의 찾아보기와 같다.

세 문서로 만들어 보면 이렇다.

DOC1: The bright blue butterfly hangs on the breeze.
DOC2: It's best to forget the great sky and to retire from every wind.
DOC3: Under blue sky, in bright sunlight, one need not search around.

결과 역인덱스의 일부는 다음과 같다.

이제 질의는 목록 조회와 집합 연산이다. sky는 {2, 3}, blue는 {1, 3}이므로 blue AND sky는 교집합 {3}이다. 불용어로 검색하면 인덱스에 없으므로 결과가 나오지 않는다.

실제 역인덱스는 문서 번호와 함께 단어의 위치(position) 도 저장한다. blue sky처럼 구(phrase)로 검색할 때 두 단어가 붙어 있는 문서를 더 높게 칠 수 있다.

단어 사전은 해시 테이블이나 B+ 트리로도 담을 수 있지만, Lucene은 FST(Finite State Transducer)라는 압축 오토마타로 저장해 접두사 검색과 메모리 효율을 함께 얻는다.

위치를 담은 게시 목록은 'web': [[1, [0, 2]], [2, [2]], [3, [1]]](1번 문서의 0·2번째, 2번 문서의 2번째 …)처럼 생겼다. 구문 질의는 이렇게 푼다.

"computer science department"
1. 세 단어의 문서 집합 교집합을 구한다 (작은 목록부터, 중간이 비면 즉시 중단)
2. 남은 문서마다 i번째 단어의 위치에서 (i−1)을 뺀다
   문서 1: [[2,5], [3], [4,6]] → [[2,5], [2], [2,4]]
3. 위치 목록들의 교집합이 비어 있지 않으면 단어가 순서대로 붙어 있다 → {2} 일치

빼기 + 해시 교집합은 O(N·K)(N: 단어 수, K: 위치 수)이고, 첫 목록의 위치마다 다른 목록을 이진 탐색하면 O(K·N·log K)다. 보통 단어 수는 적고 위치 수는 많아 빼기 방식이 유리하다. 질의에도 색인과 똑같은 전처리(소문자화, 불용어, 어간 추출)를 해야 맞는다. 어간 추출은 색인 시간을 몇 배로 늘리는 비싼 단계다.

한국어 색인

한국어는 띄어쓰기 단위(어절)에 조사·어미가 붙어 있어 공백 토큰화만으로는 같은 단어가 모이지 않는다. 보안개발트랙입니다와 보안개발트랙에서는은 다른 토큰이 되고, 영어처럼 -s, -ing를 떼는 규칙으로는 어미를 걷어낼 수 없다.

• Elasticsearch·OpenSearch는 공식 한국어 분석기 Nori(mecab-ko-dic 사전 기반)를 제공한다. 사용자 사전으로 복합어를 등록하고 decompound_mode로 분해 수준을 정한다.
• 파이썬에서는 KoNLPy(Mecab·Komoran·Okt 래퍼)나 Kiwi(kiwipiepy)를 쓴다.
• 실무에서는 형태소 분석 필드와 N-gram 필드를 함께 두고 점수를 합치는 경우가 많다.

랭킹

apple처럼 수많은 문서에 들어 있는 단어는 결과가 너무 많다. 어떤 문서를 먼저 보여 줄지 정하는 것이 랭킹이다. 신호는 단어 중요도(TF-IDF, BM25) 외에도 단어 위치(검색어끼리 가까운가), 신선도, 링크 구조(PageRank) 등이 있다. 웹 검색의 랭킹 신호와 다단계 랭킹은 웹 검색엔진의 동작에 있고, 여기서는 단어 중요도 점수만 다룬다.

랭킹 점수: TF-IDF에서 BM25로

기본 직관은 한 문서에 자주 나오지만 전체 문서에서는 드문 단어가 그 문서의 핵심어라는 것이다. TF-IDF가 이를 그대로 식으로 옮겼다.

TF-IDF  w(i, j) = tf(i, j) × log(N / df(i))
 
BM25    score(D, Q) = Σ IDF(qᵢ) × f(qᵢ, D) × (k1 + 1)
                                 ─────────────────────────────────────────
                                 f(qᵢ, D) + k1 × (1 − b + b × |D| / avgdl)
        IDF(qᵢ) = ln(1 + (N − n(qᵢ) + 0.5) / (n(qᵢ) + 0.5))

예를 들어 문서 10개 중 카드뉴스가 3개, 오늘이 9개에 있으면 IDF(log₁₀)는 0.52와 0.046이다. TF-IDF의 약점은 tf가 선형으로 커진다는 것이다. 같은 단어를 네 번 반복하면 점수가 네 배가 되고, 긴 문서가 유리하다. BM25(Okapi BM25)는 tf 포화와 문서 길이 보정으로 이 둘을 고쳤고, Elasticsearch·OpenSearch·Lucene의 기본 유사도다.

TF-IDF로 순위를 매길 때는 문서와 질의를 같은 단어 공간의 벡터로 놓는다(벡터 공간 모델). TF를 문서 벡터 길이(유클리드 노름)로 나눠 정규화해야, 같은 내용을 두 번 이어 붙인 긴 문서가 부당하게 유리해지지 않는다. IDF에 로그를 쓰는 이유는 df가 10인 단어와 100인 단어의 중요도를 10배가 아니라 완만하게 차이 내려는 것이고, 정보 이론의 놀람 정도 −log p와 같은 꼴이다. 질의 벡터와 문서 벡터의 코사인 유사도로 정렬한다. 단어 가방(bag of words)이라 「Bob likes Alice」와 「Alice likes Bob」을 구별하지 못한다.

관계를 검색하기: 그래프 위의 역인덱스

역인덱스의 「단어」 자리에 관계를 넣으면 소셜 그래프도 검색할 수 있다. Facebook 그래프 검색의 기반인 Unicorn이 이 방식이다. 사용자·페이지·장소·사진은 노드, 친구·좋아요·체크인·태그는 간선이고, 「간선 종류:노드 ID」가 색인어가 된다.

색인어                → 게시 목록(posting list)
friend:10003         → [1234, 5678, …]   10003의 친구들
lives-in:111         → [1234, …]         111(뉴욕)에 사는 사람
like:222             → [1234, …]         222(어떤 드라마)를 좋아하는 사람
 
"뉴욕에 사는 내 친구" = AND(friend:10003, lives-in:111)

질의 입력을 자연어로 받으면 문법으로 해석하는 단계가 앞에 붙는다. 가중 문맥 자유 문법(WCFG)으로 「검색할 수 있는 문장」을 정의하고, 질의 조각을 엔티티로 인식·해소한 뒤 비용(규칙 비용, 엔티티 일치 비용, 삽입·삭제·치환 같은 어휘 일치 비용)이 가장 낮은 해석 N개를 고른다. 각 해석은 intersect(friends(나), residents(도시)) 같은 의미 트리로 바뀌어 위의 검색 질의가 된다. 랭킹 변경은 CTR·NDCG·참여 지표를 대조군과 비교하는 실험으로 결정한다.

한계와 확장

• 역인덱스는 글자가 일치해야 찾는다. 자동차로 차량을 찾으려면 동의어 사전이 필요하다.
• 의미가 비슷한 문서를 찾는 벡터 검색(임베딩 + kNN)이 이 빈틈을 메운다. Elasticsearch·OpenSearch도 벡터 필드를 지원하며, BM25 점수와 벡터 점수를 섞는 하이브리드 검색이 흔하다.
• 오타는 역인덱스에서 그대로 빗나간다. 편집 거리 기반 퍼지 검색으로 비슷한 단어까지 찾는다.
• 랭킹 공식은 출발점이다. 실서비스는 클릭 로그로 결과를 평가하고 가중치를 조정한다.

정리

• 검색엔진 = 색인(문서 → 역인덱스) + 질의(같은 분석 → 조회 → 랭킹).
• 역인덱스는 토큰화 → 정규화 → 불용어 제거 → 어간 추출 → 정렬·병합으로 만든다.
• 한국어는 형태소 분석(Nori 등)과 N-gram을 상황에 맞게 섞는다.
• 랭킹의 기본은 BM25다. TF-IDF에 tf 포화와 문서 길이 보정을 더한 것이다.
• 원리를 알고, 구현은 Elasticsearch·OpenSearch에 맡긴다.

관련 노트: 웹 검색엔진의 동작: 크롤링, 색인, 랭킹, 질의 처리, 문자열·문서 유사도: 편집 거리와 코사인 유사도, SEO 기초: 크롤링부터 메타 태그까지, 데이터베이스 모델: RDB, NoSQL, NewSQL, SQL 기초, Elasticsearch와 ELK 스택