use std::collections::HashMap;
use crate::text;
pub const DEFAULT_K1: f32 = 1.2;
pub const DEFAULT_B: f32 = 0.75;
#[derive(Debug, Clone)]
pub struct Bm25 {
k1: f32,
b: f32,
avgdl: f32,
tf: Vec<HashMap<String, u32>>,
len: Vec<u32>,
df: HashMap<String, u32>,
}
impl Bm25 {
pub fn from_tokens(docs: &[Vec<String>]) -> Self {
Self::from_tokens_with(docs, DEFAULT_K1, DEFAULT_B)
}
pub fn from_tokens_with(docs: &[Vec<String>], k1: f32, b: f32) -> Self {
let mut tf: Vec<HashMap<String, u32>> = Vec::with_capacity(docs.len());
let mut df: HashMap<String, u32> = HashMap::new();
let mut len = Vec::with_capacity(docs.len());
let mut total = 0u64;
for doc in docs {
let mut counts: HashMap<String, u32> = HashMap::new();
for t in doc {
*counts.entry(t.clone()).or_insert(0) += 1;
}
for term in counts.keys() {
*df.entry(term.clone()).or_insert(0) += 1;
}
total += doc.len() as u64;
len.push(doc.len() as u32);
tf.push(counts);
}
let avgdl = if docs.is_empty() { 0.0 } else { total as f32 / docs.len() as f32 };
Bm25 { k1, b, avgdl: avgdl.max(1.0), tf, len, df }
}
pub fn from_texts<S: AsRef<str>>(docs: &[S]) -> Self {
let toks: Vec<Vec<String>> = docs.iter().map(|d| text::tokenize(d.as_ref())).collect();
Self::from_tokens(&toks)
}
pub fn len(&self) -> usize {
self.tf.len()
}
pub fn is_empty(&self) -> bool {
self.tf.is_empty()
}
fn idf(&self, term: &str) -> f32 {
let n = self.tf.len() as f32;
let df = self.df.get(term).copied().unwrap_or(0) as f32;
(1.0 + (n - df + 0.5) / (df + 0.5)).ln()
}
pub fn score(&self, query: &[String], idx: usize) -> f32 {
let Some(tf) = self.tf.get(idx) else { return 0.0 };
let dl = self.len[idx] as f32;
let norm = 1.0 - self.b + self.b * (dl / self.avgdl);
let mut total = 0.0;
for term in query {
let f = tf.get(term).copied().unwrap_or(0) as f32;
if f == 0.0 {
continue;
}
total += self.idf(term) * (f * (self.k1 + 1.0)) / (f + self.k1 * norm);
}
total
}
pub fn score_all(&self, query: &[String]) -> Vec<f32> {
(0..self.tf.len()).map(|i| self.score(query, i)).collect()
}
}
#[cfg(test)]
mod tests {
use super::*;
fn corpus() -> Vec<&'static str> {
vec![
"rust async runtime tokio handles concurrent io",
"python crawlers use a lot of memory and are slow",
"tokio and rayon combine async io with data parallelism",
"the weather today is mild and pleasant",
]
}
#[test]
fn ranks_the_on_topic_document_first() {
let idx = Bm25::from_texts(&corpus());
let q = text::tokenize("tokio rayon parallelism");
let scores = idx.score_all(&q);
let best =
scores.iter().enumerate().max_by(|a, b| a.1.total_cmp(b.1)).map(|(i, _)| i).unwrap();
assert_eq!(best, 2, "scores were {scores:?}");
assert_eq!(scores[3], 0.0, "off-topic doc should score zero");
}
#[test]
fn rare_terms_outweigh_common_ones() {
let idx = Bm25::from_texts(&corpus());
assert!(idx.idf("rayon") > idx.idf("and"));
}
#[test]
fn works_on_korean_text() {
let docs = ["러스트 비동기 런타임", "파이썬 크롤러 메모리", "비동기 병렬 처리"];
let idx = Bm25::from_texts(&docs);
let scores = idx.score_all(&text::tokenize("비동기 런타임"));
assert!(scores[0] > scores[1], "{scores:?}");
}
#[test]
fn empty_corpus_is_safe() {
let idx = Bm25::from_texts::<&str>(&[]);
assert!(idx.is_empty());
assert!(idx.score_all(&text::tokenize("anything")).is_empty());
}
}