Например, можно проиндексировать все последовательности из n символов подряд в каждом хеше. Потом поискать в этом индексе все последовательности из n символов в образце. Потом хеши из получившегося списка уже проверить на расстояние хемминга. Если брать n < L/k, где L - длина хеша, а k -допустимое количество ошибок, то все нужные хеши попадут в список. Чем больше n, тем меньше лишнего будет в списке.
Это ж сколько последовательностей будет? Сотни? Тысячи? Для каждого хэша?
Другой пример - использование бора (trie). Все хеши складываются в бор. Потом там запускается рекурсивный алгоритм, который может сделать k ошибок (параметр функции). Он или идет по текущему символу или делает ошибку и идет по любой другому ребру, но уже там может сделать максимум k-1 ошибку. Конечно, этот метод будет заходить в тупики, но он обойдет лишь малую долю всего дерева.
Даже если и так, то где хранить этот бор? В ОЗУ? Накладно, да и невозможно при большой базе данных. Рипать с диска? Даже с SSD это займёт много (очень много) операций. Если даже предположить, что наш хэш состоит из 8x8 бит (8 байт), то кол-во вариантов даже с учётом 1 ошибки уже 64 штуки. Для двух ошибок - несколько тысяч!
Или, более оптимальный для поиска, но менее быстрый при добавлении вариант - в индексе хранятся все хеши со всем возможными ошибками. Он будет сильно жирнее, конечно, но поиск будет работать быстро.
Это вообще пипец! Думаю, Вы просто не понимаете, что размер индексов увеличится в тысячи раз даже для двух ошибок!
Если база маленькая, то проще, конечно же провести поэлементное сравнение. Меня интересует, как это делают большие ребята типа Яндекса или Гугла или TinEye.
Я написал свой алгоритм поиска изображений, который в корне отличается от перцептивных хэшей, но мне интересно знать, как у них всё работает. Неужно поиск по изображениям они делают на сотнях и тысячах серверов?
Средний
