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

2022-10-09 11:42:01 +08:00
 ly710

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++ 不知道扩展成三个集合以后,上面的公式和算法能不能成立?数学比较差,请教各位,谢谢!

855 次点击
所在节点    问与答
0 条回复

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://ex.noerr.eu.org/t/885479

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX