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

Ответ 1

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

Ответ:

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

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

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

• Метрическое дерево (Википедия)
• BK-tree (Википедия)
• M-tree (Википедия)
• VP-tree (Wikipedia)
• Обложка (Википедия)

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

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

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

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

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

Добавление: Мне было очень интересно узнать о проблеме, поэтому я профилировал три реализации: линейный поиск, дерево BK и дерево VP. Обратите внимание, что деревья VP и BK очень похожи. Дети node в дереве BK являются "оболочками" деревьев, содержащих точки, каждый из которых является фиксированным расстоянием от центра дерева. A node в дереве VP имеет двух детей, один из которых содержит все точки в сфере, центрированной на центре node, а другой дочерний элемент, содержащий все внешние точки. Таким образом, вы можете представить VP node как BK node с двумя очень толстыми "оболочками" вместо многих более тонких.

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

• База данных: 100M псевдослучайные целые числа
• Количество тестов: 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

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

Например, для максимального расстояния 5 это 242825 номеров (sum _{d = 0 to 5} {32 выберите d}). Для сравнения, решение Vitris Epp для Vitrich Epip, например, проходит через 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. Мой код (на основе Dietrich's) находится здесь (игнорируйте документацию там, по крайней мере, пока, не знаете, что с этим делать, но tree.c содержит весь код, а мой test.bat показывает, как я скомпилирован и запущен (я использовал флаги от Dietrich Makefile)). Ярлык для моего решения.

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

Ответ 3

Как насчет сортировки списка, а затем выполнения бинарного поиска в этом отсортированном списке по различным возможным значениям внутри вас. Расстояние Хэмминга?

Ответ 4

Вы можете предварительно вычислить все возможные варианты исходного списка на заданном расстоянии от хамминга и сохранить его в цветном фильтре. Это дает вам быстрый "НЕТ", но не обязательно четкий ответ "Да".

Для YES сохраните список всех исходных значений, связанных с каждой позицией в цветном фильтре, и пройдите их по одному за раз. Оптимизируйте размер вашего цветного фильтра для компромиссов скорости/памяти.

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

Ответ 5

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

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

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

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

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

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

Ответ 6

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

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

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

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

• отрежьте строку запроса так же, как в qslice с 1 по 4.

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

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

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

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

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

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

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

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

[...]

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

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

Моника Хензигер расширила это в своей статье "Поиск вблизи -duplicate web pages: крупномасштабная оценка алгоритмов" :

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

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

Это также объясняется в статье Обнаружение почти дубликатов для веб-сканирования Google Gurmeet Singh Manku, Arvind Jain и Anish Das Sarma:

3. ПРОБЛЕМА РАССТОЯНИЯ ХОЗЯЙСТВА

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

[...]

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

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

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

Примечание. Я отправил аналогичный ответ на связанный с БД вопрос