两个十六进制数的相似性

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

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

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

要生成掩码，您可以使用旧的 NextBitPermutation trick, which has been posted on Whosebug several times before, for example 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);
    }
}

两个十六进制数的相似性

Similarity of two Hexadecimal numbers

java

search

data-structures

similarity

hamming-distance