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

Question

[Александр Алексеев]

О том, что такое перцептивные хэши в интернете есть много хороших и понятных статей. Однако, что происходит, когда мы задаём поиск по базе этих хэшей? С одной стороны, можно хэши проиндексировать. В этом случае поиск будет осуществляться очень быстро, но мы не сможем найти немного отличающиеся изображения. С другой стороны, можно осуществить поиск по всем хэшам в базе данныч. В этом случае, нам придётся вычислять расстояние Хэмминга для каждой пары (заданный образец и хэш из бады данных). Это даё т большую гибкость в поиске, но сам поиск становится очень медленным. Даже для миллиона хешей поиск будет идти десятки секунд! Так как же на самом деле их сравнивают?

Answer 1

[Wataru]

Есть всякие индексы, позволяющие искать совпадение с несколькими ошибками. Конечно, там будет какое-то количество лишней работы, но все-равно просматривать надо лишь малую часть всех хешей в базе.

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

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

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

Answer 2

[Александр Алексеев]

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

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

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

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

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

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

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

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

Comments

[d'Ivan]

Это ответ?

Answer 3

[Karpion]

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

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

Comments

[Александр Алексеев]

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

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

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

Товарищ выше тоже так рассуждал. Если Вы даёте советы посторонним людям (вроде меня), то всё вроде как логично. Но если Вы сами попробуете войти в эту комнату (с Вашими советами), то это - ад. За такое могут и с работы уволить, а , если Вы частник, то можете просто вылететь в трубу.

Answer 4

[d'Ivan]

Подсчет расстояния Хэмминга на большом наборе данных

Comments

[Александр Алексеев]

Спасибо, интересная статья!
Однако, несмотря на приведённый в статье пример, не понятно, как современные поисковые системы осуществляют поиск за доли секунды по базе из нескольких миллиардов изображений! Там (в описании HEngine) подобными возможностями даже и не пахнет (на мой взгляд).