一些与Minhash相关的算法

此crate提供了一些源自原始Minhash的最近算法的实现。它们具有更好的性能和更广泛的适用性。

它实现了

• ProbMinHash2、ProbMinHash3和ProbMinHash3a，如O. Ertl论文《ProbMinHash.一类用于概率Jaccard相似度的局部敏感哈希算法》（2020年）所述：ProbMinHash.一类用于概率Jaccard相似度的局部敏感哈希算法 probminhash Ertl 或 IEEE-2022

这些算法通过敏感哈希计算Jaccard加权指数的估计值。它是将Jaccard指数扩展到对象具有权重或重数的情况。
这种Jaccard加权指数提供了在离散概率分布上的度量，如Moulton Jiang在《Maximally consistent sampling and the Jaccard index of probability distributions》（2018年）中解释的那样：Moulton Jiang. Maximally consistent sampling and the Jaccard index of probability distributions Moulton-Jiang-ieee 或 Moulton-Jiang-arxiv

记Jaccard加权指数为Jp，则1. - Jp定义了一个有限离散概率的度量。
此模块是crate的核心，它还有另外两个模块。

• Superminhash

用于Jaccard相似度估计的新Minwise哈希算法 Otmar Ertl 2017-2018 Cf superminhash Ertl

此算法在无权重对象上运行，可以将数十亿个对象绘制成f32/f64向量。哈希值通过sketch方法计算，或可以在进入SuperMinHash方法之前计算。

它对数据进行一次遍历，因此可以用于流处理。

此算法的变体，Superminhash2，将数据绘制成u32/u64向量，但速度较慢。它可以通过sminhash2功能访问。

• SetSketch

SetSketch: 在MinHash和HyperLogLog之间的差距 Otmar Ertl 2021 arxiv 或 vldb

此算法在无权重对象上运行。它比SuperMinHash慢，但可以将数十亿个对象绘制成16字节整数的向量。此外，草图是可合并的。
我们提供了草图（适应LSH和Jaccard距离）以及草图集的基数估计器。

• 高于一次排列哈希（简称OPH）的稠密化算法。

  • 快速且精确的Minwise哈希的最佳密度化.
    Ashumali Shrivastava 2017 pmlr-2017.

  • 关于MinWise哈希的密度化。
    Mai, Rao, Kapilevitch, Rossi, Abbasi-Yadkori, Sinha. pmlr-2020

• ProbOrdMinHash2是在Ertl的ProbMinHash2基础上实现的针对编辑距离的局部敏感哈希，后者如Ertl的probordminhash2。
  它受到Marcais.G et al. BioInformatics 2019的启发，参见Marcais

• Invhash

它是一个模块，提供从u32到u32或u64到u64的可逆哈希，可用于对索引进行预哈希。（参见invhash.rs中对Thomas Wang的可逆整数哈希函数的引用）

一些示例

一些使用示例（更多在每个模块的测试中）包括估计两个向量内容的交集

• Probminhash

一个带有IndexMap的Prominhash3a的示例
（参见test_probminhash::tests::test_probminhash3a_count_intersection_unequal_weights测试）

    type FnvIndexMap<K, V> = IndexMap<K, V, FnvBuildHasher>;
    ...
    let mut wa : FnvIndexMap::<usize,f64> = FnvIndexMap::with_capacity_and_hasher(70, FnvBuildHasher::default());
    // initialize wa ...

    let mut wb : FnvIndexMap::<usize,f64> = FnvIndexMap::with_capacity_and_hasher(70, FnvBuildHasher::default());
    // initialize ...
    let mut waprobhash = ProbMinHash3a::<usize, FnvHasher>::new(nbhash, 0);
    waprobhash.hash_weigthed_idxmap(&wa);
    //
    let mut wbprobhash = ProbMinHash3a::<usize, FnvHasher>::new(nbhash, 0);
    wbprobhash.hash_weigthed_idxmap(&wb);
    //
    let siga = waprobhash.get_signature();
    let sigb = wbprobhash.get_signature();
    let jp_approx = compute_probminhash_jaccard(siga, sigb);

一个逐个发送项目的Probminhash3的示例

    let set_size = 100;
    let mut wa = Vec::<f64>::with_capacity(set_size);
    let mut wb = Vec::<f64>::with_capacity(set_size);
    // initialize wa, wb
    ....
    // probminhash
    let mut waprobhash = ProbMinHash3::<usize, FnvHasher>::new(nbhash, 0);
    for i in 0..set_size {
        if wa[i] > 0. {
            waprobhash.hash_item(i, wa[i]);
        }
    }
    //
    let mut wbprobhash = ProbMinHash3::<usize, FnvHasher>::new(nbhash, 0);
    for i in 0..set_size {
        if wb[i] > 0. {
            wbprobhash.hash_item(i, wb[i]);
        }
    }
    let siga = waprobhash.get_signature();
    let sigb = wbprobhash.get_signature();
    let jp_approx = compute_probminhash_jaccard(siga, sigb);

• Superminhash

      let va : Vec<usize> = (0..1000).collect();
      let vb : Vec<usize> = (900..2000).collect();
      let bh = BuildHasherDefault::<FnvHasher>::default();
      let mut sminhash : SuperMinHash<usize, FnvHasher>= SuperMinHash::new(70, &bh);
      // now compute sketches
      let resa = sminhash.sketch_slice(&va);
      // we decide to reuse sminhash instead of allocating another SuperMinHash structure
      let ska = sminhash.get_hsketch().clone();
      sminhash.reinit();
      let resb = sminhash.sketch_slice(&vb);
      let skb = sminhash.get_hsketch();
      //
      let jac = get_jaccard_index_estimate(&ska, &skb).unwrap();
        ...

许可

根据您的选择，许可协议为

• Apache License, Version 2.0, LICENSE-APACHE 或 http://www.apache.org/licenses/LICENSE-2.0
• MIT许可证 LICENSE-MIT 或 http://opensource.org/licenses/MIT

。