Пакет для быстрого определения сходства между двумя битовыми последовательностями

Question

Мне нужно сравнить битовую последовательность запроса с базой данных до миллиона битовых последовательностей. Все битовые последовательности имеют длину 100 бит. Мне нужно, чтобы поиск был максимально быстрым. Существуют ли пакеты для быстрого определения сходства между двумя битовыми последовательностями? --Edit-- Битовые последовательности чувствительны к положению.

Я видел возможный алгоритм для Bit Twiddling Hacks , но если есть готовый пакет, который был бы лучше.

Answer 1

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

• Для каждого битового набора подсчитайте биты.
• Сохранение битовых комбинаций в multi_map (если вы используете STL, в Java, вероятно, есть что-то похожее)

Затем используйте следующий алгоритм:

• Создайте 2 коллекции: одну для хранения найденных шаблонов, другую для хранения, возможно, хороших шаблонов (эта вторая коллекция, вероятно, должна быть картой, отображающей «расстояния» для шаблонов)
• Возьмите свой собственный шаблон и сосчитайте биты, предположите, что это N
• Посмотрите в мультикарте на индекс N, все эти шаблоны будут иметь одинаковую сумму, но не обязательно будут полностью идентичными
• Сравните все шаблоны по индексу N. Если они равны, сохраните результат в первой коллекции. Если они не равны, сохраните результат во второй коллекции / карте, используя разницу в качестве ключа.
• Посмотрите в мультикарте на индекс N-1, все эти шаблоны будут иметь расстояние 1 или более
• Сравните все шаблоны по индексу N-1. Если они имеют расстояние 1, сохраните их в первой коллекции. Если они имеют большее расстояние, сохраните результат во второй коллекции / карте, используя разницу в качестве ключа.
• Повторите для индекса N + 1
• Теперь посмотрите во второй коллекции / карте и посмотрите, есть ли что-то, сохраненное на расстоянии 1. Если это так, удалите их из второй коллекции / карты и сохраните их в первой коллекции.

Повторяйте это для расстояния 2, расстояния 3, ... пока у вас не будет достаточно паттернов.

Если количество требуемых шаблонов не слишком велико, а среднее расстояние также не слишком велико, то число реальных сравнений между шаблонами, вероятно, составляет всего несколько%.

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

Пожалуйста, держите меня в курсе ваших результатов.

Answer 2

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

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

например. Предположим, у нас есть следующее дерево:

      root
   0       1
 0   1   0   1
0 1 0 1 0 1 0 1

Если вы хотите искать шаблоны, похожие на 011, и хотите разрешить не более 1 разного бита, выполните поиск следующим образом (рекурсивно или многопоточно):

• Начало в корне
• Возьмите левую ветвь (0), это похоже, поэтому разница все еще 0
  • Возьмите левую ветвь (0), это отличается, поэтому разница становится 1, что все еще приемлемо
    • возьмите левую ветвь (0), это отличается, поэтому разница становится 2, что слишком велико. Прервать поиск в этой ветке.
    • взять правую ветвь (1), она равна, поэтому разница остается 1, продолжить поиск в этой ветке (здесь не показано)
  • Возьмите правую ветвь (1), она равна, поэтому разница остается 0, продолжайте
    • возьмите левую ветвь (0), это отличается, поэтому разница становится 1, что все еще приемлемо, продолжайте.

Это продолжается до тех пор, пока вы не найдете свои битовые комбинации.

Если ваши битовые шаблоны более динамичны и обновляются в вашем приложении, вам придется обновить дерево.

Если проблема с памятью, рассмотрите возможность перехода на 64-битную версию.

Answer 3

Я придумал второй вариант.

Для каждой битовой комбинации из миллиона подсчитайте количество битов и сохраните битовые комбинации в multi_map STL (если вы пишете на C ++).

Затем посчитайте количество бит в вашем шаблоне. Предположим, что в вашем битовом массиве установлено N битов.

Если вы хотите разрешить не более D различий, посмотрите все битовые комбинации в multi_map, имеющие ND, N-D + 1, ..., N-1, N, N + 1, ... N + D-1, N + D бит.

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

(Первоначально я думал, что это можно решить путем подсчета даже 0 и неровных 1, но это не так.)

Предполагая, что вы хотите разрешить 1 различие, вы должны искать 3 слота в multi_map из 100 возможных слотов, оставляя вам 3% фактических битовых комбинаций для полного сравнения.