web_simhash/
fingerprint.rs

1use crate::web::WebFeatureExtractor;
2
3/// The Google paper's empirically reasonable threshold for 64-bit web-page
4/// fingerprints.
5pub const DEFAULT_NEAR_DUP_DISTANCE: u32 = 3;
6
7const FNV_OFFSET_BASIS: u64 = 0xcbf29ce484222325;
8const FNV_PRIME: u64 = 0x00000100000001b3;
9const BYTE_LANE_MASK: u64 = 0x0101_0101_0101_0101;
10
11/// Deterministic 64-bit FNV-1a hash.
12///
13/// The hash is used for reproducible feature hashing. It is not cryptographic.
14pub fn fnv1a64(bytes: &[u8]) -> u64 {
15    let mut hash = FNV_OFFSET_BASIS;
16    for byte in bytes {
17        hash ^= u64::from(*byte);
18        hash = hash.wrapping_mul(FNV_PRIME);
19    }
20    hash
21}
22
23/// Tie behavior when a SimHash accumulator lands exactly on zero.
24#[derive(Debug, Clone, Copy, PartialEq, Eq)]
25pub enum TieBreaker {
26    Zero,
27    One,
28    Alternating,
29}
30
31/// Fingerprint construction options.
32#[derive(Debug, Clone, Copy, PartialEq, Eq)]
33pub struct SimHashOptions {
34    pub tie_breaker: TieBreaker,
35}
36
37impl Default for SimHashOptions {
38    fn default() -> Self {
39        Self {
40            tie_breaker: TieBreaker::Alternating,
41        }
42    }
43}
44
45/// A string feature with an integer weight.
46#[derive(Debug, Clone, PartialEq, Eq)]
47pub struct WeightedFeature {
48    pub key: String,
49    pub weight: u32,
50}
51
52impl WeightedFeature {
53    pub fn new(key: impl Into<String>, weight: u32) -> Self {
54        Self {
55            key: key.into(),
56            weight,
57        }
58    }
59
60    pub fn hash(&self) -> FeatureHash {
61        let mut bytes = Vec::with_capacity("feature:".len() + self.key.len());
62        bytes.extend_from_slice(b"feature:");
63        bytes.extend_from_slice(self.key.as_bytes());
64        FeatureHash {
65            hash: fnv1a64(&bytes),
66            weight: self.weight,
67        }
68    }
69}
70
71/// A pre-hashed feature.
72#[derive(Debug, Clone, Copy, PartialEq, Eq)]
73pub struct FeatureHash {
74    pub hash: u64,
75    pub weight: u32,
76}
77
78impl FeatureHash {
79    pub fn new(hash: u64, weight: u32) -> Self {
80        Self { hash, weight }
81    }
82}
83
84/// A 64-bit SimHash fingerprint.
85#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
86pub struct SimHash64(pub u64);
87
88impl SimHash64 {
89    pub fn from_features(features: &[WeightedFeature]) -> Self {
90        Self::from_features_with_options(features, SimHashOptions::default())
91    }
92
93    pub fn from_features_with_options(
94        features: &[WeightedFeature],
95        options: SimHashOptions,
96    ) -> Self {
97        let hashes = features.iter().map(WeightedFeature::hash);
98        Self::from_feature_hashes_with_options(hashes, options)
99    }
100
101    pub fn from_feature_hashes<I>(hashes: I) -> Self
102    where
103        I: IntoIterator<Item = FeatureHash>,
104    {
105        Self::from_feature_hashes_with_options(hashes, SimHashOptions::default())
106    }
107
108    pub fn from_feature_hashes_with_options<I>(hashes: I, options: SimHashOptions) -> Self
109    where
110        I: IntoIterator<Item = FeatureHash>,
111    {
112        let mut accum = [0i64; 64];
113        for feature in hashes {
114            if feature.weight == 0 {
115                continue;
116            }
117            let weight = i64::from(feature.weight);
118            for bit in 0..64 {
119                if ((feature.hash >> bit) & 1) == 1 {
120                    accum[bit] += weight;
121                } else {
122                    accum[bit] -= weight;
123                }
124            }
125        }
126        Self(bits_from_signed_accumulator(&accum, options))
127    }
128
129    /// Fast unweighted SimHash over pre-hashed elements.
130    ///
131    /// This uses the byte-lane counter trick described by Otmar Ertl's
132    /// FastSimHash article: each byte lane in a `u64` counts one bit position,
133    /// then lanes are flushed before they can overflow. The result is equivalent
134    /// to the normal unweighted SimHash path.
135    pub fn from_hashes_unweighted_fast(hashes: &[u64]) -> Self {
136        Self::from_hashes_unweighted_fast_with_options(hashes, SimHashOptions::default())
137    }
138
139    pub fn from_hashes_unweighted_fast_with_options(
140        hashes: &[u64],
141        options: SimHashOptions,
142    ) -> Self {
143        let mut ones = [0u32; 64];
144        let mut lanes = [0u64; 8];
145        let mut in_lanes = 0u16;
146
147        for hash in hashes {
148            for shift in 0..8 {
149                lanes[shift] = lanes[shift].wrapping_add((hash >> shift) & BYTE_LANE_MASK);
150            }
151            in_lanes += 1;
152            if in_lanes == 255 {
153                flush_lanes(&mut ones, &mut lanes);
154                in_lanes = 0;
155            }
156        }
157
158        if in_lanes > 0 {
159            flush_lanes(&mut ones, &mut lanes);
160        }
161
162        let total = hashes.len() as i64;
163        let mut accum = [0i64; 64];
164        for bit in 0..64 {
165            accum[bit] = i64::from(ones[bit]) * 2 - total;
166        }
167        Self(bits_from_signed_accumulator(&accum, options))
168    }
169
170    pub fn from_text(text: &str, extractor: &WebFeatureExtractor) -> Self {
171        let features = extractor.extract_from_text(text);
172        Self::from_features(&features)
173    }
174
175    pub fn from_html(html: &str, extractor: &WebFeatureExtractor) -> Self {
176        let features = extractor.extract_from_html(html);
177        Self::from_features(&features)
178    }
179
180    pub fn hamming_distance(self, other: Self) -> u32 {
181        (self.0 ^ other.0).count_ones()
182    }
183
184    pub fn similarity(self, other: Self) -> f64 {
185        1.0 - f64::from(self.hamming_distance(other)) / 64.0
186    }
187
188    pub fn is_near_duplicate(self, other: Self, max_distance: u32) -> bool {
189        self.hamming_distance(other) <= max_distance
190    }
191}
192
193fn flush_lanes(ones: &mut [u32; 64], lanes: &mut [u64; 8]) {
194    for shift in 0..8 {
195        let lane = lanes[shift];
196        for byte in 0..8 {
197            let bit = shift + byte * 8;
198            ones[bit] += ((lane >> (byte * 8)) & 0xff) as u32;
199        }
200        lanes[shift] = 0;
201    }
202}
203
204fn bits_from_signed_accumulator(accum: &[i64; 64], options: SimHashOptions) -> u64 {
205    let mut value = 0u64;
206    for (bit, count) in accum.iter().enumerate() {
207        let set = match count.cmp(&0) {
208            std::cmp::Ordering::Greater => true,
209            std::cmp::Ordering::Less => false,
210            std::cmp::Ordering::Equal => match options.tie_breaker {
211                TieBreaker::Zero => false,
212                TieBreaker::One => true,
213                TieBreaker::Alternating => bit % 2 == 1,
214            },
215        };
216        if set {
217            value |= 1u64 << bit;
218        }
219    }
220    value
221}
222
223#[cfg(test)]
224mod tests {
225    use super::*;
226
227    #[test]
228    fn fnv1a_is_deterministic() {
229        assert_eq!(fnv1a64(b"test string"), 10983430520173899754);
230        assert_eq!(fnv1a64(b"test string"), fnv1a64(b"test string"));
231        assert_ne!(fnv1a64(b"test string"), fnv1a64(b"test thing"));
232    }
233
234    #[test]
235    fn weighted_features_change_the_result() {
236        let light = vec![
237            WeightedFeature::new("term:my", 1),
238            WeightedFeature::new("term:car", 1),
239            WeightedFeature::new("term:black", 1),
240        ];
241        let heavy = vec![
242            WeightedFeature::new("term:my", 1),
243            WeightedFeature::new("term:car", 1),
244            WeightedFeature::new("term:black", 8),
245        ];
246
247        assert_ne!(
248            SimHash64::from_features(&light),
249            SimHash64::from_features(&heavy)
250        );
251    }
252
253    #[test]
254    fn explicit_feature_weights_match_repetition() {
255        let repeated_hash = fnv1a64(b"feature:repeated");
256        let weighted = SimHash64::from_feature_hashes([FeatureHash::new(repeated_hash, 3)]);
257        let repeated = SimHash64::from_feature_hashes([
258            FeatureHash::new(repeated_hash, 1),
259            FeatureHash::new(repeated_hash, 1),
260            FeatureHash::new(repeated_hash, 1),
261        ]);
262
263        assert_eq!(weighted, repeated);
264    }
265
266    #[test]
267    fn hamming_distance_and_similarity_work() {
268        let a = SimHash64(0);
269        let b = SimHash64(u64::MAX);
270        let c = SimHash64(0b1011);
271
272        assert_eq!(a.hamming_distance(a), 0);
273        assert_eq!(a.hamming_distance(b), 64);
274        assert_eq!(a.hamming_distance(c), 3);
275        assert_eq!(a.similarity(a), 1.0);
276        assert_eq!(a.similarity(b), 0.0);
277    }
278
279    #[test]
280    fn fast_unweighted_path_matches_standard_path() {
281        let hashes: Vec<u64> = (0..600)
282            .map(|n| fnv1a64(format!("feature-{n}").as_bytes()))
283            .collect();
284        let fast = SimHash64::from_hashes_unweighted_fast(&hashes);
285        let standard =
286            SimHash64::from_feature_hashes(hashes.iter().copied().map(|h| FeatureHash::new(h, 1)));
287
288        assert_eq!(fast, standard);
289    }
290
291    #[test]
292    fn tie_breakers_are_deterministic() {
293        let empty_zero = SimHash64::from_feature_hashes_with_options(
294            [],
295            SimHashOptions {
296                tie_breaker: TieBreaker::Zero,
297            },
298        );
299        let empty_one = SimHash64::from_feature_hashes_with_options(
300            [],
301            SimHashOptions {
302                tie_breaker: TieBreaker::One,
303            },
304        );
305        let empty_alt = SimHash64::from_feature_hashes_with_options(
306            [],
307            SimHashOptions {
308                tie_breaker: TieBreaker::Alternating,
309            },
310        );
311
312        assert_eq!(empty_zero.0, 0);
313        assert_eq!(empty_one.0, u64::MAX);
314        assert_eq!(empty_alt.0, 0xaaaa_aaaa_aaaa_aaaa);
315    }
316}
web_simhash/fingerprint.rs

web_simhash/
fingerprint.rs
