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

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

68 голосов
/ 17 июня 2011

Проблема:

Учитывая большой (~ 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.

Ответы [ 6 ]

100 голосов
/ 17 июня 2011

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

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

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

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

Сноска: Если вы сравниваете расстояние Хэмминга для строк фиксированной ширины, вы можете добиться значительного улучшения производительности, используя встроенные функции или встроенные функции процессора. Например, с помощью 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 и линейного поиска.

  • База данных: 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 баллов или меньше) это будет быстрее и эффективнее для использования памяти.

8 голосов
/ 21 сентября 2016

Я написал решение, в котором я представляю входные числа в битовом наборе 2 32 бит, поэтому я могу проверить в 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 32 чисел). Но для расстояния 9 он все еще легко ведет.

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

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

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

3 голосов
/ 27 ноября 2017

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

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

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

  1. создайте таблицу с четырьмя столбцами: каждый из них будет содержать 8-битный (в виде строки или целого) срез из 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, хотя вам придется расширяться вверх и вниз от начальной точки для перестановок (с использованием файлов или списков), которые разделяют начальный блок и вычисляют расстояние Хемминга для результирующего кластера.

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

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

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

  1. ПРИБЛИЖЕННЫЙ ПОСЛЕДНИЙ ПОИСК СОСЕДЕЙ В ПРОСТРАНСТВЕ ХАММИНГА

[...]

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

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

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

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

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

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

  1. ПРОБЛЕМА ХАММИНГА РАССТОЯНИЯ

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

[...]

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

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

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

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

1 голос
/ 06 апреля 2015

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

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

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

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

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

Вы запускаете алгоритм с N непересекающимися множествами (где N - количество элементов на входе). Каждый раз, когда вы выполняете операцию объединения, вы уменьшаете количество непересекающихся множеств на 1. Когда алгоритм завершается, структура данных с непересекающимся множеством будет иметь все значения с расстоянием Хэмминга <= k, сгруппированные в непересекающиеся множества. Эта структура данных с непересекающимися наборами может быть вычислена в <a href="https://www.topcoder.com/community/data-science/data-science-tutorials/disjoint-set-data-structures/" rel="nofollow"> почти линейном времени .

1 голос
/ 17 июня 2011

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

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

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

1 голос
/ 17 июня 2011

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

...