Как нечеткое совпадение с коротким битовым шаблоном в длинном? - PullRequest
Новая
       9

Как нечеткое совпадение с коротким битовым шаблоном в длинном?

1 голос
/ 15 апреля 2011

Я сталкиваюсь с проблемой, когда пытаюсь сопоставить комбинацию коротких битов с длинной: у меня есть одна комбинация длинных битов, например, 6 тыс. Битов, хранящихся в массиве символов, также короткий, скажем, 150 битов, также хранящихся в массиве символов. Теперь я хочу проверить, находится ли короткий битовый шаблон в длинном битовом шаблоне. Хотя нет необходимости в том, чтобы короткий битовый шаблон точно совпадал с какой-либо частью длинного битового шаблона, я определю пороговое значение, если в качестве коэффициента битовых ошибок под ним я возьму совпадение двух шаблонов.

Учитывая проблему смещения, я не могу придумать элегантного решения. Один из способов, который я могу выяснить, - преобразовать битовый шаблон в символьный, то есть преобразовать бит 1 в «1», 0 в «0» и применить алгоритм сопоставления строк. Но, боюсь, это может стоить памяти в 7-8 раз дороже моей системы. Кто-то вокруг меня рекомендует отпечаток Рабина , однако, похоже, он не предназначен для такого рода проблем.

Надеюсь, ты сможешь мне помочь.

Спасибо и всего наилучшего.

Ответы [ 3 ]

2 голосов
/ 15 апреля 2011

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

Вместо того, чтобы реализовывать много побитовой арифметики вручную, попробуйте Многоточную библиотеку Gnu , которая включает несколько функций цепочки битов .

  • Используйте mpz_tdiv_q_2exp для сдвига вправо длинного шаблона по одному биту за раз,
  • mpz_tdiv_r_2exp для извлечения последних 150 бит и
  • mpz_hamdist, чтобы найти число битов, переброшенных между извлеченными битами и коротким шаблоном.

Должно быть достаточно быстро и быстро писать!

В качестве начальной оптимизации я бы предложил сдвинуть 150-битную комбинацию с шагом в один бит до 7 бит, чтобы у вас было 8 шаблонов для сравнения, от 150 до 157 бит. Затем, вместо того, чтобы сдвигать длинную комбинацию по одному биту за раз (что является медленным и, вероятно, доминирует во время выполнения), сдвигайте 8 бит за раз. Обязательно очистите биты, которые вы не хотите сравнивать.

1 голос
/ 15 апреля 2011

Решения с перемещением короткой битовой комбинации вдоль более длинной имеют сложность O (N * M) (N - размер короткого сегмента, M - размер длинного сегмента).

Если размеры будут расти, вы можете рассматривать это как проблему нахождения сдвига, максимизирующего (или превышающего порог) корреляцию между двумя сигналами и ускоряющего его с помощью быстрого преобразования Фурье. Это может дать что-то вроде O (N * logN), если я не ошибаюсь.

1 голос
/ 15 апреля 2011

Позволяет вызвать короткую битовую последовательность S и длинную битовую последовательность L. Я имею в виду следующий алгоритм: 

1- XOR S with size(S) rightmost bits of L. Say this is R
2- AND R with R-1 until zero, count how many times, if less than threshold 
   pattern is found
3- Shift right L and go to 1 if size(L) >= size(S)

Это должно занять O(size(L)*size(S)) время в худшем случае. Но поскольку число 1 с намного меньше, чем size(S) в каждой итерации, на практике оно должно быть эффективным.

...