use std::collections::HashSet;
use crate::rank::bm25_score;
use crate::types::ResultItem;
#[derive(Debug, Clone)]
pub struct DiversityConfig {
pub lambda: f64,
pub max_results: usize,
pub similarity_threshold: f64,
}
impl Default for DiversityConfig {
fn default() -> Self {
Self {
lambda: 0.7,
max_results: 20,
similarity_threshold: 0.8,
}
}
}
pub fn mmr_rerank(
results: &[ResultItem],
query: &str,
config: &DiversityConfig,
) -> Vec<ResultItem> {
if results.is_empty() {
return vec![];
}
let n = results.len();
let limit = config.max_results.min(n);
let relevances: Vec<f64> = results
.iter()
.map(|r| {
r.score.unwrap_or_else(|| {
let text = format!("{} {}", r.title, r.snippet);
bm25_score(&text, query)
})
})
.collect();
let term_sets: Vec<HashSet<String>> = results.iter().map(term_set).collect();
let mut selected_indices: Vec<usize> = Vec::with_capacity(limit);
let mut remaining: Vec<usize> = (0..n).collect();
let seed = remaining
.iter()
.copied()
.max_by(|&a, &b| {
relevances[a]
.partial_cmp(&relevances[b])
.unwrap_or(std::cmp::Ordering::Equal)
})
.expect("remaining is non-empty");
selected_indices.push(seed);
remaining.retain(|&i| i != seed);
while selected_indices.len() < limit && !remaining.is_empty() {
let mut best_idx = remaining[0];
let mut best_mmr = f64::NEG_INFINITY;
for &candidate in &remaining {
let rel = relevances[candidate];
let max_sim = selected_indices
.iter()
.map(|&s| jaccard(&term_sets[candidate], &term_sets[s]))
.fold(0.0_f64, f64::max);
let mmr = config.lambda * rel - (1.0 - config.lambda) * max_sim;
if mmr > best_mmr {
best_mmr = mmr;
best_idx = candidate;
}
}
selected_indices.push(best_idx);
remaining.retain(|&i| i != best_idx);
}
selected_indices
.iter()
.enumerate()
.map(|(rank, &orig)| {
let mut item = results[orig].clone();
item.rank = (rank + 1) as u32;
item.score = Some(relevances[orig]);
item
})
.collect()
}
pub fn diversity_score(results: &[ResultItem]) -> f64 {
if results.len() <= 1 {
return 1.0;
}
let term_sets: Vec<HashSet<String>> = results.iter().map(term_set).collect();
let n = term_sets.len();
let mut total_sim = 0.0;
let mut pair_count = 0u64;
for i in 0..n {
for j in (i + 1)..n {
total_sim += jaccard(&term_sets[i], &term_sets[j]);
pair_count += 1;
}
}
if pair_count == 0 {
return 1.0;
}
let mean_sim = total_sim / pair_count as f64;
1.0 - mean_sim
}
fn term_set(item: &ResultItem) -> HashSet<String> {
let text = format!("{} {}", item.title, item.snippet).to_lowercase();
text.split(|c: char| !c.is_alphanumeric())
.filter(|t| t.len() >= 3)
.filter(|t| !is_stop_word(t))
.map(|t| t.to_string())
.collect()
}
fn jaccard(a: &HashSet<String>, b: &HashSet<String>) -> f64 {
if a.is_empty() && b.is_empty() {
return 0.0;
}
let intersection = a.intersection(b).count();
let union = a.union(b).count();
if union == 0 {
return 0.0;
}
intersection as f64 / union as f64
}
fn is_stop_word(word: &str) -> bool {
const STOP: &[&str] = &[
"the", "and", "for", "are", "but", "not", "you", "all", "can", "her", "was", "one", "our",
"out", "has", "had", "how", "its", "may", "new", "now", "old", "see", "way", "who", "did",
"get", "let", "say", "she", "too", "use", "this", "that", "with", "have", "from", "they",
"been", "some", "when", "what", "your", "each", "make", "like", "just", "than", "them",
"very", "will", "more", "also",
];
STOP.contains(&word)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::types::BackendId;
fn make_item(title: &str, snippet: &str, score: Option<f64>) -> ResultItem {
ResultItem {
title: title.into(),
url: format!(
"https://{}.example.com",
title.to_lowercase().replace(' ', "-")
),
snippet: snippet.into(),
rank: 0,
backend: BackendId::DuckDuckGo,
score,
published_date: None,
}
}
#[test]
fn empty_input_returns_empty() {
let out = mmr_rerank(&[], "anything", &DiversityConfig::default());
assert!(out.is_empty());
}
#[test]
fn single_result_returned_as_is() {
let items = vec![make_item("Rust Guide", "Learn Rust programming", Some(0.9))];
let out = mmr_rerank(&items, "rust", &DiversityConfig::default());
assert_eq!(out.len(), 1);
assert_eq!(out[0].title, "Rust Guide");
assert_eq!(out[0].rank, 1);
}
#[test]
fn diverse_results_preserved() {
let items = vec![
make_item(
"Rust Programming",
"Systems language with safety guarantees",
Some(0.8),
),
make_item(
"Python Data Science",
"Pandas and NumPy for analysis",
Some(0.7),
),
make_item(
"Go Concurrency",
"Goroutines and channels for parallelism",
Some(0.6),
),
];
let out = mmr_rerank(&items, "programming languages", &DiversityConfig::default());
assert_eq!(out.len(), 3);
let titles: Vec<&str> = out.iter().map(|r| r.title.as_str()).collect();
assert!(titles.contains(&"Rust Programming"));
assert!(titles.contains(&"Python Data Science"));
assert!(titles.contains(&"Go Concurrency"));
}
#[test]
fn duplicate_results_deprioritized_by_mmr() {
let items = vec![
make_item(
"Rust Safety",
"Rust memory safety borrow checker",
Some(0.9),
),
make_item(
"Rust Safety Guide",
"Rust memory safety borrow checker explained",
Some(0.85),
),
make_item("Python Intro", "Python beginner tutorial basics", Some(0.5)),
];
let config = DiversityConfig {
lambda: 0.5,
..DiversityConfig::default()
};
let out = mmr_rerank(&items, "programming", &config);
assert_eq!(out.len(), 3);
let last = &out[2];
assert_eq!(last.title, "Rust Safety Guide");
}
#[test]
fn lambda_one_is_pure_relevance() {
let items = vec![
make_item("Low Score", "unrelated content", Some(0.1)),
make_item("High Score", "very relevant document", Some(0.9)),
make_item("Mid Score", "somewhat related", Some(0.5)),
];
let config = DiversityConfig {
lambda: 1.0,
..DiversityConfig::default()
};
let out = mmr_rerank(&items, "relevant", &config);
assert_eq!(out[0].title, "High Score");
assert_eq!(out[1].title, "Mid Score");
assert_eq!(out[2].title, "Low Score");
}
#[test]
fn lambda_zero_is_pure_diversity() {
let items = vec![
make_item(
"Rust Safety",
"Rust borrow checker memory safety",
Some(0.9),
),
make_item(
"Rust Safety Copy",
"Rust borrow checker memory safety",
Some(0.85),
),
make_item("Python Web", "Django Flask web framework", Some(0.3)),
];
let config = DiversityConfig {
lambda: 0.0,
..DiversityConfig::default()
};
let out = mmr_rerank(&items, "programming", &config);
assert_eq!(out[0].title, "Rust Safety");
assert_eq!(out[1].title, "Python Web");
assert_eq!(out[2].title, "Rust Safety Copy");
}
#[test]
fn diversity_score_unique_results_near_one() {
let items = vec![
make_item("Rust Programming", "Systems language safety", None),
make_item("Python Data Science", "Pandas NumPy analysis", None),
make_item("Go Networking", "HTTP servers goroutines", None),
];
let score = diversity_score(&items);
assert!(
score > 0.8,
"Expected diversity > 0.8 for unique results, got {score}"
);
}
#[test]
fn diversity_score_identical_results_near_zero() {
let items = vec![
make_item("Rust Safety", "Rust borrow checker memory safety", None),
make_item("Rust Safety", "Rust borrow checker memory safety", None),
make_item("Rust Safety", "Rust borrow checker memory safety", None),
];
let score = diversity_score(&items);
assert!(
score < 0.01,
"Expected diversity < 0.01 for identical results, got {score}"
);
}
#[test]
fn max_results_respected() {
let items: Vec<ResultItem> = (0..10)
.map(|i| {
make_item(
&format!("Topic {i}"),
&format!("Unique content about subject number {i}"),
Some(1.0 - i as f64 * 0.05),
)
})
.collect();
let config = DiversityConfig {
max_results: 3,
..DiversityConfig::default()
};
let out = mmr_rerank(&items, "topic", &config);
assert_eq!(out.len(), 3);
for (i, r) in out.iter().enumerate() {
assert_eq!(r.rank, (i + 1) as u32);
}
}
}