BM25 알고리즘: 검색 엔진은 어떻게 관련도 순으로 정렬할까
검색창에 단어를 넣으면 결과가 주르륵 나오는데요. 그런데 이 결과들의 “순서”는 누가 정하는 걸까요? 단순히 단어가 들어간 문서를 다 모아서 보여주기만 한다면, 정작 내가 찾던 문서는 47번째쯤에 묻혀 있을 수도 있어요. 검색이 쓸모 있으려면 가장 관련 있는 문서가 맨 위로 올라와야 합니다.
이 “관련도 순 정렬”을 책임지는 게 바로 랭킹 함수입니다. 그리고 지난 20여 년간 텍스트 검색의 사실상 표준으로 자리 잡은 랭킹 함수가 바로 BM25예요. Elasticsearch, OpenSearch, Apache Lucene, SQLite FTS5, 그리고 tantivy로 만드는 Rust 풀텍스트 검색에서 출력되는 점수가 모두 기본적으로 BM25 점수입니다. 즉 우리가 평소에 쓰는 검색 엔진 속에서 묵묵히 돌아가고 있던 알고리즘이죠.
이번 글에서는 BM25가 어떤 문제를 풀기 위해 등장했는지, 수식이 무엇을 의미하는지, 그리고 실제로 점수가 어떻게 매겨지는지를 직접 계산해보면서 익혀보겠습니다. 이름은 거창해 보여도 핵심 아이디어는 의외로 직관적이에요.
단어 빈도에서 시작하기
문서가 검색어와 얼마나 관련 있는지를 재는 가장 단순한 방법은 “검색어가 몇 번 나왔는지” 세는 겁니다. “검색 엔진”을 찾는다면 “검색”과 “엔진”이 많이 등장하는 문서가 더 관련 있을 가능성이 높겠죠. 이렇게 특정 단어가 문서에 등장한 횟수를 단어 빈도(Term Frequency, 이하 TF)라고 부릅니다.
그런데 TF만으로는 부족해요. 예를 들어 “그리고”, “하는”, “있다” 같은 단어는 거의 모든 문서에 잔뜩 나오지만, 이런 단어가 많다고 관련도가 높은 건 아니잖아요. 변별력이 없는 거죠. 반대로 “BM25” 같은 희귀한 단어는 몇 안 되는 문서에만 나오니까, 이 단어가 들어 있다는 사실 자체가 강력한 신호가 됩니다.
이 직관을 수치로 만든 게 역문서 빈도(Inverse Document Frequency, 이하 IDF)입니다. 전체 문서 중에서 그 단어를 포함한 문서가 적을수록 IDF가 커지도록 설계해서, 흔한 단어의 가중치는 낮추고 희귀한 단어의 가중치는 높입니다. 이 둘을 곱한 TF × IDF가 바로 그 유명한 TF-IDF예요. 오랫동안 텍스트 검색과 분류의 기본기 역할을 해왔습니다.
TF-IDF의 두 가지 약점
TF-IDF는 훌륭한 출발점이지만, 실제 검색에 쓰다 보면 두 가지 아쉬운 점이 드러납니다.
첫 번째는 단어 빈도가 점수에 선형적으로 반영된다는 점입니다. “검색”이라는 단어가 10번 나온 문서가 5번 나온 문서보다 정말 정확히 2배 더 관련 있을까요? 현실은 그렇지 않아요. 1번 나오던 게 2번이 되면 관련도가 꽤 올라가지만, 50번 나오던 게 51번이 된다고 해서 의미 있게 더 관련 있어지지는 않습니다. 어느 순간부터는 더 나와봐야 거기서 거기인 거죠. 그런데 TF-IDF는 이걸 무시하고 빈도를 그대로 곱해버립니다.
두 번째는 문서 길이를 제대로 다루지 못한다는 점입니다. 긴 문서는 단순히 길다는 이유만으로 어떤 단어든 더 많이 포함하게 됩니다. 1만 단어짜리 문서에서 “검색”이 10번 나온 것과, 50단어짜리 짧은 메모에서 “검색”이 10번 나온 것은 의미가 전혀 달라요. 짧은 글에서 10번이면 그 글의 핵심 주제일 가능성이 크지만, 긴 글에서 10번은 그냥 스쳐 지나간 단어일 수 있거든요.
BM25는 바로 이 두 가지 약점을 정조준해서 보완한 알고리즘입니다. 이름의 BM은 Best Matching의 줄임말이고, 25는 1970~80년대 정보 검색 연구 과정에서 나온 여러 실험 버전 중 25번째라는 데서 유래했어요. 그래서 가끔 Okapi BM25라고도 부르는데, Okapi는 이 알고리즘이 처음 구현된 검색 시스템의 이름입니다.
BM25 수식 들여다보기
먼저 전체 수식을 한번 보겠습니다. 쿼리 Q에 들어 있는 각 단어 q에 대해 점수를 계산해서 모두 더하는 구조예요.
score(D, Q) = Σ IDF(q) · f(q, D) · (k1 + 1)
q ─────────────────────────────────
f(q, D) + k1 · (1 - b + b · |D|/avgdl)기호가 많아 보이지만 하나씩 뜯어보면 어렵지 않습니다. 우선 등장하는 값들의 뜻부터 정리할게요.
f(q, D)— 문서D에 단어q가 등장한 횟수, 즉 앞에서 본 TF입니다.|D|— 문서D의 길이(단어 개수)입니다.avgdl— 전체 문서들의 평균 길이(average document length)입니다.IDF(q)— 단어q의 역문서 빈도입니다.k1— 단어 빈도 포화 정도를 조절하는 파라미터로, 보통 1.2~2.0을 씁니다.b— 문서 길이 정규화 강도를 조절하는 파라미터로, 보통 0.75를 씁니다.
이제 이 수식이 앞에서 말한 TF-IDF의 두 약점을 어떻게 해결하는지, 부분별로 나눠서 살펴보겠습니다.
k1: 단어 빈도를 포화시키기
수식에서 f(q, D)가 들어간 분수 부분이 단어 빈도를 다루는 대목입니다. 문서 길이 항을 잠시 무시하고 보면 분수는 대략 이렇게 생겼어요.
f · (k1 + 1)
───────────
f + k1여기서 f를 점점 키워보면 재미있는 일이 벌어집니다. f가 아주 커지면 분자와 분모 모두 f가 지배하게 되어 분수 전체가 k1 + 1이라는 값으로 수렴해요. 즉 단어가 아무리 많이 나와도 점수에는 상한선이 생깁니다. 이걸 단어 빈도 포화(saturation)라고 부릅니다.
실제로 k1 = 1.2일 때 등장 횟수에 따라 이 항이 어떻게 변하는지 계산해봤습니다.
k1 = 1.2
def tf_component(f, k1):
return f * (k1 + 1) / (f + k1)
print("등장횟수 f | BM25 TF항 | TF-IDF(선형)")
for f in [1, 2, 3, 5, 10, 20, 100]:
print(f" {f:>4} | {tf_component(f, k1):.3f} | {f}")등장횟수 f | BM25 TF항 | TF-IDF(선형)
1 | 1.000 | 1
2 | 1.375 | 2
3 | 1.571 | 3
5 | 1.774 | 5
10 | 1.964 | 10
20 | 2.075 | 20
100 | 2.174 | 100오른쪽의 TF-IDF는 등장 횟수에 비례해서 끝없이 커지는데요. 왼쪽 BM25는 1번에서 2번으로 갈 때는 1.0에서 1.375로 확 뛰지만, 20번에서 100번으로 갈 때는 2.075에서 2.174로 거의 움직이지 않습니다. k1 = 1.2이니까 아무리 많이 나와도 k1 + 1 = 2.2를 넘지 못하고 그 근처로 수렴하는 거예요.
이게 바로 우리의 직관과 맞아떨어집니다. 처음 몇 번의 등장은 관련도를 크게 끌어올리지만, 그 이후의 반복은 점점 의미가 줄어든다는 거죠. k1 값을 키우면 포화가 더 늦게 일어나서 빈도를 더 오래 반영하고, 줄이면 더 빨리 포화돼서 한두 번 등장만으로도 충분하다고 판단합니다.
b: 문서 길이로 점수 보정하기
이제 분모에 있던 (1 - b + b · |D|/avgdl) 항을 볼 차례입니다. 여기서 눈여겨볼 건 |D|/avgdl, 즉 이 문서의 길이가 평균에 비해 얼마나 긴지를 나타내는 비율이에요.
문서가 평균보다 길면(|D|/avgdl > 1) 이 항이 커지고, 분모가 커지니까 전체 점수는 내려갑니다. 반대로 평균보다 짧으면 점수가 올라가요. 긴 문서가 단순히 길다는 이유로 누리던 이점을 깎아내리는 거죠. 우리가 앞에서 짚었던 “긴 글에서 10번 vs 짧은 글에서 10번” 문제를 정확히 이 항이 처리합니다.
b는 이 보정을 얼마나 세게 적용할지 정하는 손잡이입니다. b = 0이면 길이 항이 통째로 사라져서 문서 길이를 아예 무시하고, b = 1이면 길이에 완전히 비례해서 정규화합니다. 기본값 0.75는 그 사이 어딘가에서 적당히 보정하겠다는 뜻이에요. 짧은 문서가 유리하긴 하되 지나치게 유리하지는 않도록 균형을 잡은 값입니다.
IDF: 흔한 단어 눌러두기
마지막 조각은 IDF(q)입니다. 앞에서 IDF의 개념은 짚었으니, BM25가 실제로 쓰는 공식을 보겠습니다. 검색 엔진 구현체(특히 Lucene)에서 널리 쓰는 형태는 이렇습니다.
IDF(q) = ln( 1 + (N - n(q) + 0.5) / (n(q) + 0.5) )여기서 N은 전체 문서 수, n(q)는 단어 q를 포함한 문서 수입니다. n(q)가 작을수록(희귀할수록) 분수가 커지고, 로그를 씌운 결과인 IDF도 커집니다. 0.5라는 보정값이 군데군데 들어가 있는데, 이건 분모가 0이 되는 걸 막고 수치를 안정시키기 위한 장치예요. 그리고 바깥의 1 + 덕분에 IDF가 음수로 내려가는 일도 없습니다.
핵심만 기억하면 됩니다. 거의 모든 문서에 나오는 흔한 단어는 IDF가 0에 가까워서 점수에 거의 기여하지 못하고, 몇몇 문서에만 나오는 희귀한 단어는 IDF가 커서 점수를 크게 좌우합니다.
직접 계산해보기
이론을 다 봤으니 이제 BM25를 처음부터 끝까지 직접 구현해서 돌려보겠습니다. 문서 4개짜리 아주 작은 코퍼스를 만들고, “검색 엔진”이라는 쿼리로 순위를 매겨볼게요.
import math
corpus = [
"파이썬 파이썬 으로 검색 엔진 만들기",
"검색 엔진 의 동작 원리 와 색인 구조",
"자바스크립트 비동기 프로그래밍 입문",
"검색 검색 검색 알고리즘 정리 노트 모음 자료 링크 메모",
]
docs = [d.split() for d in corpus]
N = len(docs)
avgdl = sum(len(d) for d in docs) / N
def idf(term):
n = sum(1 for d in docs if term in d) # term을 포함한 문서 수
return math.log(1 + (N - n + 0.5) / (n + 0.5))
def bm25(query, doc, k1=1.2, b=0.75):
score = 0.0
dl = len(doc)
for term in query:
f = doc.count(term)
if f == 0:
continue
numer = f * (k1 + 1)
denom = f + k1 * (1 - b + b * dl / avgdl)
score += idf(term) * numer / denom
return score
query = "검색 엔진".split()
print(f"문서 수 N = {N}, 평균 문서 길이 avgdl = {avgdl:.2f}")
print(f"IDF(검색) = {idf('검색'):.4f}")
print(f"IDF(엔진) = {idf('엔진'):.4f}\n")
ranked = sorted(range(N), key=lambda i: bm25(query, docs[i]), reverse=True)
for rank, i in enumerate(ranked, 1):
print(f"{rank}위 score={bm25(query, docs[i]):.4f} (길이 {len(docs[i])}) {corpus[i]}")문서 수 N = 4, 평균 문서 길이 avgdl = 7.00
IDF(검색) = 0.3567
IDF(엔진) = 0.6931
쿼리: 검색 엔진
1위 score=1.1150 (길이 6) 파이썬 파이썬 으로 검색 엔진 만들기
2위 score=0.9919 (길이 8) 검색 엔진 의 동작 원리 와 색인 구조
3위 score=0.5133 (길이 10) 검색 검색 검색 알고리즘 정리 노트 모음 자료 링크 메모
4위 score=0.0000 (길이 4) 자바스크립트 비동기 프로그래밍 입문원리만 이해하면 언어는 거들 뿐이라, 같은 로직을 자바스크립트로도 그대로 옮길 수 있어요. 별도 라이브러리 없이 표준 문법만으로 충분합니다.
const corpus = [
"파이썬 파이썬 으로 검색 엔진 만들기",
"검색 엔진 의 동작 원리 와 색인 구조",
"자바스크립트 비동기 프로그래밍 입문",
"검색 검색 검색 알고리즘 정리 노트 모음 자료 링크 메모",
];
const docs = corpus.map((d) => d.split(" "));
const N = docs.length;
const avgdl = docs.reduce((sum, d) => sum + d.length, 0) / N;
function idf(term) {
const n = docs.filter((d) => d.includes(term)).length; // term을 포함한 문서 수
return Math.log(1 + (N - n + 0.5) / (n + 0.5));
}
function bm25(query, doc, k1 = 1.2, b = 0.75) {
const dl = doc.length;
let score = 0;
for (const term of query) {
const f = doc.filter((t) => t === term).length;
if (f === 0) continue;
const numer = f * (k1 + 1);
const denom = f + k1 * (1 - b + (b * dl) / avgdl);
score += (idf(term) * numer) / denom;
}
return score;
}
const query = "검색 엔진".split(" ");
const ranked = [...docs.keys()].sort(
(a, b) => bm25(query, docs[b]) - bm25(query, docs[a]),
);
for (const [rank, i] of ranked.entries()) {
console.log(
`${rank + 1}위 score=${bm25(query, docs[i]).toFixed(4)} (길이 ${docs[i].length}) ${corpus[i]}`,
);
}실행하면 IDF 값부터 최종 순위까지 위 파이썬 결과와 한 글자도 다르지 않게 나옵니다. BM25는 결국 사칙연산과 로그 하나로 이뤄진 알고리즘이라, 어떤 언어로 옮겨도 똑같은 점수가 나오는 거죠.
결과를 하나씩 음미해보면 BM25의 성격이 그대로 드러납니다.
우선 IDF부터 보면 IDF(엔진)이 IDF(검색)보다 큽니다. “검색”은 4개 문서 중 3개에 나오지만 “엔진”은 2개에만 나오거든요. 더 희귀한 “엔진”이 들어 있다는 게 더 강한 신호인 거죠.
가장 흥미로운 건 3위와 4위입니다. 3위 문서에는 “검색”이 무려 3번이나 나오는데도, 두 단어를 한 번씩만 가진 1위·2위 문서보다 점수가 낮아요. 한 단어를 반복하는 것보다 쿼리의 여러 단어를 골고루 포함하는 게 더 유리하다는 뜻입니다. 게다가 이 문서는 길이가 10으로 평균(7)보다 길어서 길이 정규화로 점수가 더 깎였고요. 앞에서 배운 단어 빈도 포화와 문서 길이 정규화가 동시에 작동한 결과예요.
그리고 1위와 2위를 비교하면, 둘 다 “검색”과 “엔진”을 한 번씩 가졌지만 더 짧은 1위 문서(길이 6)가 2위 문서(길이 8)를 앞섰습니다. 같은 조건이면 짧은 문서가 이긴다는 길이 정규화의 효과를 깔끔하게 보여주죠. 마지막으로 쿼리 단어가 하나도 없는 4위 문서는 당연히 0점입니다.
라이브러리로 간단하게
원리를 이해했다면 실전에서는 직접 구현할 필요가 없습니다. 파이썬에는 rank_bm25라는 가벼운 라이브러리가 있어서 몇 줄이면 끝나요.
pip install rank_bm25from rank_bm25 import BM25Okapi
corpus = [
"파이썬으로 검색 엔진 만들기",
"검색 엔진의 동작 원리와 색인 구조",
"자바스크립트 비동기 프로그래밍 입문",
]
tokenized = [doc.split() for doc in corpus]
bm25 = BM25Okapi(tokenized)
query = "검색 엔진".split()
scores = bm25.get_scores(query)
for doc, s in sorted(zip(corpus, scores), key=lambda x: -x[1]):
print(f"{s:.4f} {doc}")0.6614 파이썬으로 검색 엔진 만들기
0.0957 검색 엔진의 동작 원리와 색인 구조
0.0000 자바스크립트 비동기 프로그래밍 입문토큰 분리만 직접 해서 넘겨주면 나머지는 라이브러리가 알아서 계산합니다. 점수의 절댓값은 우리가 직접 구현한 것과 다른데(파라미터 기본값과 IDF 변형이 조금 달라요), 순위는 같습니다. BM25에서 중요한 건 점수의 절댓값이 아니라 문서들 사이의 상대적인 순서니까요.
여기서 한 가지 짚고 갈 점은 토큰화의 중요성입니다. 위 예제는 한국어를 공백으로만 잘랐는데, 실제 한국어 검색에서는 “검색엔진”처럼 붙여 쓰거나 “검색을”, “검색이”처럼 조사가 붙으면 다른 단어로 취급돼서 매칭이 안 됩니다. 그래서 실무에서는 형태소 분석기로 조사와 어미를 떼어내는 전처리가 BM25 점수 못지않게 결과 품질을 좌우해요. 알고리즘이 아무리 정교해도 들어가는 단어가 엉망이면 좋은 순위가 나올 수 없거든요.
실무에서의 BM25
다행히 검색 엔진을 직접 만들 일은 드뭅니다. Elasticsearch나 OpenSearch는 기본 유사도 함수로 BM25를 채택하고 있고, 그 밑단의 Apache Lucene도 마찬가지예요. Rust 생태계라면 앞서 언급한 tantivy로 풀텍스트 검색을 구현할 때 별도 설정 없이 BM25 점수가 매겨집니다. 우리가 할 일은 보통 k1과 b 값을 데이터에 맞게 조정하는 정도예요.
SQLite 기반 앱이라면 별도 검색 엔진 없이도 SQLite FTS5로 전문 검색을 구현하면서 bm25() 함수를 바로 사용할 수 있습니다. 작은 블로그나 문서 검색에서는 이 조합만으로도 충분한 경우가 많아요.
파라미터 튜닝은 데이터의 성격을 보고 결정합니다. 문서 길이 편차가 크다면(짧은 제목과 긴 본문이 섞여 있다든지) b를 어떻게 두느냐가 결과를 크게 바꿉니다. 길이를 덜 신경 쓰고 싶으면 b를 0.75보다 낮추고요. 반대로 짧은 문서를 확실히 우대하고 싶으면 1에 가깝게 올립니다. k1은 같은 단어의 반복이 의미 있는 도메인(예: 키워드가 자주 반복되는 기술 문서)이라면 높이고, 한 번 언급으로 충분한 경우라면 낮춥니다. 정답은 없고, 검색 품질 지표를 보면서 실험으로 찾아가는 영역이에요.
물론 BM25에도 한계는 있습니다. 단어의 정확한 일치에 의존하기 때문에 의미는 같지만 표현이 다른 경우, 예컨대 “환불”로 검색하면 “결제 취소”가 적힌 문서를 찾지 못합니다. 이 빈틈을 메우는 게 임베딩 기반의 의미 검색이에요. 텍스트를 벡터로 바꿔 의미적으로 가까운 문서를 찾는 방식인데, 저장과 인덱싱은 PostgreSQL에 pgvector로 벡터 검색을 더하거나 Cloudflare Vectorize로 엣지에서 벡터 검색을 구현하는 글에서 다룬 적이 있습니다. 요즘 검색 시스템은 BM25 같은 키워드 검색과 벡터 검색을 함께 쓰는 하이브리드 방식이 대세인데, 키워드 검색의 정확성과 의미 검색의 유연함을 둘 다 챙기려는 거죠.
마치며
BM25는 이름만 보면 복잡한 통계 모델 같지만, 알고 보면 “흔한 단어는 무시하고(IDF), 단어가 너무 많이 나와도 적당히 봐주고(k1으로 포화), 긴 문서가 길다는 이유만으로 유리하지 않게(b로 정규화)” 정렬하겠다는 상식적인 아이디어들의 조합이었습니다. 각 파라미터가 어떤 직관을 담고 있는지 이해하고 나면, 검색 결과가 이상하게 나올 때 어디를 손봐야 할지 감이 잡힐 거예요.
검색 품질을 더 끌어올리고 싶다면 다음 단계로 형태소 분석기를 활용한 한국어 토큰화나, 키워드 검색과 벡터 검색을 결합하는 하이브리드 검색을 살펴보시길 권합니다. BM25는 그 모든 검색 시스템의 든든한 기본기로 계속 자리를 지킬 거고요.
알고리즘의 원래 정의가 궁금하다면 BM25를 정리한 The Probabilistic Relevance Framework: BM25 and Beyond 논문을 읽어보시면 좋습니다.
This work is licensed under
CC BY 4.0
