V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
ly710
V2EX  ›  问与答

有没有大神对最小哈希比较了解?问题请教

  •  
  •   ly710 · 2022-10-09 11:42:01 +08:00 · 711 次点击
    这是一个创建于 580 天前的主题,其中的信息可能已经有所发展或是发生改变。

    https://en.wikipedia.org/wiki/Jaccard_index
    根据定义有
    图片
    那么可以根据这个公式计算出|A∩B|,相似数可以通过 A 和 B 的最小哈希签名计算获取,算法如下:

        public static float compare(final int numOfBits, final byte[] data1, final byte[] data2) {
            if (data1.length != data2.length) {
                return 0;
            }
            final int count = countSameBits(data1, data2);
            return (float) count / (float) numOfBits;
        }
    
        protected static int countSameBits(final byte[] data1, final byte[] data2) {
            int count = 0;
            for (int i = 0; i < data1.length; i++) {
                byte b1 = data1[i];
                byte b2 = data2[i];
                for (int j = 0; j < 8; j++) {
                    if ((b1 & 1) == (b2 & 1)) {
                        count++;
                    }
                    b1 >>= 1;
                    b2 >>= 1;
                }
            }
            return count;
        }
    

    https://github.com/codelibs/minhash/blob/master/src/main/java/org/codelibs/minhash/MinHash.java
    可以看到就是比对两个数组相同元素的数量。
    那么这个方法能不能扩展到三个集合?求三个集合交集的元素数量
    J(A, B, C)=|A∩B∩C|/|A∪B∪C|
    J(A, B, C)还是通过 A, B, C 的最小哈希签名计算获得,就是上面的算法把两个数组换成三个数组,三个集合同位置元素相同 count++ 不知道扩展成三个集合以后,上面的公式和算法能不能成立?数学比较差,请教各位,谢谢!

    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1118 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 19:07 · PVG 03:07 · LAX 12:07 · JFK 15:07
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.