Эффективный поиск двоичных строк с малым расстоянием Хэмминга в большом наборе

Проблема:

Учитывая большой (~ 100 миллионов) список 32-битных целых чисел без знака, входное 32-битное целочисленное значение без знака и максимальное расстояние Хэмминга , верните все элементы списка, которые находятся в пределах указанного расстояния Хэмминга входного значения.

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

Пример:

For a maximum Hamming Distance of 1 (values typically will be quite small)

And input: 
00001000100000000000000001111101

The values:
01001000100000000000000001111101 
00001000100000000010000001111101 

should match because there is only 1 position in which the bits are different.

11001000100000000010000001111101

should not match because 3 bit positions are different.

Мои мысли на данный момент:

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

Если бы расстояние Хэмминга было бы только 1, я мог бы перевернуть каждый бит в исходном вводе и повторить указанное выше 32 раза.

Как я могу эффективно (без сканирования всего списка) обнаруживать элементы списка с расстоянием Хэмминга> 1.

Вопрос: Что мы знаем о расстоянии Хэмминга d (x, y)?

Ответ:

1. Неотрицательно: d (x, y) ≥ 0
2. Он равен нулю только для одинаковых входов: d (x, y) = 0 ⇔ x = y
3. Он симметричен: d (x, y) = d (y, x)
4. Он подчиняется неравенству треугольника , d (x, z) ≤ d (x, y) + d (y, z)

Вопрос: Почему нас это волнует?

Ответ: Потому что это означает, что расстояние Хэмминга является метрикой для метрического пространства . Есть алгоритмы индексации метрических пространств.

• Метрическое дерево (Википедия)
• BK-дерево (Википедия)
• М-дерево (Википедия)
• ВП-дерево (Википедия)
• Покровное дерево (Википедия)

Вы также можете найти алгоритмы «пространственного индексирования» в целом, зная, что ваше пространство не евклидово, а является метрическим. Многие книги по этой теме посвящены индексации строк с использованием такой метрики, как расстояние Хэмминга.

Сноска: если вы сравниваете расстояние Хэмминга для строк фиксированной ширины, вы можете получить значительное улучшение производительности, используя встроенные функции сборки или процессора. Например, с помощью GCC ( manual ) вы делаете это:

static inline int distance(unsigned x, unsigned y)
{
    return __builtin_popcount(x^y);
}

Если вы затем сообщите GCC, что компилируете для компьютера с SSE4a, то я считаю, что это должно сократиться до пары кодов операций.

Изменить: согласно ряду источников, это иногда / часто медленнее, чем обычный код маски / сдвига / добавления. Сравнительный анализ показывает, что в моей системе версия C превосходит GCC __builtin_popcountпримерно на 160%.

Приложение: Мне самому была интересна проблема, поэтому я профилировал три реализации: линейный поиск, дерево BK и дерево VP. Обратите внимание, что деревья VP и BK очень похожи. Дочерние элементы узла в BK-дереве - это «оболочки» деревьев, содержащие точки, каждая из которых находится на фиксированном расстоянии от центра дерева. Узел в дереве VP имеет двух дочерних элементов, один из которых содержит все точки в сфере с центром в центре узла, а другой дочерний элемент, содержащий все точки вне. Таким образом, вы можете думать об узле VP как о узле BK с двумя очень толстыми «оболочками» вместо множества более тонких.

Результаты были получены на моем ПК с тактовой частотой 3,2 ГГц, и алгоритмы не пытаются использовать несколько ядер (что должно быть легко). Я выбрал размер базы данных из 100 миллионов псевдослучайных чисел. Результаты представляют собой среднее значение 1000 запросов для расстояния 1..5 и 100 запросов для 6..10 и линейного поиска.

• База данных: 100 млн псевдослучайных чисел
• Количество испытаний: 1000 для расстояний 1..5, 100 для расстояний 6..10 и линейных
• Результаты: среднее количество совпадений по запросу (очень приблизительное).
• Скорость: количество запросов в секунду.
• Охват: средний процент базы данных, проверенной на запрос.

                - Дерево BK - - Дерево VP - - Линейное -
Dist Результаты Speed ​​Cov Speed ​​Cov Speed ​​Cov
1 0,90 3800 0,048% 4200 0,048%
2 11 300 0,68% 330 0,65%
3130 56 3,8% 63 3,4%
4 970 18 12% 22 10%
5 5700 8,5 26% 10 22%
6 2,6e4 5,2 42% 6,0 37%
7 1,1e5 3,7 60% 4,1 54%
8 3,5e5 3,0 74% 3,2 70%
9 1,0e6 2,6 85% 2,7 82%
10 2,5e6 2,3 91% 2,4 90%
любая 2.2 100%

В своем комментарии вы упомянули:

Я думаю, что BK-деревья можно улучшить, сгенерировав группу BK-деревьев с разными корневыми узлами и расправив их.

Я думаю, что именно по этой причине дерево VP работает (немного) лучше, чем дерево BK. Будучи «более глубоким», а не «мелким», он сравнивает с большим количеством точек, а не использует более мелкие сравнения с меньшим количеством точек. Я подозреваю, что различия более значительны в пространствах более высоких измерений.

Последний совет: конечные узлы в дереве должны быть просто плоскими массивами целых чисел для линейного сканирования. Для небольших наборов (возможно, 1000 точек или меньше) это будет быстрее и эффективнее с точки зрения памяти.

Я написал решение, в котором я представляю входные числа в битовом наборе из 2 ³² бит, поэтому я могу проверить в O (1), есть ли на входе определенное число. Затем для запрошенного числа и максимального расстояния я рекурсивно генерирую все числа в пределах этого расстояния и сверяю их с битовым набором.

Например, для максимального расстояния 5 это 242825 чисел ( сумма _{d = от 0 до 5} {32 выберите d} ). Для сравнения: например, решение Дитриха Эппа по дереву VP проходит через 22% из 100 миллионов номеров, то есть через 22 миллиона номеров.

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

Dist     BK Tree     VP Tree         Bitset   Linear

   1   10,133.83   15,773.69   1,905,202.76   4.73
   2      677.78    1,006.95     218,624.08   4.70
   3      113.14      173.15      27,022.32   4.76
   4       34.06       54.13       4,239.28   4.75
   5       15.21       23.81         932.18   4.79
   6        8.96       13.23         236.09   4.78
   7        6.52        8.37          69.18   4.77
   8        5.11        6.15          23.76   4.68
   9        4.39        4.83           9.01   4.47
  10        3.69        3.94           2.82   4.13

Prepare     4.1s       21.0s          1.52s  0.13s
times (for building the data structure before the queries)

Для небольших расстояний решение битового набора является самым быстрым из четырех. Автор вопроса Эрик прокомментировал ниже, что наибольшее расстояние интереса, вероятно, будет 4-5. Естественно, мое битовое решение становится медленнее на больших расстояниях, даже медленнее, чем линейный поиск (для расстояния 32 он будет проходить через 2 ³² числа). Но на дистанции 9 он все еще легко ведет.

Я также модифицировал тестирование Дитриха. Каждый из приведенных выше результатов предназначен для того, чтобы позволить алгоритму решить по крайней мере три запроса и столько запросов, сколько он может, примерно за 15 секунд (я выполняю раунды с 1, 2, 4, 8, 16 и т. прошло всего). Это довольно стабильно, я даже получаю похожие числа всего за 1 секунду.

Мой процессор i7-6700. Мой код (на основе Дитриха) здесь (игнорируйте документацию там, по крайней мере, пока, не знаю, что с этим делать, но он tree.cсодержит весь код и мои test.batшоу, как я скомпилировал и запустил (я использовал флаги от Дитриха Makefile)) . Ярлык к моему решению .

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

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

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

Итак, резюмируем: скажем, у вас есть куча 32-битных строк в БД или файлах и вы хотите найти каждый хэш, который находится в пределах 3-битного расстояния Хэмминга или меньше от вашей битовой строки "запроса":

1. создайте таблицу с четырьмя столбцами: каждый будет содержать 8-битный (в виде строки или int) срез 32-битных хэшей, от 1 до 4. Или, если вы используете файлы, создайте четыре файла, каждый из которых представляет собой перестановку срезов, имеющих по одному «кусочку» в начале каждого «ряда»

2. нарежьте битовую строку запроса таким же образом в qslice от 1 до 4.

