поиск шаблонов битовых полей (кодовых книг)

Question

У меня есть набор 8-битных значений в кодовой книге (около 200 из них).

Моя программа будет генерировать 8-битное значение в ответ на ввод, и мне нужно найти все (или даже первое полезное) совпадения в кодовой книге, в которых установлены одинаковые биты. Биты, которые не установлены, не имеют значения.

Можете ли вы придумать оптимальный способ а) хранить и б) искать в кодовой книге, чтобы найти все совпадения? У меня есть стандартный линейный поиск, но он, конечно, неэффективен.

Большое спасибо ...

akevan

Answer 1

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

Вы можете получить первое совпадение в 256 байтах (11 слов памяти).

инициализация:

u_int8_t bitpatterns[256];
memset(bitpatterns,0,sizeof(bitpatterns));

for(x=sizeof(codebook)-1;x>=0;x--)
  for(y=0;y<256;y++)
    if (y&codebook[x] == y)
      bitpatterns[y] = x;

Поиск:

codeword = codebook[bitpatterns[input]];

Answer 2

Одной из оптимизаций может быть хранение ваших кодов в разных сегментах в зависимости от того, сколько бит установлено. Когда вы просматриваете коды, вам просто нужно просмотреть 1/2 кодов (в среднем, если коды распределены равномерно). Это очень простая оптимизация, но сложность алгоритма остается той же (O (n)). Сортировка одного массива по количеству установленных битов позволит вам выполнять аналогичные оптимизации без необходимости хранить коды в сегментах.

Sidenote: Я думаю, что 200 - это очень маленькое число, и я не думаю, что вы увидите значительное изменение производительности от линейного подхода, независимо от того, как вы его оптимизируете, если вы не выполните много поисков. Но я предполагаю, что смысл этого упражнения не в этом ...

Answer 3

Если вы выполняете только 8-битные поиски, было бы несложно предварительно рассчитать все ваши ответы, а затем просто сохранить их в таблице с 256 записями.Таким образом, вы получите запросы с постоянным временем, а объем памяти будет порядка 256 записей.

Answer 4

Я отправляю другой ответ, потому что получил новое (и лучшее предложение):

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

Алгоритм все еще линейный, но с поиском O (log N) для обрезания (надеюсь) большинства значений. Поиск по маленьким значениям все равно будет дорогим, поиск по большим значениям будет дешевле.

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

Answer 5

Если я понимаю, вы говорите, что если ответ имеет ТОЛЬКО биты 1,3,5, то вы хотите, чтобы все коды в кодовой книге имели флаги 1,3, 5 комплектов и вам наплевать на биты 2,4,6,7,8.

Если это так, вот ваш псевдокод:

matchingCodes = new List<Code>
foreach(code in codebook)
    if((response & code) == response) matchingCodes.add(code);