use crate::domain::models::search_result::SearchResult;
use std::collections::hash_map::DefaultHasher;
use std::collections::HashSet;
use std::hash::{Hash, Hasher};
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum DeduplicationStrategy {
UrlOnly,
TitleOnly,
UrlAndTitle,
Smart,
}
#[derive(Debug, Clone)]
pub struct ContentFingerprintConfig {
pub enabled: bool,
pub algorithm: FingerprintAlgorithm,
pub fingerprint_size: usize,
pub simhash_threshold: u8,
}
impl Default for ContentFingerprintConfig {
fn default() -> Self {
Self {
enabled: true,
algorithm: FingerprintAlgorithm::SimHash,
fingerprint_size: 64,
simhash_threshold: 10, }
}
}
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum FingerprintAlgorithm {
Hash,
SimHash,
}
#[derive(Debug, Clone)]
pub struct DeduplicationConfig {
pub strategy: DeduplicationStrategy,
pub title_similarity_threshold: f32,
pub content_similarity_threshold: f32,
pub fingerprint_config: ContentFingerprintConfig,
pub case_sensitive: bool,
pub ignore_query_params: bool,
pub ignore_fragments: bool,
}
impl Default for DeduplicationConfig {
fn default() -> Self {
Self {
strategy: DeduplicationStrategy::Smart,
title_similarity_threshold: 0.85,
content_similarity_threshold: 0.8,
fingerprint_config: ContentFingerprintConfig::default(),
case_sensitive: false,
ignore_query_params: true,
ignore_fragments: true,
}
}
}
pub struct ResultDeduplicator {
config: DeduplicationConfig,
seen_urls: HashSet<String>,
seen_titles: HashSet<String>,
seen_fingerprints: HashSet<u64>,
}
impl ResultDeduplicator {
pub fn new(config: DeduplicationConfig) -> Self {
Self {
config,
seen_urls: HashSet::new(),
seen_titles: HashSet::new(),
seen_fingerprints: HashSet::new(),
}
}
pub fn with_default_config() -> Self {
Self::new(DeduplicationConfig::default())
}
fn normalize_url(&self, url: &str) -> String {
let mut normalized = url.to_string();
if self.config.ignore_fragments {
if let Some(pos) = normalized.rfind('#') {
normalized.truncate(pos);
}
}
let is_baidu_link = normalized.contains("baidu.com/link");
if self.config.ignore_query_params && !is_baidu_link {
if let Some(pos) = normalized.rfind('?') {
normalized.truncate(pos);
}
}
if !self.config.case_sensitive {
normalized = normalized.to_lowercase();
}
normalized = normalized.trim_end_matches('/').to_string();
normalized
}
fn normalize_title(&self, title: &str) -> String {
let mut normalized = title.to_string();
normalized = normalized.split_whitespace().collect::<Vec<_>>().join(" ");
if !self.config.case_sensitive {
normalized = normalized.to_lowercase();
}
normalized
}
fn generate_fingerprint(&self, content: &str) -> u64 {
match self.config.fingerprint_config.algorithm {
FingerprintAlgorithm::Hash => {
let mut hasher = DefaultHasher::new();
content.hash(&mut hasher);
hasher.finish()
}
FingerprintAlgorithm::SimHash => {
self.simhash(content)
}
}
}
fn simhash(&self, content: &str) -> u64 {
let words: Vec<&str> = content.split_whitespace().collect();
let mut hash_bits = vec![0i32; self.config.fingerprint_config.fingerprint_size];
for word in words {
let mut hasher = DefaultHasher::new();
word.hash(&mut hasher);
let word_hash = hasher.finish();
for (i, bit) in hash_bits
.iter_mut()
.enumerate()
.take(self.config.fingerprint_config.fingerprint_size)
{
if (word_hash >> (i % 64)) & 1 == 1 {
*bit += 1;
} else {
*bit -= 1;
}
}
}
let mut fingerprint = 0u64;
for (i, &bit) in hash_bits
.iter()
.enumerate()
.take(self.config.fingerprint_config.fingerprint_size.min(64))
{
if bit > 0 {
fingerprint |= 1 << i;
}
}
fingerprint
}
#[inline]
fn hamming_distance(hash1: u64, hash2: u64) -> u8 {
let xor = hash1 ^ hash2;
xor.count_ones() as u8
}
#[inline]
fn is_similar_by_fingerprint(&self, fingerprint: u64) -> bool {
if self.seen_fingerprints.contains(&fingerprint) {
return true;
}
for &existing_fingerprint in self.seen_fingerprints.iter() {
let distance = Self::hamming_distance(fingerprint, existing_fingerprint);
if distance <= self.config.fingerprint_config.simhash_threshold {
return true;
}
}
false
}
pub fn deduplicate(&mut self, results: Vec<SearchResult>) -> Vec<SearchResult> {
let mut unique_results = Vec::new();
let expected = results.len().min(1000);
self.seen_urls.reserve(expected);
self.seen_titles.reserve(expected);
self.seen_fingerprints.reserve(expected);
for result in results {
let normalized_url = self.normalize_url(&result.url);
let normalized_title = self.normalize_title(&result.title);
if self.is_duplicate(&normalized_url, &normalized_title) {
continue;
}
self.remember_unique(&normalized_url, &normalized_title);
unique_results.push(result);
}
unique_results
}
fn is_duplicate(&self, normalized_url: &str, normalized_title: &str) -> bool {
let url_exists = self.seen_urls.contains(normalized_url);
let title_exists = self.seen_titles.contains(normalized_title);
match self.config.strategy {
DeduplicationStrategy::UrlOnly => url_exists,
DeduplicationStrategy::TitleOnly => title_exists,
DeduplicationStrategy::UrlAndTitle => {
url_exists || title_exists
}
DeduplicationStrategy::Smart => {
url_exists
|| title_exists
|| (self.config.fingerprint_config.enabled
&& self.is_similar_by_fingerprint(self.generate_fingerprint(normalized_title)))
}
}
}
fn remember_unique(&mut self, normalized_url: &str, normalized_title: &str) {
self.seen_urls.insert(normalized_url.to_string());
self.seen_titles.insert(normalized_title.to_string());
if matches!(self.config.strategy, DeduplicationStrategy::Smart)
&& self.config.fingerprint_config.enabled
{
let fingerprint = self.generate_fingerprint(normalized_title);
self.seen_fingerprints.insert(fingerprint);
}
}
pub fn deduplicate_multi_engine(
&mut self,
engine_results: Vec<(String, Vec<SearchResult>)>,
) -> Vec<SearchResult> {
let mut all_results = Vec::new();
for (engine_name, results) in engine_results {
for mut result in results {
result.engine = engine_name.clone();
all_results.push(result);
}
}
self.deduplicate(all_results)
}
pub fn reset(&mut self) {
self.seen_urls.clear();
self.seen_titles.clear();
self.seen_fingerprints.clear();
}
pub fn get_stats(&self) -> DeduplicationStats {
DeduplicationStats {
seen_urls_count: self.seen_urls.len(),
seen_titles_count: self.seen_titles.len(),
seen_fingerprints_count: self.seen_fingerprints.len(),
}
}
}
#[derive(Debug, Clone)]
pub struct DeduplicationStats {
pub seen_urls_count: usize,
pub seen_titles_count: usize,
pub seen_fingerprints_count: usize,
}
#[cfg(test)]
mod tests {
use super::*;
use crate::domain::models::search_result::SearchResult;
fn create_test_result(url: &str, title: &str, description: Option<&str>) -> SearchResult {
SearchResult {
title: title.to_string(),
url: url.to_string(),
description: description.map(|d| d.to_string()),
engine: "test".to_string(),
score: 0.0,
published_time: None,
}
}
#[test]
fn test_url_deduplication() {
let mut dedup = ResultDeduplicator::with_default_config();
dedup.config.strategy = DeduplicationStrategy::UrlOnly;
let results = vec![
create_test_result("https://example.com/page1", "Title 1", None),
create_test_result("https://example.com/page1", "Title 2", None), create_test_result("https://example.com/page2", "Title 3", None),
];
let deduplicated = dedup.deduplicate(results);
assert_eq!(deduplicated.len(), 2);
assert_eq!(deduplicated[0].title, "Title 1");
assert_eq!(deduplicated[1].title, "Title 3");
}
#[test]
fn test_title_deduplication() {
let mut dedup = ResultDeduplicator::with_default_config();
dedup.config.strategy = DeduplicationStrategy::TitleOnly;
dedup.config.title_similarity_threshold = 0.9;
let results = vec![
create_test_result("https://example.com/page1", "Rust Programming Guide", None),
create_test_result("https://example.com/page2", "Rust Programming Guide", None), create_test_result(
"https://example.com/page3",
"Python Programming Guide",
None,
),
];
let deduplicated = dedup.deduplicate(results);
assert_eq!(deduplicated.len(), 2);
assert_eq!(deduplicated[0].title, "Rust Programming Guide");
assert_eq!(deduplicated[1].title, "Python Programming Guide");
}
#[test]
fn test_smart_deduplication() {
let mut dedup = ResultDeduplicator::with_default_config();
dedup.config.strategy = DeduplicationStrategy::Smart;
dedup.config.title_similarity_threshold = 0.9;
let results = vec![
create_test_result(
"https://example.com/page1",
"Rust Programming Guide",
Some("Learn Rust programming"),
),
create_test_result(
"https://example.com/page2",
"Rust Programming Guide",
Some("Learn Rust programming language"),
), create_test_result(
"https://example.com/page3",
"Python Programming Guide",
Some("Learn Python programming"),
),
];
let deduplicated = dedup.deduplicate(results);
assert_eq!(deduplicated.len(), 2);
}
#[test]
fn test_url_normalization() {
let dedup = ResultDeduplicator::with_default_config();
assert_eq!(
dedup.normalize_url("https://example.com/path?param=value#fragment"),
"https://example.com/path"
);
assert_eq!(
dedup.normalize_url("https://EXAMPLE.com/PATH/"),
"https://example.com/path"
);
}
#[test]
fn test_normalize_url_empty_string() {
let dedup = ResultDeduplicator::with_default_config();
assert_eq!(dedup.normalize_url(""), "");
}
#[test]
fn test_normalize_url_only_fragment() {
let dedup = ResultDeduplicator::with_default_config();
assert_eq!(
dedup.normalize_url("https://example.com#section"),
"https://example.com"
);
}
#[test]
fn test_normalize_url_only_query() {
let dedup = ResultDeduplicator::with_default_config();
assert_eq!(
dedup.normalize_url("https://example.com?a=1&b=2"),
"https://example.com"
);
}
#[test]
fn test_normalize_url_case_sensitive_config() {
let config = DeduplicationConfig {
case_sensitive: true,
..DeduplicationConfig::default()
};
let dedup = ResultDeduplicator::new(config);
assert_eq!(
dedup.normalize_url("https://EXAMPLE.com/PATH/"),
"https://EXAMPLE.com/PATH"
);
}
#[test]
fn test_normalize_url_keep_query_when_disabled() {
let config = DeduplicationConfig {
ignore_query_params: false,
ignore_fragments: false,
..DeduplicationConfig::default()
};
let dedup = ResultDeduplicator::new(config);
assert_eq!(
dedup.normalize_url("https://example.com/path?a=1#frag"),
"https://example.com/path?a=1#frag"
);
}
#[test]
fn test_normalize_title_whitespace_collapsed() {
let dedup = ResultDeduplicator::with_default_config();
assert_eq!(
dedup.normalize_title("Rust Programming Guide"),
"rust programming guide"
);
}
#[test]
fn test_normalize_title_leading_trailing_whitespace_trimmed() {
let dedup = ResultDeduplicator::with_default_config();
assert_eq!(dedup.normalize_title(" Rust Guide "), "rust guide");
}
#[test]
fn test_normalize_title_case_sensitive_config() {
let config = DeduplicationConfig {
case_sensitive: true,
..DeduplicationConfig::default()
};
let dedup = ResultDeduplicator::new(config);
assert_eq!(
dedup.normalize_title("Rust Programming Guide"),
"Rust Programming Guide"
);
}
#[test]
fn test_normalize_title_empty_string() {
let dedup = ResultDeduplicator::with_default_config();
assert_eq!(dedup.normalize_title(""), "");
}
#[test]
fn test_generate_fingerprint_deterministic() {
let dedup = ResultDeduplicator::with_default_config();
let fp1 = dedup.generate_fingerprint("rust programming language");
let fp2 = dedup.generate_fingerprint("rust programming language");
assert_eq!(fp1, fp2, "same content should produce same fingerprint");
}
#[test]
fn test_generate_fingerprint_different_content() {
let dedup = ResultDeduplicator::with_default_config();
let fp1 = dedup.generate_fingerprint("rust programming language");
let fp2 = dedup.generate_fingerprint("python scripting language");
assert_ne!(
fp1, fp2,
"different content should produce different fingerprint"
);
}
#[test]
fn test_generate_fingerprint_empty_content() {
let dedup = ResultDeduplicator::with_default_config();
let fp = dedup.generate_fingerprint("");
let fp2 = dedup.generate_fingerprint("");
assert_eq!(fp, fp2, "empty content should be deterministic");
}
#[test]
fn test_generate_fingerprint_hash_algorithm() {
let config = DeduplicationConfig {
fingerprint_config: ContentFingerprintConfig {
algorithm: FingerprintAlgorithm::Hash,
..ContentFingerprintConfig::default()
},
..DeduplicationConfig::default()
};
let dedup = ResultDeduplicator::new(config);
let fp1 = dedup.generate_fingerprint("test content");
let fp2 = dedup.generate_fingerprint("test content");
assert_eq!(fp1, fp2, "Hash algorithm should be deterministic");
}
#[test]
fn test_hamming_distance_identical_hashes() {
let hash = 0b1010_1010u64;
assert_eq!(ResultDeduplicator::hamming_distance(hash, hash), 0);
}
#[test]
fn test_hamming_distance_one_bit_difference() {
let hash1 = 0b1000u64;
let hash2 = 0b1001u64;
assert_eq!(ResultDeduplicator::hamming_distance(hash1, hash2), 1);
}
#[test]
fn test_hamming_distance_all_bits_different() {
assert_eq!(ResultDeduplicator::hamming_distance(0u64, u64::MAX), 64);
}
#[test]
fn test_deduplicate_empty_input() {
let mut dedup = ResultDeduplicator::with_default_config();
let results: Vec<SearchResult> = vec![];
let deduplicated = dedup.deduplicate(results);
assert!(deduplicated.is_empty());
}
#[test]
fn test_deduplicate_single_result_preserved() {
let mut dedup = ResultDeduplicator::with_default_config();
let results = vec![create_test_result("https://example.com", "Title", None)];
let deduplicated = dedup.deduplicate(results);
assert_eq!(deduplicated.len(), 1);
}
#[test]
fn test_deduplicate_all_duplicates_keeps_one() {
let mut dedup = ResultDeduplicator::with_default_config();
let results = vec![
create_test_result("https://example.com", "Same Title", None),
create_test_result("https://example.com", "Same Title", None),
create_test_result("https://example.com", "Same Title", None),
];
let deduplicated = dedup.deduplicate(results);
assert_eq!(deduplicated.len(), 1);
}
#[test]
fn test_reset_clears_all_state() {
let mut dedup = ResultDeduplicator::with_default_config();
let results = vec![
create_test_result("https://example.com", "Title 1", None),
create_test_result("https://example.com", "Title 1", None),
];
let first_pass = dedup.deduplicate(results.clone());
assert_eq!(first_pass.len(), 1);
dedup.reset();
let stats = dedup.get_stats();
assert_eq!(stats.seen_urls_count, 0);
assert_eq!(stats.seen_titles_count, 0);
assert_eq!(stats.seen_fingerprints_count, 0);
let second_pass = dedup.deduplicate(results);
assert_eq!(
second_pass.len(),
1,
"after reset, first result should pass again"
);
}
#[test]
fn test_get_stats_after_deduplication() {
let mut dedup = ResultDeduplicator::with_default_config();
let results = vec![
create_test_result("https://example.com/1", "Title 1", None),
create_test_result("https://example.com/2", "Title 2", None),
create_test_result("https://example.com/1", "Title 1", None), ];
dedup.deduplicate(results);
let stats = dedup.get_stats();
assert_eq!(stats.seen_urls_count, 2, "should have 2 unique URLs");
assert_eq!(stats.seen_titles_count, 2, "should have 2 unique titles");
}
#[test]
fn test_deduplicate_multi_engine_merges_and_deduplicates() {
let mut dedup = ResultDeduplicator::with_default_config();
let engine_results = vec![
(
"google".to_string(),
vec![
create_test_result("https://example.com/1", "Rust Guide", None),
create_test_result("https://example.com/2", "Go Guide", None),
],
),
(
"bing".to_string(),
vec![
create_test_result("https://example.com/1", "Rust Guide", None), create_test_result("https://example.com/3", "Python Guide", None),
],
),
];
let deduplicated = dedup.deduplicate_multi_engine(engine_results);
assert_eq!(
deduplicated.len(),
3,
"should have 3 unique results after cross-engine dedup"
);
assert_eq!(deduplicated[0].engine, "google");
assert_eq!(deduplicated[2].engine, "bing");
}
#[test]
fn test_url_and_title_strategy() {
let mut dedup = ResultDeduplicator::with_default_config();
dedup.config.strategy = DeduplicationStrategy::UrlAndTitle;
let results = vec![
create_test_result("https://example.com/1", "Title A", None),
create_test_result("https://example.com/2", "Title A", None), create_test_result("https://example.com/3", "Title C", None),
];
let deduplicated = dedup.deduplicate(results);
assert_eq!(
deduplicated.len(),
2,
"same title should trigger dedup in UrlAndTitle strategy"
);
}
#[test]
fn test_smart_deduplication_similar_by_hamming_distance() {
let mut dedup = ResultDeduplicator::with_default_config();
dedup.config.strategy = DeduplicationStrategy::Smart;
dedup.config.fingerprint_config.simhash_threshold = 64;
let results = vec![
create_test_result("https://example.com/1", "Rust Programming Guide", None),
create_test_result("https://example.com/2", "Completely Different Topic", None),
];
let deduplicated = dedup.deduplicate(results);
assert_eq!(
deduplicated.len(),
1,
"hamming distance path should detect similarity"
);
}
#[test]
fn test_url_and_title_strategy_does_not_use_fingerprint() {
let mut dedup = ResultDeduplicator::with_default_config();
dedup.config.strategy = DeduplicationStrategy::UrlAndTitle;
dedup.config.fingerprint_config.simhash_threshold = 64;
let results = vec![
create_test_result("https://example.com/1", "Rust Guide", None),
create_test_result("https://example.com/2", "Python Tutorial", None),
];
let deduplicated = dedup.deduplicate(results);
assert_eq!(
deduplicated.len(),
2,
"UrlAndTitle should NOT use hamming distance (only exact URL/title match)"
);
}
#[test]
fn test_normalize_url_strips_trailing_slash() {
let dedup = ResultDeduplicator::with_default_config();
assert_eq!(
dedup.normalize_url("https://example.com/path/"),
"https://example.com/path"
);
}
#[test]
fn test_deduplicate_same_url_different_schemes_kept_separate() {
let mut dedup = ResultDeduplicator::with_default_config();
dedup.config.strategy = DeduplicationStrategy::UrlOnly;
let results = vec![
create_test_result("http://example.com/page", "Title HTTP", None),
create_test_result("https://example.com/page", "Title HTTPS", None),
];
let deduplicated = dedup.deduplicate(results);
assert_eq!(deduplicated.len(), 2);
}
#[test]
fn test_deduplicate_www_vs_non_www_kept_separate() {
let mut dedup = ResultDeduplicator::with_default_config();
dedup.config.strategy = DeduplicationStrategy::UrlOnly;
let results = vec![
create_test_result("https://www.example.com/page", "Title WWW", None),
create_test_result("https://example.com/page", "Title No WWW", None),
];
let deduplicated = dedup.deduplicate(results);
assert_eq!(deduplicated.len(), 2);
}
#[test]
fn test_deduplicate_tracking_params_removed() {
let mut dedup = ResultDeduplicator::with_default_config();
dedup.config.strategy = DeduplicationStrategy::UrlOnly;
let results = vec![
create_test_result(
"https://example.com/page?utm_source=google",
"Title 1",
None,
),
create_test_result("https://example.com/page?utm_source=bing", "Title 2", None),
];
let deduplicated = dedup.deduplicate(results);
assert_eq!(deduplicated.len(), 1);
}
#[test]
fn test_deduplicate_fragment_differences_removed() {
let mut dedup = ResultDeduplicator::with_default_config();
dedup.config.strategy = DeduplicationStrategy::UrlOnly;
let results = vec![
create_test_result("https://example.com/page#section1", "Title 1", None),
create_test_result("https://example.com/page#section2", "Title 2", None),
];
let deduplicated = dedup.deduplicate(results);
assert_eq!(deduplicated.len(), 1);
}
#[test]
fn test_deduplicate_case_insensitive_url() {
let mut dedup = ResultDeduplicator::with_default_config();
dedup.config.strategy = DeduplicationStrategy::UrlOnly;
let results = vec![
create_test_result("https://EXAMPLE.com/Page", "Title Upper", None),
create_test_result("https://example.com/page", "Title Lower", None),
];
let deduplicated = dedup.deduplicate(results);
assert_eq!(
deduplicated.len(),
1,
"URLs should match case-insensitively"
);
}
#[test]
fn test_baidu_link_urls_not_collapsed_by_query_strip() {
let mut d = ResultDeduplicator::with_default_config();
let merged = vec![
SearchResult {
title: "Result A".to_string(),
url: "https://www.baidu.com/link?url=aaa111".to_string(),
description: None,
engine: "baidu".to_string(),
score: 0.9,
published_time: None,
},
SearchResult {
title: "Result B".to_string(),
url: "https://www.baidu.com/link?url=bbb222".to_string(),
description: None,
engine: "baidu".to_string(),
score: 0.8,
published_time: None,
},
];
let out = d.deduplicate(merged);
assert_eq!(
out.len(),
2,
"distinct baidu /link redirect URLs must not collapse into one"
);
}
}