Как найти ближайшие пары (расстояние Хэмминга) строки двоичных бинов в Ruby без проблем O ^ 2?

Question

У меня есть MongoDB с около 1 миллиона документов.Во всех этих документах есть строка, представляющая 256-битную ячейку с единичными и нулевыми значениями, например:

0110101010101010110101010101

В идеале я хотел бы запросить близкие двоичные совпадения.Это означает, что если два документа имеют следующие номера.Да, это расстояние Хэмминга.

В настоящее время это не поддерживается в Монго.Итак, я вынужден сделать это на уровне приложений.

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

У меня много оперативной памяти.И в ruby, кажется, есть замечательная жемчужина (алгоритмы), которая может создать множество деревьев, ни одно из которых, как мне кажется, не работает (пока), которое уменьшило бы количество запросов, которые мне нужно было бы сделать.

В идеале, я хотел бы сделать 1 миллион запросов, найти почти повторяющиеся строки и иметь возможность обновлять их, чтобы отразить это.

Любые мысли будут оценены.

Answer 1

Я закончил поиск всех документов в памяти .. (подмножество с идентификатором и строкой).

Затем я использовал BK Tree для сравнения строк.

Answer 2

Расстояние Хэмминга определяет метрическое пространство , поэтому вы можете использовать алгоритм O (n log n), чтобы найти ближайшую пару точек , которая имеет типичное деление и-победить природу.

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

Редактировать: Теперь я вижу, что Википедия фактически не предоставляет алгоритм, поэтому вот одно описание .

Редактировать 2: Алгоритм можно изменить, чтобы он сдался, если на расстоянии меньше n нет пар. Для случая расстояния Хэмминга: просто посчитайте уровень рекурсии, на котором вы находитесь. Если вы не нашли что-то на уровне n ни в одной ветви, то сдавайтесь (другими словами, никогда не вводите n + 1). Если вы используете метрику, в которой разделение на одно измерение не всегда дает расстояние 1, вам необходимо настроить уровень рекурсии, в котором вы отказываетесь.

Answer 3

Насколько я понимаю, у вас есть входная строка X, и вы хотите запросить в базе данных документ, содержащий строковое поле b, чтобы расстояние Хэмминга между X и document.b было меньше некоторого небольшое число d.

Вы можете сделать это за линейное время , просто отсканировав все ваши документы N = 1M и рассчитав расстояние (которое занимает небольшое фиксированное время для каждого документа). Поскольку вам нужны только документы с расстоянием, меньшим d, вы можете отказаться от сравнения после d несопоставленных символов; вам нужно сравнить все 256 символов, если большинство из них совпадают.

Вы можете попробовать отсканировать меньше N документов, то есть получить лучше, чем линейное время .

Пусть ones(s) будет числом 1 с в строке s. Для каждого документа сохраните ones(document.b) как новое индексированное поле ones_count. Тогда вы можете запрашивать документы только в том случае, если количество документов достаточно близко к ones(X), в частности, ones(X) - d <= <code>document.ones_count <= <code>ones(X) + d. Индекс Монго должен сработать.

Если вы хотите найти все достаточно близкие пары в наборе, см. Ответ @ Philippe.

Answer 4

Это звучит как какая-то алгоритмическая проблема. Вы можете попробовать сначала сравнить их с одинаковым числом в 1 или 0 битов, а затем перейти к следующему списку. Те, которые идентичны, конечно же, выйдут на первое место. Я не думаю, что тонны ОЗУ здесь помогут.

Вы также можете попробовать работать с более мелкими кусками. Вместо того, чтобы иметь дело с 256-битными последовательностями, вы могли бы рассматривать это как 32-битные последовательности? 16 16-битных последовательностей? В этот момент вы можете вычислить различия в справочной таблице и использовать ее как своего рода индекс.

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