웹 검색 품질을 설계하는 역색인·BM25·PageRank

후보 문서를 찾고 순위를 매기는 검색 구조

웹 검색에서 역색인(Inverted Index), BM25, PageRank는 서로 다른 역할을 맡는다. 역색인은 질의어와 관련된 문서 후보를 빠르게 꺼내고, BM25는 텍스트 관련성을 점수화하며, PageRank는 링크 그래프에서 얻은 권위 신호를 더한다.

역색인은 용어를 문서 목록에 연결하는 구조다. 각 용어의 postings에는 문서 ID, 용어 빈도, 위치 정보가 들어간다. 대규모 색인에서는 Variable Byte, PForDelta 같은 압축 방식과 세그먼트 기반 쓰기·머지 전략을 함께 사용한다.

BM25는 Okapi BM25 계열의 확률적 검색 모델이다. 용어 포화 파라미터 k1과 문서 길이 정규화 파라미터 b를 사용하며, k1≈1.2~2.0, b≈0.6~0.8 범위가 권장된다. 질의어별 가중치와 IDF는 희귀한 용어를 더 강하게 반영한다.

PageRank는 링크 그래프 위에서 권위 점수를 계산한다. 감쇠 계수 d≈0.85를 사용하는 랜덤 서퍼 모델이며, 전역 신호이므로 링크 조작과 스팸에 대한 대응이 필요하다. 계산은 주기적인 오프라인 배치로 수행한다.

색인 파이프라인과 랭킹 경로

문서가 색인에 들어가기 전에는 정규화, 토크나이징, 형태소 분석, 스테밍·불용어 처리가 이어진다. 언어 감지와 중복 제거를 수행하고, 필드별 부스팅도 이 단계에서 반영할 수 있다. 쓰기는 세그먼트 단위 Append-Only 방식으로 처리하고, 백그라운드 병합 뒤 Near-Real-Time 방식으로 공개한다.

검색 요청에서는 역색인이 수천~수만 개의 후보를 먼저 회수한다. 이 후보에 BM25를 적용한 뒤, BM25와 PageRank를 선형 결합하거나 Learning-to-Rank로 통합해 재랭킹한다.

샤딩과 리플리케이션은 수평 확장과 고가용성을 위한 기반이다. 검색 경로를 Read-Only로 유지하는 한편, 색인 최신성과 일관성 사이의 균형은 NRT 커밋·퍼블리시 시맨틱스로 운영한다.

성능 측면에서는 용어 사전을 FST로 메모리에 적재하고, 상위-N 스킵 목록과 블록 압축으로 I/O를 줄인다. 쿼리 캐시와 포스팅 블록 캐시, 다중 스레드 병렬 집계, Early Termination도 함께 고려한다.

품질 평가는 NDCG, ERR, MRR 기반의 오프라인 측정과 A/B 테스트 기반 온라인 검증으로 나뉜다. 클릭모델과 세션 분석은 쿼리 리라이트에도 활용할 수 있으며, 오타 교정과 동의어 확장이 대표적인 적용 방식이다.

각 알고리즘이 담당하는 범위

알고리즘	성능(지연/CPU)	확장성	일관성	안정성	운영 편의
Inverted Index	상: ms 단위 조회	상: 샤딩 용이	중: NRT, 최종 일관성	상: 복제·세그먼트 격리	중: 머지/압축 관리 필요
BM25	상: 경량 연산	상: 분산 병렬	상: 결정적 재현성	상: 파라미터 고정	상: 파라미터 튜닝 단순
PageRank	중: 그래프 계산 비용	상: 배치 분산	중: 주기적 갱신	중: 링크 스팸 민감	중: 오프라인 파이프라인 필요

참고: 실제 평가는 데이터 크기, 하드웨어, 구현에 따라 변동 가능.

웹·문서·상품 검색에서의 결합 방식

대규모 웹 검색의 오프라인 경로는 크롤링, 정제, 역색인 생성, PageRank 배치 계산, 세그먼트 퍼블리시로 이어진다. 온라인에서는 질의를 파싱하고 역색인에서 후보를 회수한 뒤 BM25 스코어링, PageRank 조인, 재랭킹, 스니펫 생성을 거쳐 결과를 반환한다.

사내 문서 검색에서는 필드 가중치(BM25F), 접근 제어(ACL) 필터, 한국어 형태소 분석기가 핵심 요소가 된다. 신선도 부스팅과 동의어 사전은 문서 탐색성을 높이는 데 사용한다.

전자상거래 검색은 BM25에 인기도·전환율, 재고·가격 제약을 결합한다. 품절과 가격 필터를 먼저 적용하고, PageRank 대신 셀러 평판이나 리뷰 신뢰도를 신호로 사용할 수 있다.

