1use crate::types::ResultItem;
11use std::collections::HashSet;
12
13#[derive(Debug, Clone)]
15pub struct ResultCluster {
16 pub label: String,
18 pub results: Vec<ResultItem>,
20 pub common_terms: Vec<String>,
22}
23
24#[derive(Debug, Clone)]
26pub struct ClusterConfig {
27 pub similarity_threshold: f64,
29 pub max_clusters: usize,
31 pub min_cluster_size: usize,
33}
34
35impl Default for ClusterConfig {
36 fn default() -> Self {
37 Self {
38 similarity_threshold: 0.15,
39 max_clusters: 5,
40 min_cluster_size: 2,
41 }
42 }
43}
44
45pub fn cluster_results(results: &[ResultItem], config: &ClusterConfig) -> Vec<ResultCluster> {
49 if results.is_empty() {
50 return vec![];
51 }
52
53 if results.len() == 1 {
54 return vec![ResultCluster {
55 label: extract_label(&results[0]),
56 results: results.to_vec(),
57 common_terms: vec![],
58 }];
59 }
60
61 let term_sets: Vec<HashSet<String>> = results.iter().map(extract_terms).collect();
63
64 let n = results.len();
66 let mut similarity = vec![vec![0.0f64; n]; n];
67 for i in 0..n {
68 for j in (i + 1)..n {
69 let sim = jaccard_similarity(&term_sets[i], &term_sets[j]);
70 similarity[i][j] = sim;
71 similarity[j][i] = sim;
72 }
73 }
74
75 let mut assignments: Vec<Option<usize>> = vec![None; n];
77 let mut clusters: Vec<Vec<usize>> = vec![];
78
79 for i in 0..n {
80 let mut best_cluster = None;
82 let mut best_sim = config.similarity_threshold;
83
84 for (c_idx, cluster) in clusters.iter().enumerate() {
85 let avg_sim: f64 =
87 cluster.iter().map(|&j| similarity[i][j]).sum::<f64>() / cluster.len() as f64;
88
89 if avg_sim > best_sim {
90 best_sim = avg_sim;
91 best_cluster = Some(c_idx);
92 }
93 }
94
95 match best_cluster {
96 Some(c_idx) => {
97 clusters[c_idx].push(i);
98 assignments[i] = Some(c_idx);
99 }
100 None => {
101 assignments[i] = Some(clusters.len());
103 clusters.push(vec![i]);
104 }
105 }
106 }
107
108 let mut output: Vec<ResultCluster> = clusters
110 .iter()
111 .map(|indices| {
112 let cluster_results: Vec<ResultItem> =
113 indices.iter().map(|&i| results[i].clone()).collect();
114
115 let cluster_terms: Vec<&HashSet<String>> =
116 indices.iter().map(|&i| &term_sets[i]).collect();
117
118 let common = find_common_terms(&cluster_terms);
119 let label = if common.is_empty() {
120 extract_label(&cluster_results[0])
121 } else {
122 common
123 .iter()
124 .take(3)
125 .cloned()
126 .collect::<Vec<_>>()
127 .join(", ")
128 };
129
130 ResultCluster {
131 label,
132 results: cluster_results,
133 common_terms: common,
134 }
135 })
136 .collect();
137
138 let (large, small): (Vec<_>, Vec<_>) = output
140 .into_iter()
141 .partition(|c| c.results.len() >= config.min_cluster_size);
142
143 output = large;
144
145 if !small.is_empty() {
146 let other_results: Vec<ResultItem> = small.into_iter().flat_map(|c| c.results).collect();
147
148 if !other_results.is_empty() {
149 output.push(ResultCluster {
150 label: "Other".into(),
151 results: other_results,
152 common_terms: vec![],
153 });
154 }
155 }
156
157 output.truncate(config.max_clusters);
159
160 output
161}
162
163fn extract_terms(item: &ResultItem) -> HashSet<String> {
165 let text = format!("{} {}", item.title, item.snippet).to_lowercase();
166 text.split(|c: char| !c.is_alphanumeric())
167 .filter(|t| t.len() >= 3)
168 .filter(|t| !is_common_word(t))
169 .map(|t| t.to_string())
170 .collect()
171}
172
173fn jaccard_similarity(a: &HashSet<String>, b: &HashSet<String>) -> f64 {
175 if a.is_empty() && b.is_empty() {
176 return 0.0;
177 }
178 let intersection = a.intersection(b).count();
179 let union = a.union(b).count();
180 if union == 0 {
181 return 0.0;
182 }
183 intersection as f64 / union as f64
184}
185
186fn find_common_terms(term_sets: &[&HashSet<String>]) -> Vec<String> {
188 if term_sets.is_empty() {
189 return vec![];
190 }
191
192 let threshold = (term_sets.len() as f64 * 0.6).ceil() as usize;
193
194 let mut counts: std::collections::HashMap<&str, usize> = std::collections::HashMap::new();
196 for ts in term_sets {
197 for term in ts.iter() {
198 *counts.entry(term.as_str()).or_insert(0) += 1;
199 }
200 }
201
202 let mut common: Vec<String> = counts
203 .into_iter()
204 .filter(|(_, count)| *count >= threshold)
205 .map(|(term, _)| term.to_string())
206 .collect();
207
208 common.sort();
209 common
210}
211
212fn extract_label(item: &ResultItem) -> String {
214 let title = &item.title;
215 if title.len() <= 40 {
216 title.clone()
217 } else {
218 format!("{}...", &title[..37])
219 }
220}
221
222fn is_common_word(word: &str) -> bool {
224 const COMMON: &[&str] = &[
225 "the", "and", "for", "are", "but", "not", "you", "all", "can", "her", "was", "one", "our",
226 "out", "has", "had", "how", "its", "may", "new", "now", "old", "see", "way", "who", "did",
227 "get", "let", "say", "she", "too", "use", "this", "that", "with", "have", "from", "they",
228 "been", "some", "when", "what", "your", "each", "make", "like", "just", "than", "them",
229 "very", "will", "more", "also",
230 ];
231 COMMON.contains(&word)
232}
233
234#[cfg(test)]
235mod tests {
236 use super::*;
237 use crate::types::BackendId;
238
239 fn make_item(title: &str, snippet: &str) -> ResultItem {
240 ResultItem {
241 title: title.into(),
242 url: format!("https://{}.com", title.to_lowercase().replace(' ', "-")),
243 snippet: snippet.into(),
244 rank: 1,
245 backend: BackendId::DuckDuckGo,
246 score: Some(0.5),
247 published_date: None,
248 }
249 }
250
251 #[test]
252 fn empty_input_empty_output() {
253 let clusters = cluster_results(&[], &ClusterConfig::default());
254 assert!(clusters.is_empty());
255 }
256
257 #[test]
258 fn single_result_single_cluster() {
259 let results = vec![make_item("Rust Guide", "Learn Rust programming")];
260 let clusters = cluster_results(&results, &ClusterConfig::default());
261 assert_eq!(clusters.len(), 1);
262 assert_eq!(clusters[0].results.len(), 1);
263 }
264
265 #[test]
266 fn similar_results_clustered_together() {
267 let results = vec![
268 make_item(
269 "Rust Memory Safety",
270 "Rust borrow checker prevents memory bugs in systems code",
271 ),
272 make_item(
273 "Rust Ownership Model",
274 "Ownership and borrowing in Rust for safe concurrency",
275 ),
276 make_item(
277 "Rust Lifetimes Explained",
278 "Understanding lifetimes and references in Rust compiler",
279 ),
280 make_item(
281 "Python Data Science",
282 "Pandas, NumPy, and matplotlib for data analysis",
283 ),
284 make_item(
285 "Python Machine Learning",
286 "Scikit-learn and TensorFlow for training ML models",
287 ),
288 ];
289
290 let config = ClusterConfig {
291 similarity_threshold: 0.08, min_cluster_size: 2,
293 ..Default::default()
294 };
295
296 let clusters = cluster_results(&results, &config);
297
298 assert!(
300 clusters.len() >= 2,
301 "Expected at least 2 clusters, got {} with labels: {:?}",
302 clusters.len(),
303 clusters.iter().map(|c| &c.label).collect::<Vec<_>>()
304 );
305 }
306
307 #[test]
308 fn respects_max_clusters() {
309 let results: Vec<ResultItem> = (0..20)
310 .map(|i| {
311 make_item(
312 &format!("Topic {i}"),
313 &format!("Unique content about subject {i}"),
314 )
315 })
316 .collect();
317
318 let config = ClusterConfig {
319 max_clusters: 3,
320 min_cluster_size: 1,
321 ..Default::default()
322 };
323
324 let clusters = cluster_results(&results, &config);
325 assert!(clusters.len() <= 3, "Should respect max_clusters");
326 }
327
328 #[test]
329 fn jaccard_identical_sets() {
330 let a: HashSet<String> = ["rust", "web"].iter().map(|s| s.to_string()).collect();
331 let b: HashSet<String> = ["rust", "web"].iter().map(|s| s.to_string()).collect();
332 assert!((jaccard_similarity(&a, &b) - 1.0).abs() < 0.01);
333 }
334
335 #[test]
336 fn jaccard_disjoint_sets() {
337 let a: HashSet<String> = ["rust", "web"].iter().map(|s| s.to_string()).collect();
338 let b: HashSet<String> = ["python", "django"].iter().map(|s| s.to_string()).collect();
339 assert!((jaccard_similarity(&a, &b)).abs() < 0.01);
340 }
341
342 #[test]
343 fn cluster_labels_not_empty() {
344 let results = vec![
345 make_item("Rust Programming", "Systems programming with Rust"),
346 make_item("Rust Memory Safety", "Memory safety in Rust language"),
347 ];
348 let clusters = cluster_results(&results, &ClusterConfig::default());
349 for cluster in &clusters {
350 assert!(
351 !cluster.label.is_empty(),
352 "Cluster label should not be empty"
353 );
354 }
355 }
356}