datasketch_minhash_lsh/
minhash.rs

1use crate::create_rng;
2use crate::error::MinHashingError;
3use itertools::Itertools;
4use rand::distributions::Uniform;
5use rand::Rng;
6use std::cmp::min;
7use std::collections::hash_map::DefaultHasher;
8use std::hash::{Hash, Hasher};
9
10const _MERSENNE_PRIME: u64 = (1 << 61) - 1;
11const _MAX_HASH: u64 = (1 << 32) - 1;
12
13type Result<T> = std::result::Result<T, MinHashingError>;
14
15/// A min-hash value generated by MinHash
16#[derive(Clone, Debug)]
17pub struct HashValues(pub Vec<u64>);
18
19/// The MinHash struct
20#[derive(Clone)]
21pub struct MinHash {
22    seed: Option<u64>,
23    num_perm: usize,
24    /// The HashValues corresponding to the set as it currently is
25    pub hash_values: HashValues,
26    permutations: Vec<(u64, u64)>,
27}
28
29impl MinHash {
30    /// Build a new MinHash struct
31    pub fn new(num_perm: usize, seed: Option<u64>) -> MinHash {
32        let hash_values = Self::init_hash_values(num_perm);
33        let permutations = Self::init_permutations(num_perm, seed);
34        MinHash {
35            seed,
36            num_perm,
37            hash_values,
38            permutations,
39        }
40    }
41
42    fn init_hash_values(num_perm: usize) -> HashValues {
43        let vec = vec![_MAX_HASH; num_perm];
44        HashValues(vec)
45    }
46
47    fn init_permutations(num_perm: usize, seed: Option<u64>) -> Vec<(u64, u64)> {
48        let rng = create_rng(seed);
49        let distribution = Uniform::new(0, _MAX_HASH);
50        rng.sample_iter(distribution)
51            .take(num_perm * 2)
52            .tuples()
53            .collect_vec()
54    }
55
56    /// Add a new value to the set
57    pub fn update<T: Hash>(&mut self, value_to_be_hashed: &T) {
58        let mut hasher = DefaultHasher::new();
59        value_to_be_hashed.hash(&mut hasher);
60        let hash_value = hasher.finish() as u32 as u64;
61        // TODO: Is there a better way to get u32 hashes?
62        let hash_value_permutations = self
63            .permutations
64            .iter()
65            .map(|(a, b)| (((a * hash_value) + b) % _MERSENNE_PRIME) & _MAX_HASH);
66        // np.min
67        self.hash_values
68            .0
69            .iter_mut()
70            .zip_eq(hash_value_permutations)
71            .for_each(|(old, new)| *old = min(*old, new));
72    }
73
74    /// Compute the jaccard distance between to MinHash sets that use the same seed and number of
75    /// permutation functions
76    pub fn jaccard(&mut self, other_minhash: &MinHash) -> Result<f32> {
77        if other_minhash.seed != self.seed {
78            return Err(MinHashingError::DifferentSeeds);
79        }
80        if other_minhash.num_perm != self.num_perm {
81            return Err(MinHashingError::DifferentNumPermFuncs);
82        }
83        let matches = self
84            .hash_values
85            .0
86            .iter_mut()
87            .zip_eq(&other_minhash.hash_values.0)
88            .filter(|(left, right)| left == right)
89            .count();
90        let result = matches as f32 / self.num_perm as f32;
91        Ok(result)
92    }
93
94    pub fn update_batch<T: Hash>(&mut self, _value_to_be_hashed: &[T]) {
95        unimplemented!("Can be added if we need it");
96    }
97}
98
99#[cfg(test)]
100mod test {
101    use super::*;
102
103    #[test]
104    fn test_init_() {
105        let m1 = <MinHash>::new(4, Some(0));
106        let m2 = <MinHash>::new(4, Some(0));
107        assert_eq!(m1.hash_values.0, m2.hash_values.0);
108        assert_eq!(m1.permutations, m2.permutations);
109    }
110
111    #[test]
112    fn test_update() {
113        let mut m1 = <MinHash>::new(4, Some(1));
114        let m2 = <MinHash>::new(4, Some(1));
115        m1.update(&12);
116        for i in 0..4 {
117            assert!(m1.hash_values.0[i] < m2.hash_values.0[i]);
118        }
119    }
120
121    #[test]
122    fn test_jaccard() -> Result<()> {
123        let mut m1 = <MinHash>::new(4, Some(1));
124        let mut m2 = <MinHash>::new(4, Some(1));
125        assert_eq!(m1.jaccard(&m2)?, 1.0);
126        m2.update(&12);
127        assert_eq!(m1.jaccard(&m2)?, 0.0);
128        m1.update(&13);
129        assert!(m1.jaccard(&m2)? < 1.0);
130        m1.update(&12);
131        let distance = m1.jaccard(&m2)?;
132        assert!(distance < 1.0 && distance > 0.0);
133        Ok(())
134    }
135
136    #[test]
137    fn test_data_sketch_minhash() {
138        // A test similar to the one in lsh_rs_minhash
139        let n_projections = 3;
140        let mut m = <MinHash>::new(n_projections, Some(0));
141        m.update(&0);
142        m.update(&2);
143        m.update(&4);
144        assert_eq!(m.hash_values.0.len(), n_projections);
145        println!("{:?}", &m.hash_values);
146    }
147}
datasketch_minhash_lsh/minhash.rs

datasketch_minhash_lsh/
minhash.rs
