java - 两个十六进制数的相似度

Question

我正在尝试使用汉明和 Levenshtein 距离找到相似的哈希值(十六进制哈希值)。假设两个哈希值相似，如果它们的汉明距离小于 10(不同位数)。

Hash 1= ffffff (base 16)
Hash 2= fffff0 (base 16)

两个哈希之间的汉明距离是4。它们是相似的。因为，

Hash 1= 11111111 11111111 11111111 (base 2)
Hash 2= 11111111 11111111 11110000 (base 2)

我有 800 万个这样的哈希值。我想知道什么是适合存储 800 万个哈希值的数据结构。我最初尝试了“Trie”，但考虑了以下场景，

Hash 1 = 0fabde (00001111 10101011 11011110)
Hash 2 = adcbfe (10101010 11001011 11111110)

汉明距离为 7。所以我无法进行前缀搜索。

我知道我可以使用 XOR 和 Integer.bitCount() 来获取不同位数，但我有一个目标哈希和 800 万个哈希来搜索，即给定一个哈希，我必须在其中找到所有相似的哈希我们在存储库中拥有 800 万个哈希值。

有没有什么方法可以有效地存储哈希值，从而减少我的搜索基数？

Answer 1

如果散列像显示的那样小，您可以“直接”对它们进行索引 - 也就是说，将它们放在一个大数组中，然后对索引进行一些数学计算。

仅生成可能对应于请求的汉明距离 d 内的哈希值的索引非常简单，只需将 key 与包含最多 d 的所有掩码进行异或> 设置位(见下文)。由于有 800 万个哈希值，但可能只存在 1600 万个，因此预计大约一半的已访问索引是“有用的”，即可以找到一些东西。

要生成掩码，您可以使用旧的 NextBitPermutation技巧，之前已经在 StackOverflow 上发布过多次，例如 here .对于java，只需使用逻辑右移并将__builtin_ctz替换为numberOfTrailingZeros即可得到(未测试)

int t = v | (v - 1);
int w = (t + 1) | (((~t & -~t) - 1) >>> (Integer.numberOfTrailingZeros(v) + 1));

这里的 w 是 v 之后的位置换。

全局结构类似于(未测试)

for (int k = 1; k <= d; k++) {
    int diff = (1 << k) - 1;
    while (diff <= 0xFFFFFF) {
        if (hashes[key ^ diff])
            // do something with it
        diff = nextBitPermutation(diff);
    }
}