Хеширование сходства

Question

Обычно цель хэширования - превратить непрерывную функцию в дискретную: небольшое изменение на входе должно вызвать большое изменение на выходе.Однако существует ли какой-либо алгоритм хеширования, который (очень) грубо говоря, возвращает одинаковые, но (все еще разные) хеши для аналогичных входных данных?

(Примером использования этого может быть проверка того, являются ли два файла«похоже», проверяя их хэши на сходство. Конечно, некоторые ошибки всегда допустимы.)

Answer 1

Посмотрите на Хеширование с учетом населенного пункта (LSH). Это вероятностный способ быстрого нахождения группы точек около заданной, например.

Answer 2

Учитывая функцию расстояния, которая сообщает вам, насколько похожи или различаются ваши объекты, вы также можете использовать перестановки расстояний: http://www.computer.org/portal/web/csdl/doi/10.1109/TPAMI.2007.70815 или эскизы: http://portal.acm.org/citation.cfm?id=1638180

Для реализации последнего подхода: http://obsearch.net