Обычный подход (по крайней мере, для меня) состоит в том, чтобы разделить строку битов хеша на несколько частей и запросить эти фрагменты для точного соответствия.Это этап «предварительной фильтрации».Затем вы можете выполнить побитовое вычисление расстояния Хэмминга для возвращенных результатов, которое должно быть только меньшим подмножеством вашего общего набора данных.Это можно сделать с помощью файлов данных или таблиц SQL.
Итак, проще говоря: скажем, у вас есть набор 32-битных хэшей в БД, и вы хотите найти каждый хэш, который находится в пределах 4-битного расстояния Хэммингавашего хэша «запроса»:
создайте таблицу с четырьмя столбцами: каждый будет содержать 8-битовый (в виде строки или целого) срез из 32-битных хэшей, с 1 по 4.
разделите хэш вашего запроса таким же образом в qslice 1 - 4.
запросите эту таблицу так, чтобы любой из qslice1=islice1 or qslice2=islice2 or qslice3=islice3 or qslice4=islice4.Это дает вам каждый хеш БД, который находится в пределах 3 бит (4 - 1) от хеша запроса.
для каждого возвращенного хеша, вычислите точное расстояние Хэмминга попарно с вашим хешем запроса(восстановление хеша на стороне индекса из четырех секций)
Количество операций на шаге 4 должно быть намного меньше, чем полное вычисление парного хемминга всей таблицы.
Этот подход был впервые описан afaik Моисеем Чарикаром в его семантике "simhash" paper и соответствующем патенте Google :
ПРИБЛИЖЕННЫЙ БЛИЖАЙШИЙ ПОИСК СОСЕДЕЙ В ПРОСТРАНСТВЕ ХАММИНГА
[...]
Учитывая битовые векторы, состоящие из d битов каждый, мы выбираем N = O (n 1 / (1+)) случайные перестановки битов.Для каждой случайной перестановки σ мы поддерживаем отсортированный порядок O σ битовых векторов в лексикографическом порядке битов, переставляемых σ.Для заданного вектора битов запроса q мы находим приблизительного ближайшего соседа, выполняя следующие действия:
Для каждой перестановки σ мы выполняем двоичный поиск по O σ, чтобы найти два битовых вектора, ближайших к q (в лексикографическомпорядок, полученный битами, переставленными σ).Теперь мы ищем в каждом из отсортированных порядков O σ, исследуя элементы выше и ниже позиции, возвращаемой двоичным поиском, в порядке длины самого длинного префикса, который соответствует q.
Моника Хензигер подробно изложено в ее статье "Поиск почти дублированных веб-страниц: масштабная оценка алгоритмов" :
3.3 Результаты для алгоритма C
Мы разбили битовую строку каждой страницы на 12 непересекающихся 4-байтовых фрагмента, создав 20-битные фрагменты, и вычислили C-подобие всех страниц, которые имели хотя бы один общий фрагмент.При таком подходе гарантируется поиск всех пар страниц с разницей до 11, т. Е. С-сходство 373. Но некоторые из них могут пропустить из-за больших отличий.
Это также объясняется в статье Обнаружение почти дубликатов для веб-сканирования Гурмитом Сингхом Манку, Арвиндом Джайном и Аниш Дас Сарма:
ПРОБЛЕМА ДИСТАНЦИИ ХАММИНГА
Определение: Учитывая набор f-битных отпечатков пальцев и отпечаток запроса F, определите, отличается ли существующий отпечаток пальца от F не более чем на k бит.(В версии вышеупомянутой проблемы в пакетном режиме мы имеем набор отпечатков запросов вместо одного отпечатка запроса)
[...]
Интуиция: рассмотрим отсортированную таблицу2 df -бит действительно случайные отпечатки пальцев.Сосредоточьтесь только на самых значимых d битах в таблице.Перечисление этих чисел d-битов составляет «почти счетчик» в том смысле, что (а) существует довольно много 2-битных комбинаций, и (б) очень мало d-битных комбинаций дублируются.С другой стороны, младшие значащие биты f - d являются «почти случайными».
Теперь выберите d так, чтобы | d - d |это небольшое целое число.Поскольку таблица сортируетсяed, одного зонда достаточно для идентификации всех отпечатков пальцев, которые соответствуют F в d наиболее значимых битовых позициях.Так как | d - d |мала, число таких совпадений также ожидается небольшим.Для каждого соответствующего отпечатка пальца мы можем легко определить, отличается ли он от F не более чем на k битовых позиций или нет (эти различия, естественно, будут ограничены f - d наименее значимыми битовыми позициями).
Описанная выше процедура помогает нам найти существующий отпечаток, который отличается от F в k позициях битов, все из которых ограничены, чтобы быть среди наименее значимых f - d битов F. Это заботится о достаточном количестве случаев.Чтобы охватить все случаи, достаточно создать небольшое количество дополнительных отсортированных таблиц, как это официально описано в следующем разделе.
PS: Большинство из этих тонких мозгов связаны с Google в некоторых случаях.уровень или какое-то время для этого, FWIW.