alekseev_ap
@alekseev_ap
Свободный разработчик

Как сравниваются перцептивные хэши?

О том, что такое перцептивные хэши в интернете есть много хороших и понятных статей. Однако, что происходит, когда мы задаём поиск по базе этих хэшей? С одной стороны, можно хэши проиндексировать. В этом случае поиск будет осуществляться очень быстро, но мы не сможем найти немного отличающиеся изображения. С другой стороны, можно осуществить поиск по всем хэшам в базе данныч. В этом случае, нам придётся вычислять расстояние Хэмминга для каждой пары (заданный образец и хэш из бады данных). Это даё т большую гибкость в поиске, но сам поиск становится очень медленным. Даже для миллиона хешей поиск будет идти десятки секунд! Так как же на самом деле их сравнивают?
  • Вопрос задан
  • 206 просмотров
Пригласить эксперта
Ответы на вопрос 4
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Есть всякие индексы, позволяющие искать совпадение с несколькими ошибками. Конечно, там будет какое-то количество лишней работы, но все-равно просматривать надо лишь малую часть всех хешей в базе.

Например, можно проиндексировать все последовательности из n символов подряд в каждом хеше. Потом поискать в этом индексе все последовательности из n символов в образце. Потом хеши из получившегося списка уже проверить на расстояние хемминга. Если брать n < L/k, где L - длина хеша, а k -допустимое количество ошибок, то все нужные хеши попадут в список. Чем больше n, тем меньше лишнего будет в списке.

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

Или, более оптимальный для поиска, но менее быстрый при добавлении вариант - в индексе хранятся все хеши со всем возможными ошибками. Он будет сильно жирнее, конечно, но поиск будет работать быстро.
Ответ написан
alekseev_ap
@alekseev_ap Автор вопроса
Свободный разработчик
Например, можно проиндексировать все последовательности из n символов подряд в каждом хеше. Потом поискать в этом индексе все последовательности из n символов в образце. Потом хеши из получившегося списка уже проверить на расстояние хемминга. Если брать n < L/k, где L - длина хеша, а k -допустимое количество ошибок, то все нужные хеши попадут в список. Чем больше n, тем меньше лишнего будет в списке.

Это ж сколько последовательностей будет? Сотни? Тысячи? Для каждого хэша?

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

Даже если и так, то где хранить этот бор? В ОЗУ? Накладно, да и невозможно при большой базе данных. Рипать с диска? Даже с SSD это займёт много (очень много) операций. Если даже предположить, что наш хэш состоит из 8x8 бит (8 байт), то кол-во вариантов даже с учётом 1 ошибки уже 64 штуки. Для двух ошибок - несколько тысяч!

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

Это вообще пипец! Думаю, Вы просто не понимаете, что размер индексов увеличится в тысячи раз даже для двух ошибок!

Если база маленькая, то проще, конечно же провести поэлементное сравнение. Меня интересует, как это делают большие ребята типа Яндекса или Гугла или TinEye.

Я написал свой алгоритм поиска изображений, который в корне отличается от перцептивных хэшей, но мне интересно знать, как у них всё работает. Неужно поиск по изображениям они делают на сотнях и тысячах серверов?
Ответ написан
@Karpion
Перцептивный хэш тем и хорош, что для слабо различающихся изображений он одинаковый.

А ещё можно организовать БД с этими хешами так, чтобы каждый хэш содержал ссылки на все хэши, которые от него мало отличаются. Ну или можно по ходе дела сгенерировать все хэши, отличающиеся от данного на один бит, на два бита, на три бита, etc; ну и запросить БД по этим вариациям.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы