Skip to main content

fetchium_core/rank/
cluster.rs

1//! Result Clustering Engine (RCE) — semantic topic grouping.
2//!
3//! Novel algorithm: After ranking, cluster results into semantic topic groups
4//! using term-overlap similarity. Instead of a flat list, users see organized
5//! facets of their query.
6//!
7//! Uses single-pass agglomerative clustering with term-overlap Jaccard
8//! similarity. O(N²) but N is small (typically 10-30 results).
9
10use crate::types::ResultItem;
11use std::collections::HashSet;
12
13/// A cluster of related results.
14#[derive(Debug, Clone)]
15pub struct ResultCluster {
16    /// Human-readable label derived from common terms.
17    pub label: String,
18    /// Results in this cluster, in rank order.
19    pub results: Vec<ResultItem>,
20    /// Terms that are common across most results in this cluster.
21    pub common_terms: Vec<String>,
22}
23
24/// Configuration for clustering.
25#[derive(Debug, Clone)]
26pub struct ClusterConfig {
27    /// Minimum Jaccard similarity to consider results as related.
28    pub similarity_threshold: f64,
29    /// Maximum number of clusters.
30    pub max_clusters: usize,
31    /// Minimum results per cluster (smaller clusters get merged into "Other").
32    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
45/// Cluster a list of ranked results into topic groups.
46///
47/// Results within each cluster maintain their relative ranking order.
48pub 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    // Extract term sets for each result
62    let term_sets: Vec<HashSet<String>> = results.iter().map(extract_terms).collect();
63
64    // Compute pairwise similarity matrix
65    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    // Greedy clustering: assign each result to the most similar cluster
76    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        // Find the best existing cluster for this result
81        let mut best_cluster = None;
82        let mut best_sim = config.similarity_threshold;
83
84        for (c_idx, cluster) in clusters.iter().enumerate() {
85            // Average similarity to cluster members
86            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                // Start a new cluster
102                assignments[i] = Some(clusters.len());
103                clusters.push(vec![i]);
104            }
105        }
106    }
107
108    // Build output clusters
109    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    // Merge small clusters into "Other"
139    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    // Limit to max clusters
158    output.truncate(config.max_clusters);
159
160    output
161}
162
163/// Extract significant terms from a result.
164fn 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
173/// Jaccard similarity between two term sets.
174fn 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
186/// Find terms common to most results in a cluster.
187fn 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    // Count term frequency across results
195    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
212/// Extract a label from a single result.
213fn 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
222/// Common words to exclude from clustering terms.
223fn 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, // low threshold to detect topical grouping
292            min_cluster_size: 2,
293            ..Default::default()
294        };
295
296        let clusters = cluster_results(&results, &config);
297
298        // Should have at least 2 clusters (Rust safety vs Python data)
299        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}