use std::collections::{HashMap, HashSet};
const N_PERM: usize = 64;
const BANDS: usize = 16;
const ROWS_PER_BAND: usize = 4;
fn fnv1a(s: &str) -> u64 {
let mut h: u64 = 0xcbf29ce484222325;
for byte in s.as_bytes() {
h ^= *byte as u64;
h = h.wrapping_mul(0x100000001b3);
}
h
}
fn shingles(key: &str, k: usize) -> Vec<u64> {
let chars: Vec<char> = key.chars().collect();
let mut out = Vec::new();
if chars.is_empty() || chars.len() < k {
if chars.is_empty() {
return out;
}
out.push(fnv1a(key));
return out;
}
for i in 0..=(chars.len() - k) {
let shingle: String = chars[i..i + k].iter().collect();
out.push(fnv1a(&shingle));
}
out.sort_unstable();
out.dedup();
out
}
fn signature(shingle_hashes: &[u64]) -> Option<[u64; N_PERM]> {
if shingle_hashes.is_empty() {
return None;
}
let mut sig = [u64::MAX; N_PERM];
for (i, slot) in sig.iter_mut().enumerate() {
let a = (i as u64).wrapping_mul(0x9E3779B97F4A7C15).wrapping_add(1);
let b = (i as u64).wrapping_mul(0xC2B2AE3D27D4EB4F).wrapping_add(0x165667B19E3779F9);
let mut m = u64::MAX;
for &x in shingle_hashes {
let h = a.wrapping_mul(x) ^ b;
if h < m { m = h; }
}
*slot = m;
}
Some(sig)
}
fn jaccard_est(a: &[u64; N_PERM], b: &[u64; N_PERM]) -> f64 {
let eq = a.iter().zip(b.iter()).filter(|(x, y)| x == y).count();
eq as f64 / N_PERM as f64
}
pub(crate) struct UnionFind {
parent: Vec<usize>,
}
impl UnionFind {
pub(crate) fn new(n: usize) -> Self {
UnionFind { parent: (0..n).collect() }
}
pub(crate) fn find(&mut self, x: usize) -> usize {
let mut root = x;
while self.parent[root] != root {
root = self.parent[root];
}
let mut cur = x;
while self.parent[cur] != cur {
let next = self.parent[cur];
self.parent[cur] = root;
cur = next;
}
root
}
pub(crate) fn union(&mut self, a: usize, b: usize) {
let (ra, rb) = (self.find(a), self.find(b));
if ra != rb {
self.parent[ra.max(rb)] = ra.min(rb); }
}
}
pub fn near_dup_drop_indices(keys: &[String], threshold: f64, shingle_size: usize) -> HashSet<usize> {
let n = keys.len();
let k = shingle_size.max(1);
let sigs: Vec<Option<[u64; N_PERM]>> = keys.iter().map(|key| signature(&shingles(key, k))).collect();
let mut buckets: HashMap<(usize, [u64; ROWS_PER_BAND]), Vec<usize>> = HashMap::new();
for (idx, sig) in sigs.iter().enumerate() {
let Some(sig) = sig else { continue }; for band in 0..BANDS {
let mut bkey = [0u64; ROWS_PER_BAND];
bkey.copy_from_slice(&sig[band * ROWS_PER_BAND..(band + 1) * ROWS_PER_BAND]);
buckets.entry((band, bkey)).or_default().push(idx);
}
}
let mut uf = UnionFind::new(n);
for members in buckets.values() {
if members.len() < 2 { continue; }
for a in 0..members.len() {
for b in (a + 1)..members.len() {
let (i, j) = (members[a], members[b]);
if uf.find(i) == uf.find(j) { continue; }
let (Some(si), Some(sj)) = (&sigs[i], &sigs[j]) else { continue };
if jaccard_est(si, sj) >= threshold {
uf.union(i, j);
}
}
}
}
let mut root_min: HashMap<usize, usize> = HashMap::new();
for (i, sig) in sigs.iter().enumerate().take(n) {
if sig.is_none() { continue; }
let r = uf.find(i);
let e = root_min.entry(r).or_insert(i);
if i < *e { *e = i; }
}
let mut drop = HashSet::new();
for (i, sig) in sigs.iter().enumerate().take(n) {
if sig.is_none() { continue; }
let r = uf.find(i);
if root_min[&r] != i {
drop.insert(i);
}
}
drop
}
pub fn near_match_count(base: &[String], query: &[String], threshold: f64, shingle_size: usize) -> usize {
let k = shingle_size.max(1);
let base_sigs: Vec<Option<[u64; N_PERM]>> = base.iter().map(|s| signature(&shingles(s, k))).collect();
let mut buckets: HashMap<(usize, [u64; ROWS_PER_BAND]), Vec<usize>> = HashMap::new();
for (idx, sig) in base_sigs.iter().enumerate() {
let Some(sig) = sig else { continue };
for band in 0..BANDS {
let mut bkey = [0u64; ROWS_PER_BAND];
bkey.copy_from_slice(&sig[band * ROWS_PER_BAND..(band + 1) * ROWS_PER_BAND]);
buckets.entry((band, bkey)).or_default().push(idx);
}
}
let mut count = 0usize;
for q in query {
let Some(qsig) = signature(&shingles(q, k)) else { continue };
let mut matched = false;
'bands: for band in 0..BANDS {
let mut bkey = [0u64; ROWS_PER_BAND];
bkey.copy_from_slice(&qsig[band * ROWS_PER_BAND..(band + 1) * ROWS_PER_BAND]);
if let Some(cands) = buckets.get(&(band, bkey)) {
for &bi in cands {
if let Some(bsig) = &base_sigs[bi] {
if jaccard_est(&qsig, bsig) >= threshold {
matched = true;
break 'bands;
}
}
}
}
}
if matched { count += 1; }
}
count
}
#[cfg(test)]
mod tests {
use super::*;
fn s(x: &str) -> String { x.to_string() }
#[test]
fn drops_near_identical_keeps_first() {
let a = "the quick brown fox jumps over the lazy dog in the meadow at dawn every single morning";
let b = "the quick brown fox jumps over the lazy dog in the meadow at dusk every single morning";
let c = "the quick brown fox jumps over the lazy dog in the meadow at noon every single morning";
let d = "completely unrelated content about astronomy galaxies nebulae and the expanding universe entirely";
let keys = vec![s(a), s(b), s(c), s(d)];
let drop = near_dup_drop_indices(&keys, 0.6, 5);
assert!(drop.contains(&1) && drop.contains(&2));
assert!(!drop.contains(&0) && !drop.contains(&3));
}
#[test]
fn distinct_answers_drop_nothing() {
let keys = vec![
s("alpha beta gamma delta epsilon zeta eta theta"),
s("one two three four five six seven eight"),
s("red orange yellow green blue indigo violet white"),
];
assert!(near_dup_drop_indices(&keys, 0.85, 5).is_empty());
}
#[test]
fn exact_duplicates_dropped() {
let keys = vec![s("identical answer text here now"), s("identical answer text here now")];
let drop = near_dup_drop_indices(&keys, 0.85, 5);
assert_eq!(drop.len(), 1);
assert!(drop.contains(&1));
}
#[test]
fn empty_keys_never_clustered() {
let keys = vec![s(""), s(""), s("a real distinct sentence with several words present")];
assert!(near_dup_drop_indices(&keys, 0.5, 5).is_empty());
}
#[test]
fn near_match_count_counts_paraphrase_matches() {
let base = vec![
s("the quick brown fox jumps over the lazy dog in the meadow at dawn each morning"),
s("astronomy galaxies nebulae and the steadily expanding universe across deep cosmic time"),
];
let query = vec![
s("the quick brown fox jumps over the lazy dog in the meadow at dusk each morning"), s("a totally unrelated note about baking sourdough bread with a long cold ferment"), s("astronomy galaxies nebulae and the steadily expanding universe across deep cosmic time"), ];
assert_eq!(near_match_count(&base, &query, 0.6, 5), 2);
}
#[test]
fn near_match_count_disjoint_is_zero() {
let base = vec![s("alpha beta gamma delta epsilon zeta eta theta iota kappa lambda mu")];
let query = vec![s("one two three four five six seven eight nine ten eleven twelve")];
assert_eq!(near_match_count(&base, &query, 0.6, 5), 0);
}
#[test]
fn near_match_count_ignores_empty() {
let base = vec![s("")];
let query = vec![s(""), s("a real distinct sentence with several meaningful words present here")];
assert_eq!(near_match_count(&base, &query, 0.5, 5), 0);
}
#[test]
fn deterministic_across_runs() {
let keys = vec![
s("the quick brown fox jumps over the lazy dog today and yesterday and also tomorrow"),
s("the quick brown fox jumps over the lazy dog today and yesterday and also tonight"),
];
let a = near_dup_drop_indices(&keys, 0.6, 5);
let b = near_dup_drop_indices(&keys, 0.6, 5);
assert_eq!(a, b);
}
}