Skip to main content

fetchium_core/search/
dedup.rs

1//! Cross-source deduplication — URL normalization + SimHash content similarity.
2//!
3//! Two-phase deduplication pipeline:
4//! 1. **URL dedup**: Normalize URLs (strip tracking params, fragments, trailing slash),
5//!    then exact-match. Keeps the higher-scored item when duplicates are found.
6//! 2. **SimHash dedup**: Compute 64-bit SimHash of `title + snippet`. Items whose
7//!    Hamming distance is ≤ `threshold` (default 6, i.e. ≥90% similarity) are
8//!    considered near-duplicates; only the first is kept.
9
10use crate::types::ResultItem;
11use std::collections::HashMap;
12use tracing::debug;
13
14// ── SimHash ────────────────────────────────────────────────────────────────────
15
16/// 64-bit SimHash fingerprint for near-duplicate content detection.
17///
18/// Based on Charikar's locality-sensitive hashing algorithm:
19/// tokenise → hash each token with FNV-1a → accumulate ±1 per bit → sign-collapse.
20#[derive(Debug, Clone, Copy, PartialEq, Eq)]
21pub struct SimHash(pub u64);
22
23impl SimHash {
24    /// Compute a SimHash fingerprint from arbitrary text.
25    ///
26    /// Algorithm:
27    /// 1. Split text into whitespace-delimited tokens, lowercased.
28    /// 2. For each token: compute FNV-1a-64 hash; for each bit position,
29    ///    add +1 if the bit is set, −1 otherwise.
30    /// 3. Collapse: bit[i] = 1 iff counter[i] > 0.
31    pub fn compute(text: &str) -> Self {
32        let mut counters = [0i32; 64];
33
34        for word in text.split_whitespace() {
35            let word = word.to_lowercase();
36            // Strip leading/trailing punctuation
37            let word = word.trim_matches(|c: char| !c.is_alphanumeric());
38            if word.len() < 2 {
39                continue;
40            }
41            let hash = fnv1a_64(word.as_bytes());
42            for (bit, counter) in counters.iter_mut().enumerate() {
43                if (hash >> bit) & 1 == 1 {
44                    *counter += 1;
45                } else {
46                    *counter -= 1;
47                }
48            }
49        }
50
51        let mut fingerprint = 0u64;
52        for (bit, &counter) in counters.iter().enumerate() {
53            if counter > 0 {
54                fingerprint |= 1u64 << bit;
55            }
56        }
57        SimHash(fingerprint)
58    }
59
60    /// Hamming distance between two fingerprints (number of differing bits, 0–64).
61    #[inline]
62    pub fn distance(&self, other: &SimHash) -> u32 {
63        (self.0 ^ other.0).count_ones()
64    }
65
66    /// Returns `true` if the two fingerprints are similar (Hamming distance ≤ threshold).
67    ///
68    /// A threshold of 6 means ≤6/64 bits differ (≥90% bit-level agreement).
69    #[inline]
70    pub fn is_similar(&self, other: &SimHash, threshold: u32) -> bool {
71        self.distance(other) <= threshold
72    }
73}
74
75/// FNV-1a 64-bit hash (fast, non-cryptographic).
76#[inline]
77fn fnv1a_64(bytes: &[u8]) -> u64 {
78    const FNV_OFFSET: u64 = 14_695_981_039_346_656_037;
79    const FNV_PRIME: u64 = 1_099_511_628_211;
80    let mut hash = FNV_OFFSET;
81    for &byte in bytes {
82        hash ^= byte as u64;
83        hash = hash.wrapping_mul(FNV_PRIME);
84    }
85    hash
86}
87
88// ── URL normalisation ──────────────────────────────────────────────────────────
89
90/// Common tracking/analytics query parameters to strip during URL normalisation.
91const TRACKING_PARAMS: &[&str] = &[
92    // UTM (Google Analytics)
93    "utm_source",
94    "utm_medium",
95    "utm_campaign",
96    "utm_term",
97    "utm_content",
98    "utm_id",
99    "utm_name",
100    // Social platform trackers
101    "fbclid",
102    "gclid",
103    "msclkid",
104    "twclid",
105    "igshid",
106    // Generic referral/tracking
107    "ref",
108    "source",
109    "_ga",
110    "_gl",
111    "mc_cid",
112    "mc_eid",
113    "si",
114    "feature",
115    "app",
116];
117
118/// Normalise a URL for deduplication.
119///
120/// Transformations applied:
121/// - Strip URL fragment (`#section`)
122/// - Remove common tracking query parameters (UTM, fbclid, gclid, …)
123/// - Strip trailing slash on non-root paths
124/// - Lowercase the host
125///
126/// Falls back to `url.to_lowercase()` if the URL cannot be parsed.
127pub fn normalize_url(url: &str) -> String {
128    if url.is_empty() {
129        return String::new();
130    }
131
132    match url::Url::parse(url) {
133        Ok(mut parsed) => {
134            // Strip fragment
135            parsed.set_fragment(None);
136
137            // ArXiv version normalization: /abs/2301.12345v3 → /abs/2301.12345
138            // Ensures different versions of the same paper are deduped as one URL.
139            if parsed.host_str().unwrap_or("").ends_with("arxiv.org") {
140                let path = parsed.path().to_owned();
141                // Match /abs/NNNN.NNNNvN or /pdf/NNNN.NNNNvN.pdf patterns
142                let normalized_path = {
143                    // Strip trailing version like v1, v2, v12
144                    let p = if let Some(stripped) = path.strip_suffix(".pdf") {
145                        stripped
146                    } else {
147                        &path
148                    };
149                    // Remove vN suffix from the paper ID
150                    if let Some(v_pos) = p.rfind('v') {
151                        let after_v = &p[v_pos + 1..];
152                        if !after_v.is_empty() && after_v.chars().all(|c| c.is_ascii_digit()) {
153                            p[..v_pos].to_owned()
154                        } else {
155                            p.to_owned()
156                        }
157                    } else {
158                        p.to_owned()
159                    }
160                };
161                // Also normalize /pdf/ → /abs/ so PDF and abstract links dedup
162                let normalized_path = normalized_path.replace("/pdf/", "/abs/");
163                parsed.set_path(&normalized_path);
164            }
165
166            // Filter out tracking query parameters
167            let filtered: Vec<(String, String)> = parsed
168                .query_pairs()
169                .filter(|(k, _)| !TRACKING_PARAMS.contains(&k.as_ref()))
170                .map(|(k, v)| (k.into_owned(), v.into_owned()))
171                .collect();
172
173            if filtered.is_empty() {
174                parsed.set_query(None);
175            } else {
176                let qs = filtered
177                    .iter()
178                    .map(|(k, v)| format!("{k}={v}"))
179                    .collect::<Vec<_>>()
180                    .join("&");
181                parsed.set_query(Some(&qs));
182            }
183
184            // Strip trailing slash on non-root paths (e.g. /article/ → /article)
185            let mut s = parsed.to_string();
186            let path = parsed.path();
187            if s.ends_with('/') && path != "/" {
188                s.pop();
189            }
190            s
191        }
192        Err(_) => url.to_lowercase(),
193    }
194}
195
196// ── Deduplication ──────────────────────────────────────────────────────────────
197
198/// Deduplicate a list of `ResultItem`s using URL normalisation + SimHash similarity.
199///
200/// **Phase 1 — URL dedup**: Groups results by normalised URL. When two items
201/// share a URL, the one with the higher `score` (or the earlier one if equal) is kept.
202///
203/// **Phase 2 — SimHash dedup**: Scans remaining results for near-duplicate content
204/// (Hamming distance ≤ `simhash_threshold`). Only the first of each cluster is kept.
205///
206/// **Re-ranking**: After deduplication, `rank` fields are reassigned from 1 upward.
207///
208/// # Arguments
209/// * `results` — Items from one or more backends (mixed ranking acceptable).
210/// * `simhash_threshold` — Maximum Hamming distance to consider near-duplicate
211///   (0 = exact match only, 64 = everything matches; default 6 ≈ 90% similarity).
212pub fn deduplicate(mut results: Vec<ResultItem>, simhash_threshold: u32) -> Vec<ResultItem> {
213    let original_len = results.len();
214
215    // ── Phase 1: URL dedup ────────────────────────────────────────────────────
216    let mut url_seen: HashMap<String, usize> = HashMap::with_capacity(results.len());
217    let mut phase1: Vec<ResultItem> = Vec::with_capacity(results.len());
218
219    for item in results.drain(..) {
220        let key = normalize_url(&item.url);
221        match url_seen.get(&key).copied() {
222            Some(existing_idx) => {
223                // Keep the higher-scored item
224                let existing_score = phase1[existing_idx].score.unwrap_or(0.0);
225                let new_score = item.score.unwrap_or(0.0);
226                if new_score > existing_score {
227                    phase1[existing_idx] = item;
228                }
229                // (else: discard the new item — the existing one is better)
230            }
231            None => {
232                url_seen.insert(key, phase1.len());
233                phase1.push(item);
234            }
235        }
236    }
237
238    // ── Phase 2: SimHash near-dup dedup ──────────────────────────────────────
239    let mut seen_hashes: Vec<SimHash> = Vec::with_capacity(phase1.len());
240    let mut final_results: Vec<ResultItem> = Vec::with_capacity(phase1.len());
241
242    for item in phase1 {
243        let text = format!("{} {}", item.title, item.snippet);
244        let hash = SimHash::compute(&text);
245
246        let is_near_dup = seen_hashes
247            .iter()
248            .any(|h| h.is_similar(&hash, simhash_threshold));
249
250        if !is_near_dup {
251            seen_hashes.push(hash);
252            final_results.push(item);
253        }
254    }
255
256    // ── Re-assign contiguous ranks ────────────────────────────────────────────
257    for (i, item) in final_results.iter_mut().enumerate() {
258        item.rank = (i + 1) as u32;
259    }
260
261    debug!(
262        "Dedup: {} → {} results (URL+SimHash, threshold={})",
263        original_len,
264        final_results.len(),
265        simhash_threshold
266    );
267
268    final_results
269}
270
271#[cfg(test)]
272mod tests {
273    use super::*;
274    use crate::types::BackendId;
275
276    // ── Helpers ───────────────────────────────────────────────────────────────
277
278    fn make_item(title: &str, url: &str, snippet: &str) -> ResultItem {
279        ResultItem {
280            title: title.into(),
281            url: url.into(),
282            snippet: snippet.into(),
283            rank: 1,
284            backend: BackendId::DuckDuckGo,
285            score: None,
286            published_date: None,
287        }
288    }
289
290    fn make_item_with_score(title: &str, url: &str, snippet: &str, score: f64) -> ResultItem {
291        ResultItem {
292            title: title.into(),
293            url: url.into(),
294            snippet: snippet.into(),
295            rank: 1,
296            backend: BackendId::DuckDuckGo,
297            score: Some(score),
298            published_date: None,
299        }
300    }
301
302    // ── SimHash tests ─────────────────────────────────────────────────────────
303
304    #[test]
305    fn simhash_identical_texts_distance_zero() {
306        let h1 = SimHash::compute("hello world foo bar baz");
307        let h2 = SimHash::compute("hello world foo bar baz");
308        assert_eq!(h1.distance(&h2), 0);
309    }
310
311    #[test]
312    fn simhash_different_domains_high_distance() {
313        let h1 = SimHash::compute("quantum physics nuclear reactor neutrons electrons protons");
314        let h2 = SimHash::compute("chocolate cake baking sugar flour vanilla cream butter");
315        assert!(
316            h1.distance(&h2) > 6,
317            "Expected high distance, got {}",
318            h1.distance(&h2)
319        );
320    }
321
322    #[test]
323    fn simhash_near_identical_texts_low_distance() {
324        let h1 = SimHash::compute("Rust programming language systems safe fast reliable");
325        // Adding a couple of words shouldn't push beyond a moderate threshold
326        let h2 =
327            SimHash::compute("Rust programming language systems safe fast reliable concurrent");
328        assert!(
329            h1.distance(&h2) <= 20,
330            "Expected low distance for similar text, got {}",
331            h1.distance(&h2)
332        );
333    }
334
335    #[test]
336    fn simhash_is_similar_exact_match() {
337        let h = SimHash::compute("same text");
338        assert!(h.is_similar(&h, 0));
339    }
340
341    #[test]
342    fn simhash_is_similar_threshold() {
343        let h1 = SimHash::compute("abc def ghi jkl");
344        let h2 = SimHash::compute("abc def ghi jkl");
345        assert!(h1.is_similar(&h2, 6));
346        assert!(!h1.is_similar(&h2, 0) || h1.distance(&h2) == 0);
347    }
348
349    #[test]
350    fn fnv1a_deterministic() {
351        let h1 = fnv1a_64(b"hello");
352        let h2 = fnv1a_64(b"hello");
353        assert_eq!(h1, h2);
354        // Different inputs → different hash (with very high probability)
355        let h3 = fnv1a_64(b"world");
356        assert_ne!(h1, h3);
357    }
358
359    // ── URL normalization tests ───────────────────────────────────────────────
360
361    #[test]
362    fn normalize_url_strips_utm_params() {
363        let url = "https://example.com/article?id=42&utm_source=twitter&utm_medium=social";
364        let norm = normalize_url(url);
365        assert!(norm.contains("id=42"), "id=42 should be kept in: {norm}");
366        assert!(
367            !norm.contains("utm_source"),
368            "utm_source should be stripped from: {norm}"
369        );
370        assert!(
371            !norm.contains("utm_medium"),
372            "utm_medium should be stripped from: {norm}"
373        );
374    }
375
376    #[test]
377    fn normalize_url_strips_fbclid() {
378        let url = "https://example.com/page?fbclid=abc123";
379        let norm = normalize_url(url);
380        assert!(
381            !norm.contains("fbclid"),
382            "fbclid should be stripped from: {norm}"
383        );
384    }
385
386    #[test]
387    fn normalize_url_strips_fragment() {
388        let url = "https://example.com/page#section-2";
389        let norm = normalize_url(url);
390        assert!(
391            !norm.contains('#'),
392            "Fragment should be stripped from: {norm}"
393        );
394        assert!(
395            norm.contains("example.com/page"),
396            "Path should be kept in: {norm}"
397        );
398    }
399
400    #[test]
401    fn normalize_url_strips_trailing_slash_on_path() {
402        let url = "https://example.com/article/";
403        let norm = normalize_url(url);
404        assert!(
405            !norm.ends_with('/'),
406            "Trailing slash should be stripped from: {norm}"
407        );
408        assert!(norm.ends_with("article"), "Path should be kept in: {norm}");
409    }
410
411    #[test]
412    fn normalize_url_keeps_root_slash() {
413        let url = "https://example.com/";
414        let norm = normalize_url(url);
415        assert!(
416            norm.contains("example.com"),
417            "Host should be present in: {norm}"
418        );
419        // Root slash is preserved (it's the only path component)
420    }
421
422    #[test]
423    fn normalize_url_strips_all_tracking_no_remaining_query() {
424        let url = "https://example.com/page?utm_source=x&utm_medium=y&utm_campaign=z";
425        let norm = normalize_url(url);
426        assert!(
427            !norm.contains('?'),
428            "All params stripped, so no '?' in: {norm}"
429        );
430    }
431
432    #[test]
433    fn normalize_url_empty_string() {
434        assert_eq!(normalize_url(""), "");
435    }
436
437    #[test]
438    fn normalize_url_invalid_url_lowercased() {
439        let url = "NOT A URL";
440        let norm = normalize_url(url);
441        assert_eq!(norm, "not a url");
442    }
443
444    // ── Deduplication tests ───────────────────────────────────────────────────
445
446    #[test]
447    fn deduplicate_removes_exact_url_duplicates() {
448        let items = vec![
449            make_item("Page A", "https://example.com/page", "content A"),
450            make_item(
451                "Page A dup",
452                "https://example.com/page",
453                "content A duplicate",
454            ),
455            make_item("Page B", "https://other.com/page", "different content B"),
456        ];
457        let deduped = deduplicate(items, 6);
458        assert_eq!(deduped.len(), 2, "Expected 2 results after URL dedup");
459    }
460
461    #[test]
462    fn deduplicate_removes_url_duplicates_with_tracking_params() {
463        let items = vec![
464            make_item("Page A", "https://example.com/page", "content"),
465            make_item(
466                "Page A twitter",
467                "https://example.com/page?utm_source=twitter",
468                "content",
469            ),
470            make_item("Page B", "https://other.com/different", "different content"),
471        ];
472        let deduped = deduplicate(items, 6);
473        assert_eq!(deduped.len(), 2, "Tracking-param variant should be deduped");
474    }
475
476    #[test]
477    fn deduplicate_keeps_higher_scored_url_duplicate() {
478        let items = vec![
479            make_item_with_score("Low score", "https://example.com/page", "content", 0.3),
480            make_item_with_score("High score", "https://example.com/page", "content", 0.9),
481        ];
482        let deduped = deduplicate(items, 0); // threshold=0 to only do URL dedup
483        assert_eq!(deduped.len(), 1);
484        assert_eq!(deduped[0].title, "High score");
485    }
486
487    #[test]
488    fn deduplicate_removes_simhash_near_duplicates() {
489        let text = "Rust is a systems programming language focused on safety and performance";
490        let items = vec![
491            make_item("Rust A", "https://a.com", text),
492            make_item("Rust B", "https://b.com", text), // Same content, different URL
493            make_item(
494                "Python",
495                "https://python.org",
496                "Python is a dynamic scripting language for web development",
497            ),
498        ];
499        let deduped = deduplicate(items, 3); // Strict SimHash threshold
500                                             // Python should survive; the two Rust items with identical content should be deduped
501        let has_python = deduped.iter().any(|r| r.title == "Python");
502        assert!(has_python, "Python result should survive dedup");
503        assert!(
504            deduped.len() < 3,
505            "At least one Rust duplicate should be removed"
506        );
507    }
508
509    #[test]
510    fn deduplicate_reassigns_ranks_sequentially() {
511        let items = vec![
512            make_item("A", "https://a.com", "content about topic a"),
513            make_item("B", "https://b.com", "content about topic b"),
514            make_item("C", "https://c.com", "content about topic c"),
515        ];
516        let deduped = deduplicate(items, 6);
517        for (i, item) in deduped.iter().enumerate() {
518            assert_eq!(
519                item.rank,
520                (i + 1) as u32,
521                "Rank should be {} but was {}",
522                i + 1,
523                item.rank
524            );
525        }
526    }
527
528    #[test]
529    fn deduplicate_empty_input() {
530        let deduped = deduplicate(vec![], 6);
531        assert!(deduped.is_empty());
532    }
533
534    #[test]
535    fn deduplicate_single_item() {
536        let items = vec![make_item("Only", "https://only.com", "only content")];
537        let deduped = deduplicate(items, 6);
538        assert_eq!(deduped.len(), 1);
539        assert_eq!(deduped[0].rank, 1);
540    }
541
542    #[test]
543    fn deduplicate_preserves_unique_results() {
544        // Use clearly distinct topics so SimHash does not group them
545        let distinct_items = vec![
546            make_item(
547                "Rust compiler",
548                "https://rustlang.org",
549                "memory safety borrow checker lifetimes ownership systems",
550            ),
551            make_item(
552                "Machine learning",
553                "https://pytorch.org",
554                "neural networks gradient descent backpropagation training epochs",
555            ),
556            make_item(
557                "Database indexing",
558                "https://postgresql.org",
559                "btree btree index scan sequential lookup primary key",
560            ),
561            make_item(
562                "Network protocol",
563                "https://ietf.org",
564                "tcp ip handshake packets routing latency bandwidth",
565            ),
566            make_item(
567                "Cryptocurrency",
568                "https://bitcoin.org",
569                "blockchain hash proof-of-work mining consensus ledger",
570            ),
571        ];
572        let deduped = deduplicate(distinct_items, 6);
573        // All items are topically distinct — none should be removed
574        assert_eq!(deduped.len(), 5, "All 5 distinct items should be kept");
575    }
576}