1use crate::types::ResultItem;
11use std::collections::HashMap;
12use tracing::debug;
13
14#[derive(Debug, Clone, Copy, PartialEq, Eq)]
21pub struct SimHash(pub u64);
22
23impl SimHash {
24 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 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 #[inline]
62 pub fn distance(&self, other: &SimHash) -> u32 {
63 (self.0 ^ other.0).count_ones()
64 }
65
66 #[inline]
70 pub fn is_similar(&self, other: &SimHash, threshold: u32) -> bool {
71 self.distance(other) <= threshold
72 }
73}
74
75#[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
88const TRACKING_PARAMS: &[&str] = &[
92 "utm_source",
94 "utm_medium",
95 "utm_campaign",
96 "utm_term",
97 "utm_content",
98 "utm_id",
99 "utm_name",
100 "fbclid",
102 "gclid",
103 "msclkid",
104 "twclid",
105 "igshid",
106 "ref",
108 "source",
109 "_ga",
110 "_gl",
111 "mc_cid",
112 "mc_eid",
113 "si",
114 "feature",
115 "app",
116];
117
118pub 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 parsed.set_fragment(None);
136
137 if parsed.host_str().unwrap_or("").ends_with("arxiv.org") {
140 let path = parsed.path().to_owned();
141 let normalized_path = {
143 let p = if let Some(stripped) = path.strip_suffix(".pdf") {
145 stripped
146 } else {
147 &path
148 };
149 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 let normalized_path = normalized_path.replace("/pdf/", "/abs/");
163 parsed.set_path(&normalized_path);
164 }
165
166 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 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
196pub fn deduplicate(mut results: Vec<ResultItem>, simhash_threshold: u32) -> Vec<ResultItem> {
213 let original_len = results.len();
214
215 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 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 }
231 None => {
232 url_seen.insert(key, phase1.len());
233 phase1.push(item);
234 }
235 }
236 }
237
238 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 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 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 #[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 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 let h3 = fnv1a_64(b"world");
356 assert_ne!(h1, h3);
357 }
358
359 #[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 }
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 #[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); 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), 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); 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 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 assert_eq!(deduped.len(), 5, "All 5 distinct items should be kept");
575 }
576}