use serde::{Deserialize, Serialize};
use std::collections::{HashMap, HashSet};
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct Bm25Params {
pub k1: f32,
pub b: f32,
}
impl Default for Bm25Params {
fn default() -> Self {
Self { k1: 1.2, b: 0.75 }
}
}
pub fn tokenize(text: &str) -> Vec<String> {
text.to_lowercase()
.split(|c: char| !c.is_alphanumeric() && c != '_' && c != '-')
.filter(|t| !t.is_empty() && t.len() > 1)
.map(|t| t.to_string())
.collect()
}
#[derive(Debug, Clone, Default, Serialize, Deserialize)]
pub struct Bm25Index {
inverted_index: HashMap<String, Vec<(u64, u32)>>,
doc_lengths: HashMap<u64, usize>,
params: Bm25Params,
#[serde(default)]
total_tokens: Option<usize>,
#[serde(default)]
document_terms: HashMap<u64, Vec<String>>,
}
impl Bm25Index {
pub fn new() -> Self {
Self {
inverted_index: HashMap::new(),
doc_lengths: HashMap::new(),
params: Bm25Params::default(),
total_tokens: Some(0),
document_terms: HashMap::new(),
}
}
pub fn with_params(params: Bm25Params) -> Self {
Self {
inverted_index: HashMap::new(),
doc_lengths: HashMap::new(),
params,
total_tokens: Some(0),
document_terms: HashMap::new(),
}
}
pub fn index_document(&mut self, doc_id: u64, text: &str) {
if self.doc_lengths.contains_key(&doc_id) {
self.remove_document(doc_id);
}
let tokens = tokenize(text);
if tokens.is_empty() {
self.doc_lengths.insert(doc_id, 0);
return;
}
*self
.total_tokens
.get_or_insert_with(|| self.doc_lengths.values().sum()) += tokens.len();
self.doc_lengths.insert(doc_id, tokens.len());
let mut term_counts: HashMap<String, u32> = HashMap::new();
for token in tokens {
*term_counts.entry(token).or_insert(0) += 1;
}
self.document_terms
.insert(doc_id, term_counts.keys().cloned().collect());
for (term, count) in term_counts {
self.inverted_index
.entry(term)
.or_default()
.push((doc_id, count));
}
}
pub fn remove_document(&mut self, doc_id: u64) {
let total = *self
.total_tokens
.get_or_insert_with(|| self.doc_lengths.values().sum());
if let Some(length) = self.doc_lengths.remove(&doc_id) {
self.total_tokens = Some(total.saturating_sub(length));
if let Some(terms) = self.document_terms.remove(&doc_id) {
for term in terms {
if let Some(postings) = self.inverted_index.get_mut(&term) {
postings.retain(|(id, _)| *id != doc_id);
if postings.is_empty() {
self.inverted_index.remove(&term);
}
}
}
} else {
for postings in self.inverted_index.values_mut() {
postings.retain(|(id, _)| *id != doc_id);
}
self.inverted_index
.retain(|_, postings| !postings.is_empty());
}
}
}
pub fn total_docs(&self) -> usize {
self.doc_lengths.len()
}
pub fn avg_doc_length(&self) -> f32 {
if self.doc_lengths.is_empty() {
return 0.0;
}
let sum = self
.total_tokens
.unwrap_or_else(|| self.doc_lengths.values().sum());
sum as f32 / self.doc_lengths.len() as f32
}
pub fn search(&self, query: &str, top_k: usize) -> Vec<(u64, f32)> {
let mut result = self.search_filtered(query, top_k, None);
if let Some(&(_, max_score)) = result.first()
&& max_score > 0.0
{
for (_, score) in &mut result {
*score /= max_score;
}
}
result
}
pub fn search_filtered(
&self,
query: &str,
top_k: usize,
allowed: Option<&HashSet<u64>>,
) -> Vec<(u64, f32)> {
self.search_where(query, top_k, allowed, |_| true)
}
pub(crate) fn search_where(
&self,
query: &str,
top_k: usize,
allowed: Option<&HashSet<u64>>,
accept: impl Fn(u64) -> bool,
) -> Vec<(u64, f32)> {
let query_tokens = tokenize(query);
if top_k == 0 || query_tokens.is_empty() || self.doc_lengths.is_empty() {
return Vec::new();
}
let n_docs = self.total_docs() as f32;
let avgdl = self.avg_doc_length();
let k1 = self.params.k1;
let b = self.params.b;
let mut scores: HashMap<u64, f32> = HashMap::new();
let mut unique_query_terms: HashSet<&str> = HashSet::new();
for token in &query_tokens {
if !unique_query_terms.insert(token.as_str()) {
continue; }
if let Some(postings) = self.inverted_index.get(token.as_str()) {
let doc_freq = postings.len() as f32;
let idf = ((n_docs - doc_freq + 0.5) / (doc_freq + 0.5) + 1.0)
.ln()
.max(0.1);
for &(doc_id, tf) in postings {
if allowed.is_some_and(|ids| !ids.contains(&doc_id)) || !accept(doc_id) {
continue;
}
let doc_len = *self.doc_lengths.get(&doc_id).unwrap_or(&0) as f32;
let tf_val = tf as f32;
let denom = tf_val + k1 * (1.0 - b + b * (doc_len / avgdl.max(1.0)));
let term_score = idf * (tf_val * (k1 + 1.0)) / denom.max(0.0001);
*scores.entry(doc_id).or_insert(0.0) += term_score;
}
}
}
let mut result: Vec<(u64, f32)> = scores.into_iter().collect();
let compare =
|a: &(u64, f32), b: &(u64, f32)| b.1.total_cmp(&a.1).then_with(|| a.0.cmp(&b.0));
if result.len() > top_k {
result.select_nth_unstable_by(top_k, compare);
}
result.truncate(top_k);
result.sort_by(compare);
result
}
}
pub fn reciprocal_rank_fusion(
ranked_lists: &[(&[u64], f32)],
k: f32,
top_n: usize,
) -> Vec<(u64, f32)> {
let mut scores: HashMap<u64, f32> = HashMap::new();
for &(doc_ids, weight) in ranked_lists {
for (rank_idx, &doc_id) in doc_ids.iter().enumerate() {
let rank = (rank_idx + 1) as f32;
let rrf_score = weight / (k + rank);
*scores.entry(doc_id).or_insert(0.0) += rrf_score;
}
}
let mut fused: Vec<(u64, f32)> = scores.into_iter().collect();
fused.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal));
fused.truncate(top_n);
fused
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_bm25_tokenization() {
let tokens = tokenize("Hello, World! This is TapirusDB-2026.");
assert_eq!(
tokens,
vec!["hello", "world", "this", "is", "tapirusdb-2026"]
);
}
#[test]
fn test_bm25_search_scoring() {
let mut index = Bm25Index::new();
index.index_document(1, "The quick brown fox jumps over the lazy dog");
index.index_document(
2,
"The engineering team built TapirusDB for embedded edge AI memory",
);
index.index_document(3, "TapirusDB is ultra fast and safe in Pure Safe Rust");
let results = index.search("TapirusDB Safe Rust", 5);
assert!(!results.is_empty());
assert_eq!(results[0].0, 3);
assert_eq!(results[0].1, 1.0); }
#[test]
fn test_bm25_remove_document() {
let mut index = Bm25Index::new();
index.index_document(1, "Artificial intelligence agent memory");
index.index_document(2, "Database engine persistence");
assert_eq!(index.total_docs(), 2);
index.remove_document(1);
assert_eq!(index.total_docs(), 1);
let res = index.search("intelligence", 5);
assert!(res.is_empty());
}
#[test]
fn test_reciprocal_rank_fusion() {
let list_a: Vec<u64> = vec![10, 20, 30];
let list_b: Vec<u64> = vec![20, 10, 40];
let fused = reciprocal_rank_fusion(&[(&list_a, 1.0), (&list_b, 1.0)], 60.0, 3);
assert!(!fused.is_empty());
assert!(fused[0].0 == 10 || fused[0].0 == 20);
assert!(fused[0].1 > 0.03);
}
}