3. запросить эту таблицу таким образом, что любой из qslice1=islice1 or qslice2=islice2 or qslice3=islice3 or qslice4=islice4. Это дает вам каждую строку, которая находится в пределах 7 бит ( 8 - 1) от строки запроса. При использовании файла выполните двоичный поиск в каждом из четырех файлов с перестановкой для получения тех же результатов.

4. для каждой возвращаемой битовой строки вычислить точное расстояние Хэмминга попарно с вашей битовой строкой запроса (восстановление битовых строк на стороне индекса из четырех срезов либо из БД, либо из переставленного файла)

Количество операций на шаге 4 должно быть намного меньше, чем полное попарное вычисление Хэмминга всей вашей таблицы, и это очень эффективно на практике. Кроме того, можно легко разделить файлы на файлы меньшего размера, поскольку требуется более высокая скорость, используя параллелизм.

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

Если вы работаете в памяти, а не в файлах, ваш набор данных 32-битных строк размером 100 МБ будет в диапазоне 4 ГБ. Следовательно, для четырех переставленных списков может потребоваться около 16 ГБ + ОЗУ. Хотя вместо этого я получаю отличные результаты с файлами с отображением памяти и должен меньше ОЗУ для наборов данных аналогичного размера.

Доступны реализации с открытым исходным кодом. Лучшее в этом пространстве - IMHO, сделанное для Simhash Moz , C ++, но предназначенное для 64- битных строк, а не 32-битных.

Этот подход с ограниченным расстоянием касания был впервые описан AFAIK Моисеем Чарикаром в его основополагающей статье "simhash" и в соответствующем патенте Google :

5. ПРИБЛИЗИТЕЛЬНЫЙ ПОИСК БЛИЖАЙШИХ СОСЕДЕЙ В КОСМИЧЕСКОМ ПРОСТРАНСТВЕ

[...]

Учитывая битовые векторы, состоящие из d бит каждый, мы выбираем N = O (n 1 / (1+)) случайных перестановок битов. Для каждой случайной перестановки σ мы поддерживаем отсортированный порядок O σ битовых векторов в лексикографическом порядке битов, переставляемых с помощью σ. Учитывая битовый вектор запроса q, мы находим приблизительного ближайшего соседа, выполнив следующие действия:

Для каждой перестановки σ мы выполняем двоичный поиск на O σ, чтобы найти два битовых вектора, ближайших к q (в лексикографическом порядке, полученном битами, переставленными с помощью σ). Теперь мы ищем в каждом из отсортированных порядков O σ, исследуя элементы выше и ниже позиции, возвращенной двоичным поиском, в порядке длины самого длинного префикса, соответствующего q.

Моника Хензигер подробно рассказала об этом в своей статье «Поиск почти дублирующихся веб-страниц: широкомасштабная оценка алгоритмов» :

3.3 Результаты для алгоритма C

Мы разделили битовую строку каждой страницы на 12 неперекрывающихся 4-байтовых частей, создав 20B частей, и вычислили C-подобие всех страниц, у которых есть хотя бы одна общая часть. Этот подход гарантированно найдет все пары страниц с разницей до 11, т. Е. C-подобием 373, но может пропустить некоторые из-за больших различий.

Это также объясняется в статье Гурмит Сингх Манку, Арвинд Джайн и Аниш Дас Сарма «Обнаружение почти дубликатов для веб- сканирования»:

3. ПРОБЛЕМА УБИВАЮЩЕЙ ДИСТАНЦИИ

Определение: учитывая набор f-битных отпечатков пальцев и отпечаток запроса F, определить, отличается ли существующий отпечаток от F не более чем на k бит. (В пакетной версии вышеупомянутой проблемы у нас есть набор отпечатков пальцев вместо одного отпечатка запроса)

[...]

Интуиция: рассмотрим отсортированную таблицу из 2-х битных по-настоящему случайных отпечатков пальцев. Сосредоточьтесь только на наиболее значимых d битах в таблице. Перечисление этих d-битовых чисел составляет «почти счетчик» в том смысле, что (а) существует довольно много двумерных битовых комбинаций и (б) дублируется очень мало d-битовых комбинаций. С другой стороны, младшие биты f - d «почти случайны».

