將類似輸入映射到類似輸出的散列函數？

Question

有沒有一個散列函數，其中輸入的小變化導致輸出的小變化？例如，像：

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

Answer 1

一個平凡的解決方案將是XOR所有字節模塊N.例如對於一個64位散列，你需要XOR（輸入[0] ^輸入[8] ^輸入[16]）+ 256 *（輸入[1] ^輸入[9] ^輸入[17]）等。 因此， 「Foo」哈希爲「Foo \ 0 \ 0 \ 0 \ 0 \ 0」和「Foo！」哈希到「Foo！\ 0 \ 0 \ 0 \ 0」。

Answer 2

我不會稱之爲散列，因爲散列的點恰恰相反。然而，你所說的目標是輸入產生微小變化的小變化，我會考慮使用soundex函數或Ratcliff算法。

Answer 3

我會推薦Mark Manasse的simhash，algorithm。

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