algorithm - 同様の入力を同様の出力にマップするハッシュ関数?

Question

入力の小さな変化が出力の小さな変化になるハッシュ関数はありますか? たとえば、次のようなものです。

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

Answer 1

ハッシュのポイントは正反対なので、これをハッシュとは呼びません。ただし、入力の小さな変化が出力の小さな変化を生み出すというあなたの目標により、soundex関数またはRatcliffアルゴリズムのいずれかを使用することを検討します。

Answer 2

Mark Manasseによるsimhashアルゴリズムをお勧めします。

Answer 3

ローカリティ センシティブ ハッシュ (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

Answer 4

些細な解決策は、64ビットハッシュのすべてのバイトモジュールNEgを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" にハッシュします。