Теперь выберите d так, чтобы | d - d | - маленькое целое число. Поскольку таблица отсортирована, одного зонда достаточно, чтобы идентифицировать все отпечатки пальцев, которые соответствуют F в d наиболее значимых битовых позициях. Поскольку | d - d | мало, количество таких совпадений также ожидается невелико. Для каждого совпадающего отпечатка пальца мы можем легко выяснить, отличается ли он от F не более чем в k битовых позициях или нет (эти различия, естественно, будут ограничены f - d наименее значимыми битовыми позициями).

Описанная выше процедура помогает нам найти существующий отпечаток, который отличается от F k битовыми позициями, все из которых ограничены, чтобы быть среди наименее значимых f - d битов F. Это позволяет позаботиться о значительном количестве случаев. Чтобы охватить все случаи, достаточно создать небольшое количество дополнительных отсортированных таблиц, как формально описано в следующем разделе.

Примечание: я опубликовал аналогичный ответ на связанный вопрос только для БД.

Вы можете предварительно вычислить все возможные варианты исходного списка в пределах указанного расстояния Хэмминга и сохранить их в фильтре Блума. Это дает вам быстрый ответ «НЕТ», но не обязательно четкий ответ «ДА».

Если ДА, сохраните список всех исходных значений, связанных с каждой позицией в фильтре Блума, и просматривайте их по одному. Оптимизируйте размер фильтра Блума с учетом компромисса между скоростью и памятью.

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

Как насчет сортировки списка, а затем выполнения двоичного поиска в этом отсортированном списке по различным возможным значениям в пределах вашего расстояния Хэмминга?

Один из возможных подходов к решению этой проблемы - использование структуры данных с несвязным набором . Идея состоит в том, чтобы объединить элементы списка с расстоянием Хэмминга <= k в одном наборе. Вот схема алгоритма:

• Для каждого члена списка вычислите все возможные значения с расстоянием Хэмминга <= k. Для k = 1 имеется 32 значения (для 32-битных значений). Для k = 2, 32 + 32 * 31/2 значения.

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

  • Если значение находится в исходном вводе, выполните операцию «объединения» с элементом списка .

  • Сохраняйте количество выполненных операций объединения в переменной.

Вы начинаете алгоритм с N непересекающихся множеств (где N - количество элементов во входных данных). Каждый раз, когда вы выполняете операцию объединения, вы уменьшаете на 1 количество непересекающихся множеств. Когда алгоритм завершается, структура данных с непересекающимся множеством будет иметь все значения с расстоянием Хэмминга <= k, сгруппированные в непересекающиеся множества. Эта структура данных с непересекающимися наборами может быть вычислена почти за линейное время .

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

Чтобы запросить, начните с бюджета расстояния dи вашего входного слова w. Для каждого сегмента верхнего уровня со значением байта bвычислите расстояние Хэмминга d_0между bи старшим байтом w. Рекурсивный поиск в этом сегменте с бюджетом d - d_0: то есть для каждого байтового значения b'пусть d_1будет расстояние Хэмминга между b'и вторым байтом w. Рекурсивный поиск на третьем уровне с бюджетом d - d_0 - d_1и т. Д.

Обратите внимание, что ведра образуют дерево. Когда ваш бюджет становится отрицательным, прекратите поиск в этом поддереве. Если вы рекурсивно спускаетесь в лист, не увеличивая бюджет расстояния, это значение листа должно быть частью выходных данных.

Вот один из способов представить структуру внешней границы сегмента: иметь массив длиной 16_777_216 ( = (2**8)**3 = 2**24), где элемент с индексом iявляется начальным индексом сегмента, содержащего значения в диапазоне [256 * i, 256 * i + 255]. Чтобы найти индекс, который находится за пределами этого сегмента, найдите индекс i + 1 (или используйте конец массива для i + 1 = 2 ** 24).

Бюджет памяти составляет 100 м * 4 байта на слово = 400 МБ для входных данных и 2 ** 24 * 4 байта на адрес = 64 МБ для структуры индексации, или всего лишь полгигаба. Структура индексации накладных расходов на исходные данные составляет 6,25%. Конечно, после того, как вы построили структуру индексации, вам нужно сохранить только самый младший байт каждого входного слова, поскольку остальные три неявно присутствуют в индексе в структуре индексации, в общей сложности ~ (64 + 50) МБ.

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

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