Хэш-функция, которая отображает аналогичные входы на аналогичные выходы

Question

Существует ли хэш-функция, в которой небольшие изменения во входных данных приводят к небольшим изменениям в выходных данных? Например, что-то вроде:

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

Answer 1

Я бы порекомендовал simhash, алгоритм Марка Манасса.

Answer 2

Я бы не назвал это хэшем, потому что точка хэша с точностью до наоборот. Однако, с вашей заявленной целью небольших изменений во входных данных, приводящих к небольшим изменениям в выходных данных, я бы посмотрел на использование либо функции soundex, либо алгоритма Ratcliff.

Answer 3

Тривиальным решением было бы XOR для всех байтов модуля NEg для 64-битного хэша, вы бы 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

Вот хороший пример перцептивного хэширования последовательностей ДНК:

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