Есть ли алгоритм хеширования, который терпим к незначительным различиям?

Question

Я занимаюсь поиском некоторых типов контента в Интернете, где я ищу определенные термины на веб-страницах и нахожу их местоположение на странице, а затем кеширую их для дальнейшего использования. Я хотел бы иметь возможность периодически проверять страницу на наличие серьезных изменений. Что-то вроде md5 можно сорвать, просто поместив текущую дату и время на страницу.

Существуют ли алгоритмы хеширования, которые работают для чего-то подобного?

Answer 1

Обычный способ сделать сходство документов - это shingling , который несколько сложнее, чем хеширование.Также обратите внимание на содержание, определенное по частям , чтобы узнать, как разделить документ.

Несколько лет назад я читал статью об использовании фильтров Блума для обнаружения сходства. Использование Bloom Filters для уточнения результатов веб-поиска .Это интересная идея, но я так и не смог поэкспериментировать с ней.

Answer 2

Это может быть хорошим местом для использования метрики расстояния Левенштейна , которая количественно определяет объем редактирования, необходимый для преобразования одной последовательности в другую.

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

Вы также можете попробовать какой-то гибридный подход - пусть алгоритм хеширования сообщит вам, что были внесены какие-либо изменения, и используйте его как триггер для извлечения архивной копии документа для более тщательного (Левенштейна) сравнения.

Answer 3

http://www.phash.org/ сделал что-то подобное для изображений.Jist: взять изображение, смазать его, преобразовать в оттенки серого, выполнить дискретное косинусное преобразование и посмотреть только на верхний левый квадрант результата (где находится важная информация)Затем запишите 0 для каждого значения меньше среднего и 1 для каждого значения больше среднего.Результат довольно хорош для небольших изменений.

Min-Hashing еще одна возможность.Найдите функции в своем тексте и запишите их в качестве значения.Объедините все эти значения, чтобы создать хеш-строку.

Для обоих вышеперечисленных используйте дерево точек обзора, чтобы вы могли искать ближние попадания.

Answer 4

Извините, но алгоритмы хеширования точно. Никто не способен быть терпимым к незначительным различиям. Вы должны принять другой подход.