c2pa_text_binding/
minhash.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2
3//! `com.writerslogic.text-minhash.1` — MinHash-128 over word 5-gram shingles
4//! for excerpt and quotation matching. Estimates Jaccard set overlap; two
5//! texts are treated as the same or overlapping content at Jaccard >= 0.70.
6//! 32 bands x 4 rows of LSH provide sublinear lookup keys. Deterministic and
7//! interoperable with ISO 24138 (ISCC) Text-Code semantics.
8
9use crate::normalize::words;
10
11/// Number of MinHash permutations.
12pub const NUM_PERM: usize = 128;
13/// LSH bands.
14pub const BANDS: usize = 32;
15/// Rows per band (`BANDS * ROWS == NUM_PERM`).
16pub const ROWS: usize = 4;
17/// Word shingle size.
18pub const SHINGLE_K: usize = 5;
19/// Match threshold on estimated Jaccard similarity.
20pub const MATCH_JACCARD: f64 = 0.70;
21
22/// Mersenne prime 2^61 - 1, the modulus for the affine permutation family.
23const MERSENNE_61: u64 = (1 << 61) - 1;
24/// Fixed seed for the permutation family, pinned so all implementations agree.
25const PERM_SEED: u64 = 0x0123_4567_89AB_CDEF;
26
27/// A MinHash signature plus its LSH band hashes.
28#[derive(Clone, Debug, PartialEq, Eq)]
29pub struct MinHash {
30    pub sig: [u64; NUM_PERM],
31    pub bands: [u64; BANDS],
32    pub shingle_count: usize,
33}
34
35/// SplitMix64 step — used only to derive the fixed permutation parameters.
36fn splitmix64(state: &mut u64) -> u64 {
37    *state = state.wrapping_add(0x9E37_79B9_7F4A_7C15);
38    let mut z = *state;
39    z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
40    z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
41    z ^ (z >> 31)
42}
43
44/// The pinned `(a, b)` affine permutation parameters: h -> (a*h + b) mod p.
45fn permutation_params() -> ([u64; NUM_PERM], [u64; NUM_PERM]) {
46    let mut state = PERM_SEED;
47    let mut a = [0u64; NUM_PERM];
48    let mut b = [0u64; NUM_PERM];
49    for i in 0..NUM_PERM {
50        // a in [1, p-1] so the permutation is a bijection; b in [0, p-1].
51        a[i] = (splitmix64(&mut state) % (MERSENNE_61 - 1)) + 1;
52        b[i] = splitmix64(&mut state) % MERSENNE_61;
53    }
54    (a, b)
55}
56
57/// FNV-1a 64-bit base hash of a shingle, reduced into the Mersenne field.
58fn base_hash(shingle: &str) -> u64 {
59    const OFFSET: u64 = 0xcbf2_9ce4_8422_2325;
60    const PRIME: u64 = 0x0000_0100_0000_01b3;
61    let mut h = OFFSET;
62    for &byte in shingle.as_bytes() {
63        h ^= byte as u64;
64        h = h.wrapping_mul(PRIME);
65    }
66    h % MERSENNE_61
67}
68
69/// FNV-1a 64-bit over the little-endian bytes of a band's rows.
70fn band_hash(rows: &[u64]) -> u64 {
71    const OFFSET: u64 = 0xcbf2_9ce4_8422_2325;
72    const PRIME: u64 = 0x0000_0100_0000_01b3;
73    let mut h = OFFSET;
74    for &v in rows {
75        for byte in v.to_le_bytes() {
76            h ^= byte as u64;
77            h = h.wrapping_mul(PRIME);
78        }
79    }
80    h
81}
82
83impl MinHash {
84    /// Compute the MinHash signature of `text`.
85    pub fn compute(text: &str) -> Self {
86        let toks = words(text);
87        let shingles = shingles(&toks);
88        let (a, b) = permutation_params();
89        let mut sig = [u64::MAX; NUM_PERM];
90        for s in &shingles {
91            let h = base_hash(s);
92            for i in 0..NUM_PERM {
93                let v = mul_mod(a[i], h).wrapping_add(b[i]) % MERSENNE_61;
94                if v < sig[i] {
95                    sig[i] = v;
96                }
97            }
98        }
99        // Empty input -> all-zero signature (deterministic, never matches real content).
100        if shingles.is_empty() {
101            sig = [0u64; NUM_PERM];
102        }
103        let mut bands = [0u64; BANDS];
104        for (band, slot) in bands.iter_mut().enumerate() {
105            let start = band * ROWS;
106            *slot = band_hash(&sig[start..start + ROWS]);
107        }
108        MinHash {
109            sig,
110            bands,
111            shingle_count: shingles.len(),
112        }
113    }
114
115    /// Rehydrate a `MinHash` from a stored 128-value signature, recomputing the
116    /// LSH bands. `shingle_count` is unknown from the signature alone and is set
117    /// to zero; it does not affect [`jaccard`](Self::jaccard) or
118    /// [`shares_band`](Self::shares_band).
119    pub fn from_signature(sig: [u64; NUM_PERM]) -> Self {
120        let mut bands = [0u64; BANDS];
121        for (band, slot) in bands.iter_mut().enumerate() {
122            let start = band * ROWS;
123            *slot = band_hash(&sig[start..start + ROWS]);
124        }
125        MinHash {
126            sig,
127            bands,
128            shingle_count: 0,
129        }
130    }
131
132    /// Estimated Jaccard similarity: the fraction of equal signature positions.
133    pub fn jaccard(&self, other: &Self) -> f64 {
134        let equal = self
135            .sig
136            .iter()
137            .zip(other.sig.iter())
138            .filter(|(x, y)| x == y)
139            .count();
140        equal as f64 / NUM_PERM as f64
141    }
142
143    /// Whether the two texts share at least one LSH band (candidate for match).
144    pub fn shares_band(&self, other: &Self) -> bool {
145        self.bands.iter().any(|x| other.bands.contains(x))
146    }
147
148    /// Whether the two texts are the same or overlapping content
149    /// (estimated Jaccard >= [`MATCH_JACCARD`]).
150    pub fn matches(&self, other: &Self) -> bool {
151        self.jaccard(other) >= MATCH_JACCARD
152    }
153}
154
155/// Word 5-gram shingles. Texts shorter than `SHINGLE_K` words yield a single
156/// shingle over all their words so short quotations still produce a signature.
157fn shingles(toks: &[String]) -> Vec<String> {
158    if toks.is_empty() {
159        return Vec::new();
160    }
161    if toks.len() < SHINGLE_K {
162        return vec![toks.join(" ")];
163    }
164    toks.windows(SHINGLE_K).map(|w| w.join(" ")).collect()
165}
166
167/// 64-bit modular multiply mod 2^61-1 without overflow, via 128-bit widening.
168fn mul_mod(x: u64, y: u64) -> u64 {
169    ((x as u128 * y as u128) % MERSENNE_61 as u128) as u64
170}
171
172#[cfg(test)]
173mod tests {
174    use super::*;
175
176    const SRC: &str = "the honest limit is that text which is both heavily paraphrased and \
177        retyped defeats every layer except an approximate semantic match while everything \
178        short of that degrades gracefully across the fingerprint family of algorithms";
179
180    #[test]
181    fn identical_text_jaccard_one() {
182        let a = MinHash::compute(SRC);
183        let b = MinHash::compute(SRC);
184        assert_eq!(a.jaccard(&b), 1.0);
185        assert_eq!(a, b);
186    }
187
188    #[test]
189    fn near_duplicate_shares_band() {
190        // Whole-document MinHash resolves near-duplicates and large overlaps;
191        // small-excerpt matching is the job of per-segment signatures. A
192        // one-word edit keeps Jaccard well above the 0.70 threshold, so an LSH
193        // band must collide.
194        let a = MinHash::compute(SRC);
195        let b = MinHash::compute(&SRC.replacen("gracefully", "smoothly", 1));
196        assert!(
197            a.matches(&b),
198            "near-duplicate must match at Jaccard >= 0.70"
199        );
200        assert!(
201            a.shares_band(&b),
202            "near-duplicates should share an LSH band"
203        );
204    }
205
206    #[test]
207    fn reordering_and_deletion_stay_high() {
208        let a = MinHash::compute(SRC);
209        // Delete a clause and reformat; most 5-gram shingles survive.
210        let edited = SRC.replace("heavily paraphrased and ", "");
211        let b = MinHash::compute(&edited);
212        assert!(
213            a.jaccard(&b) > 0.5,
214            "minor deletion should keep Jaccard high"
215        );
216    }
217
218    #[test]
219    fn unrelated_text_low_jaccard() {
220        let a = MinHash::compute(SRC);
221        let b = MinHash::compute(
222            "a recipe for shortbread needs only butter sugar and flour combined by hand \
223             then chilled and baked until the edges are barely golden at the rim",
224        );
225        assert!(a.jaccard(&b) < MATCH_JACCARD);
226        assert!(!a.matches(&b));
227    }
228
229    #[test]
230    fn casefold_and_zero_width_ignored() {
231        let a = MinHash::compute(SRC);
232        let b = MinHash::compute(&SRC.to_uppercase().replace(' ', "\u{200B} "));
233        assert_eq!(a, b);
234    }
235
236    #[test]
237    fn bands_derived_from_signature() {
238        let a = MinHash::compute(SRC);
239        assert_eq!(a.bands.len(), BANDS);
240        assert_eq!(BANDS * ROWS, NUM_PERM);
241    }
242
243    // Pinned test vector: first four signature values for a fixed input.
244    #[test]
245    fn vector_signature_prefix() {
246        let mh = MinHash::compute("the quick brown fox jumps over the lazy dog again");
247        assert_eq!(
248            &mh.sig[..4],
249            &[
250                111552349047830145,
251                188277353147072251,
252                213821157973154889,
253                100998052165424870
254            ],
255            "PIN: recompute and update on any intentional algorithm change"
256        );
257    }
258}
c2pa_text_binding/minhash.rs

c2pa_text_binding/
minhash.rs
