algorithm - 将相似输入映射到相似输出的哈希函数？

Question

是否存在散列函数，其中输入的微小变化会导致输出的微小变化？例如，类似：

hash("Foo") => 9e107d9d372bb6826bd81d3542a419d6
hash("Foo!") => 9e107d9d372bb6826bd81d3542a419d7 <- note small difference

Answer 1

我不会称其为散列，因为散列的点正好相反。但是，由于您声明的目标是输入的微小变化产生输出的微小变化，我会考虑使用soundex函数或Ratcliff算法。

Answer 2

我会推荐Mark Manasse的simhash算法。

Answer 3

一个简单的解决方案是对所有字节模块 NEg 进行 64 位哈希的 XOR，您将 XOR (input[0] ^ input[8] ^ input[16]) + 256*(input[1] ^ input[9 ] ^ input[17]) 等因此，“Foo”散列为“Foo\0\0\0\0\0”和“Foo！” 散列到“Foo！\0\0\0\0”。

Answer 4

局部敏感散列（LSH）降低了高维数据的维数。LSH 对输入项目进行哈希处理，以便相似项目以高概率映射到相同的“桶”：

https://en.wikipedia.org/wiki/Locality-sensitive_hashing

另见：https ://en.wikipedia.org/wiki/Perceptual_hashing

这是对 DNA 序列进行感知散列的一个很好的例子：

http://arxiv.org/pdf/1412.5517.pdf