simi/algo/
simhash.rs

1//! SimHash — locality-sensitive hash for deduplication of large documents.
2//!
3//! Generates a 64-bit fingerprint where similar documents have similar
4//! fingerprints. Similarity is measured by the Hamming distance between
5//! fingerprints.
6//!
7//! ## Performance
8//! O(n) time where n = number of features. O(1) memory (single u64).
9
10/// A 64-bit SimHash fingerprint.
11#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
12pub struct SimHashFingerprint(pub u64);
13
14const DEFAULT_SHINGLE_SIZE: usize = 4;
15
16/// Generate a SimHash fingerprint for a text.
17///
18/// Uses character-level 4-grams (tetragrams) as features by default.
19/// Each feature is hashed, and the bits are accumulated weighted by
20/// feature frequency.
21#[inline]
22pub fn fingerprint(text: &str, shingle_size: usize) -> SimHashFingerprint {
23    let chars: Vec<char> = text.chars().collect();
24    let mut shingles = Vec::new();
25
26    if chars.len() < shingle_size {
27        shingles.push(text.to_string());
28    } else {
29        // Collect shingles with their frequencies
30        for w in chars.windows(shingle_size) {
31            shingles.push(w.iter().collect::<String>());
32        }
33    }
34
35    // SimHash: accumulate +1/-1 for each bit position
36    let mut v = [0i64; 64];
37
38    for shingle in &shingles {
39        let h = fxhash64(shingle);
40        for (i, val) in v.iter_mut().enumerate() {
41            if (h >> i) & 1 == 1 {
42                *val += 1;
43            } else {
44                *val -= 1;
45            }
46        }
47    }
48
49    // Compress to 64-bit fingerprint
50    let mut fp: u64 = 0;
51    for (i, val) in v.iter().enumerate() {
52        if *val > 0 {
53            fp |= 1 << i;
54        }
55    }
56
57    SimHashFingerprint(fp)
58}
59
60/// Default fingerprint with tetragram shingles.
61#[inline]
62pub fn fingerprint_default(text: &str) -> SimHashFingerprint {
63    fingerprint(text, DEFAULT_SHINGLE_SIZE)
64}
65
66/// Hamming distance between two SimHash fingerprints.
67///
68/// Returns the number of differing bits.
69#[inline]
70pub fn hamming_distance(a: SimHashFingerprint, b: SimHashFingerprint) -> u32 {
71    (a.0 ^ b.0).count_ones()
72}
73
74/// Normalized similarity from two SimHash fingerprints.
75///
76/// Returns `1.0 - (hamming_distance / 64)` in `[0.0, 1.0]`.
77#[inline]
78pub fn similarity(a: SimHashFingerprint, b: SimHashFingerprint) -> f64 {
79    1.0 - hamming_distance(a, b) as f64 / 64.0
80}
81
82/// One-shot: hash both strings and compare.
83#[inline]
84pub fn compare(a: &str, b: &str, shingle_size: usize) -> f64 {
85    let fp_a = fingerprint(a, shingle_size);
86    let fp_b = fingerprint(b, shingle_size);
87    similarity(fp_a, fp_b)
88}
89
90/// Default one-shot with tetragram shingles.
91#[inline]
92pub fn compare_default(a: &str, b: &str) -> f64 {
93    compare(a, b, DEFAULT_SHINGLE_SIZE)
94}
95
96// FNV-1a 64-bit hash
97fn fxhash64(s: &str) -> u64 {
98    let mut hash: u64 = 0xcbf29ce484222325;
99    for b in s.bytes() {
100        hash ^= b as u64;
101        hash = hash.wrapping_mul(0x100000001b3);
102    }
103    hash
104}
105
106#[cfg(test)]
107mod tests {
108    use super::*;
109
110    #[test]
111    fn identical_documents() {
112        let s = compare_default("hello world this is a test", "hello world this is a test");
113        assert!(
114            (s - 1.0).abs() < f64::EPSILON,
115            "identical should be 1.0, got {s}"
116        );
117    }
118
119    #[test]
120    fn similar_documents() {
121        let s = compare_default(
122            "the quick brown fox jumps over the lazy dog",
123            "the quick brown fox jumps over the lazy cat",
124        );
125        assert!(s > 0.75, "expected high similarity, got {s}");
126    }
127
128    #[test]
129    fn different_documents() {
130        let fp_a = fingerprint_default("completely unrelated content one");
131        let fp_b = fingerprint_default("totally different text here two");
132        let d = hamming_distance(fp_a, fp_b);
133        assert!(d > 20, "expected at least 20 bits different, got {d}");
134    }
135
136    #[test]
137    fn symmetric() {
138        let a = compare_default("abc def", "abc xyz");
139        let b = compare_default("abc xyz", "abc def");
140        assert!((a - b).abs() < f64::EPSILON);
141    }
142
143    #[test]
144    fn small_text() {
145        let fp = fingerprint("hi", 4);
146        // Single shingle < 4 chars just uses the whole text
147        assert_ne!(fp.0, 0);
148    }
149}
simi/algo/simhash.rs

simi/algo/
simhash.rs
