Поиск шаблона в двоичном массиве - PullRequest
Новая
       27

Поиск шаблона в двоичном массиве

0 голосов
/ 08 июня 2019

Я пишу функцию для поиска в двоичном массиве (файл растрового изображения) шаблона битов. Размер шаблона от 5 до 8 бит. Я реализовал эту функцию как тестирование для каждого бита в массиве и в шаблоне. Однако это не так эффективно, как должно быть.

Прежде всего я хочу реализовать этот код на C. 



Point* FindPattern(imgInfo* pImg, int pSize, int* ptrn, Point* pDst, int* fCnt)
{
    int i, j, k, l;
    int mask;
    int rx = pSize >> 16;
    int ry = pSize & 0xFFFF;

    *fCnt = 0;
    for (i=0; i < pImg->height - ry; ++i)
        for (j=0; j < pImg->width - rx; ++j)
        {
            // for a rectangle with upper lefr corner in (i,j)
            // check if there is pattern in image
            for (k=0; k < ry; ++k)
            {
                mask = 1 << (rx - 1);
                for (l=0; l < rx; ++l, mask >>= 1)
                    if (GetPixel(pImg, j+l, i+k) != ((ptrn[k] & mask) != 0))
                        break;
                if (l < rx) // pattern not found
                    break;
            }
            if (k >= ry) //pattern found
            {
                pDst[*fCnt].x = j;
                pDst[*fCnt].y = i;
                ++(*fCnt);
            }
        }

Например, у меня есть такая двоичная строка: 1111 1111 1010 0000 0111 1111 1111 1111

и я ищу шаблон: 0100 0000

так, каков самый эффективный способ обнаружить такой образец в строке? Сдвигая биты шаблона и строки и чем XOR на них?

1 Ответ

0 голосов
/ 09 июня 2019

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

В качестве примера рассмотрим ваш паттерн 0100 0000.
Он должен быть найден в цепочке битов bs, и мы называем bs [i] i-ым битом bs.
Шаблон сопоставляется в данной позиции, если

bs [i] равно false (0)
и bs [i + 1] равно false (0)
и bs [i + 2] равно false (0)
и bs [i + 3] равно false (0)
и bs [i + 4] равно false (0)
и bs [i + 5] равно false (0)
и bs [i + 6] истинно (1)
и bs [i + 7] равно false (0)

Это можно преобразовать в логическое выражение
~ bs[i] & ~ bs[i+1] & ~ bs[i+2] & ~ bs[i+3] & ~ bs[i+4] & ~ bs[i+5] & bs[i+6] & ~ bs[i+7]
где есть логическое дополнение ~, когда в паттерне 0.

Это можно переписать со сдвигом вправо, чтобы получить выражение:
~ bs[i] & ~ ((bs>>)[i]) & ~ ((bs>>2)[i]) & ~ ((bs>>3)[i]) & ~ ((bs>>4)[i]) & ~ ((bs>>5)[i]) & ((bs>>6)[i]) & ~ ((bs>>7)[i])
где (bs>>k)[i] - это i-й бит bs, сдвинутый на k шагов вправо.

Из этого мы можем вывести следующий код C 

#include <stdio.h>

unsigned int findpattern(unsigned int bitstring, unsigned int pattern, 
                         unsigned int patternsize) {
  unsigned int match=~0;
  for(int i=0; i<patternsize; i++){
    match &= ((pattern&0x1)-1) ^ (bitstring);
    pattern >>=1;
    bitstring >>=1;
  }

  return match;
}

int main() {
  unsigned int bitstring=0xffa07fff;
  unsigned int pattern=0x40;

  unsigned int match=findpattern(bitstring,pattern,8);

  if (! match) 
    printf("No match for %x in %x\n",pattern, bitstring);
  else 
    printf("Matches found for %x in %x : %.8x\n", pattern, bitstring, match);
}

Функция findpattern возвращает int, где установлен i-й бит, если шаблон был найден в позиции i. Ни в одном шаблоне совпадение не найдено.

Идея состоит в том, чтобы просто сканировать последовательные биты шаблона по шаблону смещения вправо. В любое время, если установлен lsb, мы И получаем результат с правильно смещенной версией цепочки битов, а если lsb шаблона не установлен, мы И это с дополнением сдвинутой строки битов.
Дополнение выполняется путем ксоринга с (pattern&1)-1. Если lsb установлен, это xor с 1-1 = 0 (тождество), в противном случае xor с -1 (эквивалент ~).

Обратите внимание, что могут быть ложные совпадения в старших битах, поскольку цепочка битов каким-то образом искусственно расширена нулями (patternsize-1) слева, и это может создать проблемы с некоторой комбинацией цепочки битов / структуры. Это является причиной последней маски, которая очищает (pattersize-1) крайние левые биты совпадения, поскольку невозможно найти совпадение, кроме бита 32-шаблонного размера. По этой причине к match добавляется (2 ^ (32- (templatesize-1)), то есть число, состоящее из единиц, с нулями PatternSize-1 в крайних левых позициях.

...