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

Вопрос: Что мы знаем о расстоянии Хэмминга 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 (у, г)

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

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

• Дерево показателей (Википедия)
• BK-дерево (Википедия)
• M-tree (Википедия)
• VP-tree (Википедия)
• Покровное дерево (Википедия)

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

Сноска. Если вы сравниваете расстояние Хэмминга для строк фиксированной ширины, вы можете получить значительное улучшение производительности за счет использования встроенных функций сборки или процессора. Например, с помощью 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 Tree --   -- VP Tree --   -- Linear --
Dist    Results Speed   Cov     Speed   Cov     Speed   Cov
1          0.90 3800     0.048% 4200     0.048%
2         11     300     0.68%   330     0.65%
3        130      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%
any                                             2.2     100%

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

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

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

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

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

Например, для максимального расстояния 5 это 242825 чисел ( sum _{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 и т. Д. Запросами, пока не будет по крайней мере 10 секунд). прошло всего). Это довольно стабильно, я даже получаю похожие числа всего за 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, хотя вам придется расширяться вверх и вниз от начальной точки для перестановок (с использованием файлов или списков), которые разделяют начальный фрагмент, и вычисляют расстояние Хэмминга для результирующего кластера.

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

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

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

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

[...]

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

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

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

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

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

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

3. ПРОБЛЕМА УБИВАЮЩЕГО РАССТОЯНИЯ

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

[...]

Интуиция: рассмотрим отсортированную таблицу 2d f -битных действительно случайных отпечатков пальцев. Сосредоточьтесь только на наиболее значимых 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) МБ.

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

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