오프라인 색인과 온라인 질의 처리

⤢✕

용어가 존재하지 않으면 오타 교정을 시도하고, 실패하면 유사 질의를 추천한다. PageRank가 없거나 타임아웃이 발생하면 BM25 단독 경로로 디그레이드한다. 인덱스를 퍼블리시하는 동안에는 읽기 샤드를 원자적으로 교체하고, 질의 경로는 Read-Only로 유지한다.

성능·품질·운영에서 기대하는 변화

샤딩×복제와 캐시 적중률 40%를 가정하면 p95 응답시간을 200ms 이하로 달성할 수 있다. 단어 기반 역색인은 선형 검색(O(N))과 비교해 포스팅 교집합 기반의 준선형 탐색을 사용하므로 CPU 사용량을 10배 이상 줄일 수 있다.

BM25 도입 후 TF-IDF 대비 NDCG@10이 515%p 개선된 사례가 일반적이며, PageRank를 결합하면 네비게이셔널 쿼리 Precision@10이 310%p 개선될 수 있다. 쿼리 리라이트 적용은 무결과 빈도를 20~40% 줄인 사례가 있다.

세그먼트 병합과 퍼블리시로 인덱스 가용성 99.9% 이상을 확보할 수 있다. PageRank는 일 1회 배치로 계산하고 NRT 색인은 초~분 단위로 반영하면 신선도와 권위 신호를 함께 관리할 수 있다.

주: 수치는 일반적 범위 예시, 워크로드·데이터·구현에 따라 상이 가능. 최신 벤치마크로 검증 필요.

BM25와 PageRank를 결합하는 코드

전제조건은 Python 3.10+와 pip install rank-bm25 networkx다. 아래 예제는 소형 코퍼스의 BM25 점수와 단순 링크 그래프의 PageRank를 계산한 뒤 선형 결합으로 최종 점수를 산출한다.

# pip install rank-bm25 networkx
from rank_bm25 import BM25Okapi
import networkx as nx
import numpy as np

# 문서와 링크 그래프 예시
docs = [
    "웹 검색 알고리즘 개요 역색인과 BM25",
    "BM25 점수와 페이지랭크 결합 방법",
    "링크 분석과 PageRank 스팸 방어",
    "한국어 형태소 분석과 인덱싱 최적화"
]
tokenized = [d.lower().split() for d in docs]
bm25 = BM25Okapi(tokenized, k1=1.5, b=0.75)

# 간단 링크 그래프 (문서 ID: 0..3)
G = nx.DiGraph()
G.add_edges_from([(0,1),(1,2),(2,1),(0,3)])
pr = nx.pagerank(G, alpha=0.85)
pr_vec = np.array([pr.get(i, 0.0) for i in range(len(docs))])

# 질의 처리
query = "BM25와 PageRank"
q_tokens = query.lower().split()
bm25_scores = np.array(bm25.get_scores(q_tokens))

# 선형 결합 (가중치는 업무 특성에 맞게 튜닝)
alpha = 0.8  # 내용 관련성 비중
beta = 0.2   # 권위 신호 비중
final_scores = alpha * (bm25_scores / (bm25_scores.max() + 1e-9)) + beta * (pr_vec / (pr_vec.max() + 1e-9))

ranked = np.argsort(-final_scores)
for rank, idx in enumerate(ranked, 1):
    print(f"{rank}. doc#{idx} score={final_scores[idx]:.4f} :: {docs[idx]}")

실제 서비스에서는 필드별 BM25F와 한국어 형태소 분석기(예: Mecab, Khaiii)를 적용할 수 있다. PageRank는 오프라인 배치로 계산해 키-값 저장소에 보관하고, 질의 시점에 조인한다.

색인 신선도와 랭킹 품질 사이의 선택

세그먼트는 불변성을 유지하고 백그라운드 병합으로 쓰기와 읽기의 간섭을 줄인다. 높은 가용성을 얻는 대신 디스크 사용량은 일시적으로 증가한다.

단순 선형 결합은 해석하기 쉽다. LTR은 품질이 우수할 수 있지만 피처와 라벨 비용이 증가한다. 민감 피처를 사용할 때는 최소화·익명화 원칙을 적용하고 개인정보와 편향을 관리해야 한다.

PageRank 조작을 막기 위해 링크 농장을 탐지하고 신뢰 시드 기반 변형인 TrustRank를 도입할 수 있다. 다만 필터링이 과도하면 정당한 신규 페이지의 노출도 낮아질 수 있다.

NRT 색인은 초·분 단위 반영에 적합하고, PageRank는 일 배치로 계산한다. 캐시 계층을 둘 때는 TTL과 무효화 전략을 명확히 정해야 한다.