Skip to main content

fetchium_core/query/
fingerprint.rs

1//! Query Fingerprinting and Deduplication (QFD) — canonical query normalization.
2//!
3//! Novel algorithm: Normalize and fingerprint queries so semantically identical
4//! queries produce the same cache key. Examples:
5//! - "rust vs go" ≡ "go vs rust" ≡ "comparing rust and go"
6//! - "what is machine learning" ≡ "machine learning" (stop-word removal)
7//! - "JavaScript" ≡ "javascript" (case normalization)
8//!
9//! Uses canonical ordering of comparison terms, stop-word removal, stemming
10//! approximation, and SimHash for near-duplicate detection.
11
12/// Stop words removed during fingerprinting.
13const STOP_WORDS: &[&str] = &[
14    "a", "an", "the", "is", "are", "was", "were", "be", "been", "being", "what", "which", "who",
15    "whom", "this", "that", "these", "those", "am", "do", "does", "did", "will", "would", "shall",
16    "should", "can", "could", "may", "might", "must", "need", "dare", "i", "me", "my", "we", "our",
17    "you", "your", "he", "she", "it", "they", "them", "their", "its", "has", "have", "had",
18    "having", "in", "on", "at", "to", "for", "of", "with", "by", "from", "about", "into",
19    "through", "during", "before", "after", "how", "why", "when", "where",
20];
21
22/// Comparison operators that signal a "versus" query.
23const VS_OPERATORS: &[&str] = &[
24    "vs",
25    "vs.",
26    "versus",
27    "compared",
28    "comparison",
29    "comparing",
30    "against",
31    "differ",
32    "difference",
33    "differences",
34    "between",
35    "better",
36    "worse",
37    "or",
38];
39
40/// A fingerprinted query with its canonical form and hash.
41#[derive(Debug, Clone, PartialEq, Eq, Hash)]
42pub struct QueryFingerprint {
43    /// Canonical normalized form of the query.
44    pub canonical: String,
45    /// SimHash fingerprint (64-bit).
46    pub simhash: u64,
47    /// Whether this is a comparison query.
48    pub is_comparison: bool,
49    /// The extracted comparison entities (if comparison query).
50    pub entities: Vec<String>,
51}
52
53/// Fingerprint a query into its canonical form.
54///
55/// The normalization pipeline:
56/// 1. Lowercase
57/// 2. Remove punctuation (except hyphens in compound words)
58/// 3. Remove stop words
59/// 4. Detect comparison pattern → sort entities alphabetically
60/// 5. Apply lightweight stemming (trailing -s, -ing, -ed removal)
61/// 6. Sort remaining terms for order-independence
62/// 7. Compute SimHash over the final token set
63pub fn fingerprint(query: &str) -> QueryFingerprint {
64    let lower = query.to_lowercase();
65
66    // Tokenize: split on whitespace and punctuation (keep hyphens in words)
67    let tokens: Vec<String> = lower
68        .split(|c: char| c.is_whitespace() || (c.is_ascii_punctuation() && c != '-'))
69        .filter(|t| !t.is_empty())
70        .map(|t| t.trim_matches('-').to_string())
71        .filter(|t| !t.is_empty())
72        .collect();
73
74    // Detect comparison pattern
75    let has_vs = tokens.iter().any(|t| VS_OPERATORS.contains(&t.as_str()));
76    let (is_comparison, entities) = if has_vs {
77        extract_comparison_entities(&tokens)
78    } else {
79        (false, Vec::new())
80    };
81
82    // Remove stop words and comparison operators
83    let meaningful: Vec<String> = tokens
84        .iter()
85        .filter(|t| !STOP_WORDS.contains(&t.as_str()))
86        .filter(|t| !VS_OPERATORS.contains(&t.as_str()))
87        .map(|t| lightweight_stem(t))
88        .collect();
89
90    // Build canonical form
91    let canonical = if is_comparison && entities.len() >= 2 {
92        // For comparison queries, sort entities alphabetically
93        let mut sorted_entities = entities.clone();
94        sorted_entities.sort();
95        format!("{} vs", sorted_entities.join(" "))
96    } else {
97        // For regular queries, sort all terms
98        let mut sorted: Vec<String> = meaningful.clone();
99        sorted.sort();
100        sorted.dedup();
101        sorted.join(" ")
102    };
103
104    let simhash = compute_simhash(&meaningful);
105
106    QueryFingerprint {
107        canonical,
108        simhash,
109        is_comparison,
110        entities,
111    }
112}
113
114/// Check if two queries are near-duplicates based on SimHash distance.
115///
116/// Returns true if the Hamming distance between fingerprints is <= threshold.
117/// Default threshold of 8 catches ~87% similar queries.
118pub fn is_near_duplicate(a: &QueryFingerprint, b: &QueryFingerprint, threshold: u32) -> bool {
119    if a.canonical == b.canonical {
120        return true;
121    }
122    hamming_distance(a.simhash, b.simhash) <= threshold
123}
124
125/// Compute Hamming distance between two 64-bit hashes.
126fn hamming_distance(a: u64, b: u64) -> u32 {
127    (a ^ b).count_ones()
128}
129
130/// Extract comparison entities from tokens containing a VS operator.
131///
132/// Handles patterns like:
133/// - "rust vs go" → entities: ["go", "rust"]
134/// - "comparing rust and go" → entities: ["go", "rust"]
135/// - "rust compared to go" → entities: ["go", "rust"]
136fn extract_comparison_entities(tokens: &[String]) -> (bool, Vec<String>) {
137    // Find the position of the comparison operator
138    let vs_pos = tokens
139        .iter()
140        .position(|t| VS_OPERATORS.contains(&t.as_str()));
141
142    match vs_pos {
143        Some(pos) => {
144            let left: Vec<String> = tokens[..pos]
145                .iter()
146                .filter(|t| !STOP_WORDS.contains(&t.as_str()))
147                .filter(|t| !VS_OPERATORS.contains(&t.as_str()))
148                .map(|t| lightweight_stem(t))
149                .collect();
150
151            let right: Vec<String> = tokens[pos + 1..]
152                .iter()
153                .filter(|t| !STOP_WORDS.contains(&t.as_str()))
154                .filter(|t| !VS_OPERATORS.contains(&t.as_str()))
155                .map(|t| lightweight_stem(t))
156                .collect();
157
158            // For "comparing X and Y" patterns: operator is first token,
159            // split the raw tokens (before stop-word removal) on "and"
160            if left.is_empty() {
161                let raw_right = &tokens[pos + 1..];
162                let and_pos = raw_right.iter().position(|t| t == "and" || t == "&");
163                if let Some(ap) = and_pos {
164                    let entity_a: String = raw_right[..ap]
165                        .iter()
166                        .filter(|t| !STOP_WORDS.contains(&t.as_str()))
167                        .map(|t| lightweight_stem(t))
168                        .collect::<Vec<_>>()
169                        .join(" ");
170                    let entity_b: String = raw_right[ap + 1..]
171                        .iter()
172                        .filter(|t| !STOP_WORDS.contains(&t.as_str()))
173                        .filter(|t| !VS_OPERATORS.contains(&t.as_str()))
174                        .map(|t| lightweight_stem(t))
175                        .collect::<Vec<_>>()
176                        .join(" ");
177                    if !entity_a.is_empty() && !entity_b.is_empty() {
178                        let mut entities = vec![entity_a, entity_b];
179                        entities.sort();
180                        return (true, entities);
181                    }
182                }
183                // Fallback: if right side has 2+ meaningful tokens, split in half
184                if right.len() >= 2 {
185                    let mid = right.len() / 2;
186                    let entity_a = right[..mid].join(" ");
187                    let entity_b = right[mid..].join(" ");
188                    let mut entities = vec![entity_a, entity_b];
189                    entities.sort();
190                    return (true, entities);
191                }
192                return (false, Vec::new());
193            }
194
195            if left.is_empty() || right.is_empty() {
196                return (false, Vec::new());
197            }
198
199            let left_entity = left.join(" ");
200            let right_entity = right.join(" ");
201
202            let mut entities = vec![left_entity, right_entity];
203            entities.sort();
204            (true, entities)
205        }
206        None => (false, Vec::new()),
207    }
208}
209
210/// Lightweight stemming — strip common English suffixes.
211///
212/// This is intentionally aggressive to maximize cache hits.
213/// Not linguistically perfect, but good enough for query dedup.
214fn lightweight_stem(word: &str) -> String {
215    let w = word.to_lowercase();
216
217    // Don't stem very short words
218    if w.len() <= 3 {
219        return w;
220    }
221
222    // Strip -ing (but keep at least 3 chars)
223    if w.ends_with("ing") && w.len() > 6 {
224        return w[..w.len() - 3].to_string();
225    }
226
227    // Strip -tion/-sion (keep at least 3 chars of stem)
228    if (w.ends_with("tion") || w.ends_with("sion")) && w.len() >= 7 {
229        return w[..w.len() - 4].to_string();
230    }
231
232    // Strip -ed (but not -eed, -ied)
233    if w.ends_with("ed") && !w.ends_with("eed") && !w.ends_with("ied") && w.len() > 4 {
234        return w[..w.len() - 2].to_string();
235    }
236
237    // Strip trailing -s (but not -ss, -us, -is)
238    if w.ends_with('s')
239        && !w.ends_with("ss")
240        && !w.ends_with("us")
241        && !w.ends_with("is")
242        && w.len() > 3
243    {
244        return w[..w.len() - 1].to_string();
245    }
246
247    w
248}
249
250/// Compute a 64-bit SimHash over a set of tokens.
251///
252/// Each token gets a 64-bit FNV-1a hash, then we sum bit weights
253/// across all tokens. Final fingerprint: bit i = 1 if weight[i] > 0.
254fn compute_simhash(tokens: &[String]) -> u64 {
255    if tokens.is_empty() {
256        return 0;
257    }
258
259    let mut weights = [0i32; 64];
260
261    for token in tokens {
262        let hash = fnv1a_64(token);
263        for (i, weight) in weights.iter_mut().enumerate() {
264            if (hash >> i) & 1 == 1 {
265                *weight += 1;
266            } else {
267                *weight -= 1;
268            }
269        }
270    }
271
272    let mut fingerprint: u64 = 0;
273    for (i, &w) in weights.iter().enumerate() {
274        if w > 0 {
275            fingerprint |= 1u64 << i;
276        }
277    }
278    fingerprint
279}
280
281/// FNV-1a hash (64-bit) for a string.
282fn fnv1a_64(s: &str) -> u64 {
283    const FNV_OFFSET: u64 = 0xcbf29ce484222325;
284    const FNV_PRIME: u64 = 0x00000100000001B3;
285
286    let mut hash = FNV_OFFSET;
287    for byte in s.bytes() {
288        hash ^= byte as u64;
289        hash = hash.wrapping_mul(FNV_PRIME);
290    }
291    hash
292}
293
294/// Generate a cache key from a query fingerprint.
295///
296/// Suitable for use as a cache lookup key that's resistant to
297/// query reformulation.
298pub fn cache_key(fp: &QueryFingerprint) -> String {
299    format!("qfp:{}", fp.canonical)
300}
301
302#[cfg(test)]
303mod tests {
304    use super::*;
305
306    #[test]
307    fn rust_vs_go_order_invariant() {
308        let a = fingerprint("rust vs go");
309        let b = fingerprint("go vs rust");
310        assert_eq!(a.canonical, b.canonical);
311        assert!(a.is_comparison);
312        assert!(b.is_comparison);
313    }
314
315    #[test]
316    fn comparing_detected_as_vs() {
317        let a = fingerprint("rust vs go");
318        let b = fingerprint("comparing rust and go");
319        // Both should be detected as comparison queries
320        assert!(a.is_comparison);
321        assert!(b.is_comparison);
322        // Both should have the same sorted entities
323        assert_eq!(a.entities, b.entities);
324    }
325
326    #[test]
327    fn stop_words_removed() {
328        let a = fingerprint("what is machine learning");
329        let b = fingerprint("machine learning");
330        assert_eq!(a.canonical, b.canonical);
331    }
332
333    #[test]
334    fn case_insensitive() {
335        let a = fingerprint("JavaScript Frameworks");
336        let b = fingerprint("javascript frameworks");
337        assert_eq!(a.canonical, b.canonical);
338    }
339
340    #[test]
341    fn near_duplicate_detection() {
342        let a = fingerprint("best rust web frameworks 2024");
343        let b = fingerprint("top rust web framework 2024");
344        // These share most terms after stemming — distance should be moderate
345        let distance = hamming_distance(a.simhash, b.simhash);
346        assert!(
347            is_near_duplicate(&a, &b, 16),
348            "Expected near-duplicate: a={}, b={}, distance={}",
349            a.canonical,
350            b.canonical,
351            distance,
352        );
353    }
354
355    #[test]
356    fn different_queries_not_duplicates() {
357        let a = fingerprint("rust programming language");
358        let b = fingerprint("cooking italian pasta recipes");
359        assert!(
360            !is_near_duplicate(&a, &b, 5),
361            "Unrelated queries should not be duplicates"
362        );
363    }
364
365    #[test]
366    fn lightweight_stem_strips_suffixes() {
367        assert_eq!(lightweight_stem("programming"), "programm");
368        assert_eq!(lightweight_stem("languages"), "language");
369        assert_eq!(lightweight_stem("compared"), "compar");
370        assert_eq!(lightweight_stem("education"), "educa"); // 9 chars, strips -tion
371        assert_eq!(lightweight_stem("action"), "action"); // too short to stem safely
372    }
373
374    #[test]
375    fn lightweight_stem_preserves_short_words() {
376        assert_eq!(lightweight_stem("go"), "go");
377        assert_eq!(lightweight_stem("is"), "is");
378        assert_eq!(lightweight_stem("the"), "the");
379    }
380
381    #[test]
382    fn cache_key_deterministic() {
383        let a = cache_key(&fingerprint("rust vs go"));
384        let b = cache_key(&fingerprint("go vs rust"));
385        assert_eq!(a, b, "Same query should produce same cache key");
386    }
387
388    #[test]
389    fn empty_query() {
390        let fp = fingerprint("");
391        assert_eq!(fp.canonical, "");
392        assert!(!fp.is_comparison);
393    }
394
395    #[test]
396    fn simhash_deterministic() {
397        let a = fingerprint("rust programming");
398        let b = fingerprint("rust programming");
399        assert_eq!(a.simhash, b.simhash);
400    }
401}