Хранение и индексация двоичных строк в базе данных

Question

Двоичная строка, как определено здесь, представляет собой «массив» битов фиксированного размера. Я называю их строками, поскольку у них нет порядка (сортировка / индексация их по номерам не имеет смысла), каждый бит не зависит от других. Каждая такая строка имеет длину N битов, а N - сотни.

Мне нужно сохранить эти строки и получить новый запрос двоичной строки для ближайшего соседа, используя расстояние Хемминга в качестве метрики расстояния.
Существуют специализированные структуры данных (деревья метрик) для поиска по метрике (деревья VP, деревья покрытия, M-деревья), но мне нужно использовать обычную базу данных (в моем случае MongoDB).

Существует ли какая-либо функция индексации, которая может быть применена к двоичным строкам, которая может помочь БД получить доступ только к подмножеству записей перед выполнением сопоставления расстояний Хэмминга один к одному? В качестве альтернативы, как можно было бы реализовать такой поиск по Хэммингу в стандартной БД?

Answer 1

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

Итак, скажем

C <- some constant bitstring
S <- bitstring you're trying to find the best match for
B <- a bitstring in the database
distS <- hamming_dist(S,C)
distB <- hamming_dist(B,C)

Таким образом, для каждого B вы должны хранить его соответствующий distB.

Нижняя граница для hamming(B,S) будет тогда abs(distB-distS).И верхняя граница будет distB+distS.

Вы можете сбросить все B так, чтобы нижняя граница была выше, чем нижняя верхняя граница.

Я не уверен на 100%, какк оптимальному способу выбрать какой CЯ думаю, вы хотели бы, чтобы это была цепочка битов, близкая к «центру» вашего метрического пространства цепочек битов.

Answer 2

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

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

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