Самый быстрый способ просканировать для комбинации двоичных разрядов в потоке битов

12 ответов

Иногда полезно использовать простую грубую силу.

I подумайте, предварительно вычислите все сдвинутые значения слова и поместите их в 16 целых Итак, у вас есть такой массив (предполагая, что int вдвое шире, чем short )

 unsigned short pattern = 1234;
 unsigned int preShifts[16];
 unsigned int masks[16];
 int i;
 for(i=0; i<16; i++)
 {
      preShifts[i] = (unsigned int)(pattern<<i);  //gets promoted to int
      masks[i] = (unsigned int) (0xffff<<i);
 }

, а затем для каждого беззнакового короткого замыкания, выходящего из потока, сделайте int из этого short и предыдущий short и сравните это unsigned int с 16 беззнаковыми int. Если какой-либо из них совпадает, вы его получили.

Итак, примерно так:

  int numMatch(unsigned short curWord, unsigned short prevWord)
  {
       int numHits = 0;
       int combinedWords = (prevWord<<16) + curWord;

       int i=0;
       for(i=0; i<16; i++)
       {
             if((combinedWords & masks[i]) == preShifsts[i]) numHits++;
       }
       return numHits;
  }

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

например, 32 бита 0, а образец, который вы хотите обнаружить, - это 16 0, тогда это будет означать, что образец обнаружен 16 раз!


Затраты времени на это, предполагая, что он компилируется примерно так, как написано, составляют 16 проверок на входное слово. Для каждого входного бита выполняется одно & и == , а также переход или другое условное приращение. А также поиск в таблице маски для каждого бита.

Поиск в таблице не нужен; вместо этого сдвигая вправо вместе , мы получаем значительно более эффективный asm, как показано в другом ответе , который также показывает, как векторизовать это с помощью SIMD на x86.

25
ответ дан 27 November 2019 в 04:23
поделиться

Вы можете использовать быстрое преобразование Фурье для очень больших входных данных (значение n), чтобы найти любой битовый шаблон за время O (n log n). Вычислите взаимную корреляцию битовой маски с вводом. Взаимная корреляция последовательности x и маски y с размером n и n 'соответственно определяется

R(m) = sum  _ k = 0 ^ n' x_{k+m} y_k

, тогда вхождения вашего битового шаблона, который точно соответствует маске, где R (m) = Y, где Y - сумма одного в вашей битовой маске.

Итак, если вы пытаетесь сопоставить битовую комбинацию

[0 0 1 0 1 0]

в

[ 1 1 0 0 1 0 1 0 0 0 1 0 1 0 1]

, вы должны использовать маску

[-1 -1  1 -1  1 -1]

, -1 в маске гарантируют, что эти места должны быть равны 0.

Вы можете реализовать взаимная корреляция с использованием БПФ за время O (n log n).

Я думаю, что KMP имеет время выполнения O (n + k), поэтому он превосходит это.

3
ответ дан 27 November 2019 в 04:23
поделиться

Я бы создал 16 префиксов и 16 суффиксов. Затем для каждого 16-битного входного фрагмента определите самый длинный совпадение суффикса. У вас есть совпадение, если у следующего фрагмента есть совпадение по префиксу длины (16-N)

Совпадение суффикса фактически не означает 16 сравнений. Однако для этого требуется предварительный расчет на основе слова-шаблона. Например, если шаблонное слово - 101010101010101010, вы можете сначала проверить последний бит вашего 16-битного входного блока. Если этот бит равен 0, вам нужно только проверить ... 10101010. Если последний бит равен 1, вам нужно протестировать ... 1010101. У вас есть 8 штук каждого, всего 1 + 8 сравнений. Если шаблонное слово 1111111111110000, вы все равно протестируете последний бит вашего ввода на совпадение суффикса. Если этот бит равен 1, вам нужно выполнить 12 совпадений суффиксов (регулярное выражение: 1 {1,12}), но если это ' s 0 у вас есть только 4 возможных совпадения (регулярное выражение 1111 1111 1111 0 {1,4}), опять же в среднем для 9 тестов. Добавьте совпадение префикса 16-N , и вы увидите, что вам нужно только 10 проверок на 16-битный фрагмент.

3
ответ дан 27 November 2019 в 04:23
поделиться

Atomice

выглядел хорошо, пока я не рассмотрел запросы Люка и М.С. Сальтера о дополнительной информации о деталях.

Оказалось, что детали могут указывать на более быстрый подход. чем КМП. В статье KMP имеется ссылка на

для конкретного случая, когда шаблон поиска - «AAAAAA». Для поиска по множеству шаблонов наиболее подходящим может быть

.

Дальнейшее вводное обсуждение можно найти здесь .

4
ответ дан 27 November 2019 в 04:23
поделиться

Мои деньги на Knuth-Morris-Pratt с алфавитом из двух символов.

9
ответ дан 27 November 2019 в 04:23
поделиться

Может быть, вам следует выполнить потоковую передачу в своем битовом потоке в векторе (vec_str), передать поток в своем шаблоне в другом векторе (vec_pattern), а затем выполнить что-то вроде алгоритма ниже

i=0
while i<vec_pattern.length
    j=0
    while j<vec_str.length
            if (vec_str[j] xor vec_pattern[i])
                i=0
                j++

(надеюсь, что алгоритм правильно)

2
ответ дан 27 November 2019 в 04:23
поделиться

Похоже, хорошее применение для инструкций SIMD. SSE2 добавил кучу целочисленных инструкций для одновременной обработки нескольких целых чисел, но я не могу представить себе много решений для этого, которые не предполагали бы много битовых сдвигов, поскольку ваши данные не будут выровнены. На самом деле это похоже на то, что должна делать ПЛИС.

3
ответ дан 27 November 2019 в 04:23
поделиться

Я бы реализовал конечный автомат с 16 состояниями.

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

Когда машина достигает последнего состояния, это указывает, что шаблон был идентифицирован в потоке битов.

7
ответ дан 27 November 2019 в 04:23
поделиться

Для универсального алгоритма без SIMD вы вряд ли сможете добиться большего успеха, чем что-то вроде этого:

unsigned int const pattern = pattern to search for
unsigned int accumulator = first three input bytes

do
{
  bool const found = ( ((accumulator   ) & ((1<<16)-1)) == pattern )
                   | ( ((accumulator>>1) & ((1<<16)-1)) == pattern );
                   | ( ((accumulator>>2) & ((1<<16)-1)) == pattern );
                   | ( ((accumulator>>3) & ((1<<16)-1)) == pattern );
                   | ( ((accumulator>>4) & ((1<<16)-1)) == pattern );
                   | ( ((accumulator>>5) & ((1<<16)-1)) == pattern );
                   | ( ((accumulator>>6) & ((1<<16)-1)) == pattern );
                   | ( ((accumulator>>7) & ((1<<16)-1)) == pattern );
  if( found ) { /* pattern found */ }
  accumulator >>= 8;

  unsigned int const data = next input byte
  accumulator |= (data<<8);
} while( there is input data left );
3
ответ дан 27 November 2019 в 04:23
поделиться

Вот трюк для ускорения поиска в 32 раза, если ни алгоритм Кнута-Морриса-Пратта на алфавите из двух символов {0, 1}, ни идея Райнира не работают быстро довольно.

Сначала вы можете использовать таблицу с 256 записями, чтобы проверить, содержится ли каждый байт в вашем битовом потоке в 16-битном слове, которое вы ищете. Таблица, которую вы получаете с помощью

unsigned char table[256];
for (int i=0; i<256; i++)
  table[i] = 0; // initialize with false
for (i=0; i<8; i++)
  table[(word >> i) & 0xff] = 1; // mark contained bytes with true

Затем вы можете найти возможные позиции для совпадений в битовом потоке, используя

for (i=0; i<length; i++) {
  if (table[bitstream[i]]) {
    // here comes the code which checks if there is really a match
  }
}

Поскольку не более 8 из 256 записей таблицы не равны нулю, в среднем вам нужно внимательно смотреть только на каждую 32-ю запись. должность. Только для этого байта (в сочетании с байтами до и после) вы должны затем использовать битовые операции или некоторые методы маскирования, предложенные Райниером, чтобы увидеть, есть ли совпадение.

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

17
ответ дан 27 November 2019 в 04:23
поделиться

Я хотел бы предложить решение, использующее 3 таблицы поиска размером 256. Это было бы эффективно для больших битовых потоков. Это решение занимает 3 байта в образце для сравнения. На следующем рисунке показаны все возможные варианты размещения 16-битных данных в 3 байтах. Каждая байтовая область показана разным цветом.

alt text http://img70.imageshack.us/img70/8711/80541519.jpg

Здесь проверка от 1 до 8 будет выполняться в первом примере и от 9 до 16 в следующем примере и так далее. Теперь, когда мы ищем Pattern , мы найдем все 8 возможных вариантов (как показано ниже) этого Pattern и сохраним их в 3 справочных таблицах (слева, посередине и справа) .

Инициализация таблиц поиска:

Давайте возьмем пример 0111011101110111 в качестве шаблона для поиска. Теперь рассмотрим 4-е расположение. Левая часть будет XXX01110 . Заполните все строки левой таблицы поиска, указывающие левой частью ( XXX01110 ), с помощью 00010000 . 1 указывает начальную позицию расположения входа Pattern . Таким образом, следующие 8 рядов левой справочной таблицы будут заполнены 16 ( 00010000 ).

00001110
00101110
01001110
01101110
10001110
10101110
11001110
11101110

Средняя часть расположения будет 11101110 . Необработанное указание этим индексом (238) в средней таблице поиска будет заполнено 16 ( 00010000 ).

Теперь правая часть расположения будет 111XXXXX . Все строки (32 строки) с индексом 111XXXXX будут заполнены на 16 ( 00010000 ).

Мы не должны перезаписывать элементы в таблице поиска во время заполнения. Вместо этого выполните операцию побитового ИЛИ, чтобы обновить уже заполненный необработанный файл. В приведенном выше примере все необработанные данные, записанные с помощью 3-го порядка, будут обновлены с помощью 7-го порядка следующим образом.

alt text

Таким образом, необработанные данные с индексом XX011101 в левой таблице поиска и 11101110 в средней таблице поиска и 111XXXXX в правой таблице поиска будет обновлен до 00100010 по седьмому порядку.

Шаблон поиска:

Возьмите образец из трех байтов. Найдите Count следующим образом, где Left - это левая таблица поиска, Средняя - средняя таблица поиска, а Right - правая таблица поиска.

Count = Left[Byte0] & Middle[Byte1] & Right[Byte2];

Число 1 в Счетчик дает количество совпадающих Образца в взятой выборке.

Я могу привести пример кода, который был протестирован.

Инициализация таблицы поиска:

    for( RightShift = 0; RightShift < 8; RightShift++ )
    {
        LeftShift = 8 - RightShift;

        Starting = 128 >> RightShift;

        Byte = MSB >> RightShift;

        Count = 0xFF >> LeftShift;

        for( i = 0; i <= Count; i++ )
        {
            Index = ( i << LeftShift ) | Byte;

            Left[Index] |= Starting;
        }

        Byte = LSB << LeftShift;

        Count = 0xFF >> RightShift;

        for( i = 0; i <= Count; i++ )
        {
            Index = i | Byte;

            Right[Index] |= Starting;
        }

        Index = ( unsigned char )(( Pattern >> RightShift ) & 0xFF );

        Middle[Index] |= Starting;
    }

Шаблон поиска:

Данные - буфер потока, Левый - левая таблица поиска, Средний - средняя таблица поиска и ] Справа находится правая таблица поиска.

for( int Index = 1; Index < ( StreamLength - 1); Index++ )
{
    Count = Left[Data[Index - 1]] & Middle[Data[Index]] & Right[Data[Index + 1]];

    if( Count )
    {
        TotalCount += GetNumberOfOnes( Count );
    }
}

Ограничение:

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

Count = Left[Data[StreamLength - 2]] & Middle[Data[StreamLength - 1]] & 128;

if( Count )
{
    TotalCount += GetNumberOfOnes( Count );
}

Преимущество:

Этот алгоритм принимает только N-1 логических шагов, чтобы найти Образец в массиве N байт. Только накладные расходы заключаются в первоначальном заполнении справочных таблиц, что является постоянным во всех случаях. Так что это будет очень эффективно для поиска огромных байтовых потоков.

[1 1140390] Шаблон , если он размещен в самом конце буфера потока. В следующем коде необходимо добавить цикл после, чтобы преодолеть это ограничение.

Count = Left[Data[StreamLength - 2]] & Middle[Data[StreamLength - 1]] & 128;

if( Count )
{
    TotalCount += GetNumberOfOnes( Count );
}

Преимущество:

Этот алгоритм принимает только N-1 логических шагов, чтобы найти Образец в массиве N байт. Только накладные расходы заключаются в первоначальном заполнении справочных таблиц, которые являются постоянными во всех случаях. Так что это будет очень эффективно для поиска огромных байтовых потоков.

Слева - это левая таблица поиска, Средняя - средняя таблица поиска и Правая - правая таблица поиска.

for( int Index = 1; Index < ( StreamLength - 1); Index++ )
{
    Count = Left[Data[Index - 1]] & Middle[Data[Index]] & Right[Data[Index + 1]];

    if( Count )
    {
        TotalCount += GetNumberOfOnes( Count );
    }
}

Ограничение:

Цикл выше не может обнаружить Шаблон , если он размещен в самом конце буфера потока. В следующем коде необходимо добавить цикл после, чтобы преодолеть это ограничение.

Count = Left[Data[StreamLength - 2]] & Middle[Data[StreamLength - 1]] & 128;

if( Count )
{
    TotalCount += GetNumberOfOnes( Count );
}

Преимущество:

Этот алгоритм принимает только N-1 логических шагов, чтобы найти Образец в массиве N байт. Только накладные расходы заключаются в первоначальном заполнении справочных таблиц, которые являются постоянными во всех случаях. Так что это будет очень эффективно для поиска больших потоков байтов.

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

Count = Left[Data[StreamLength - 2]] & Middle[Data[StreamLength - 1]] & 128;

if( Count )
{
    TotalCount += GetNumberOfOnes( Count );
}

Преимущество:

Этот алгоритм принимает только N-1 логических шагов, чтобы найти Образец в массиве N байт. Только накладные расходы заключаются в первоначальном заполнении справочных таблиц, что является постоянным во всех случаях. Так что это будет очень эффективно для поиска больших потоков байтов.

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

Count = Left[Data[StreamLength - 2]] & Middle[Data[StreamLength - 1]] & 128;

if( Count )
{
    TotalCount += GetNumberOfOnes( Count );
}

Преимущество:

Этот алгоритм принимает только N-1 логических шагов, чтобы найти Образец в массиве N байт. Только накладные расходы заключаются в первоначальном заполнении справочных таблиц, которые являются постоянными во всех случаях. Так что это будет очень эффективно для поиска огромных байтовых потоков.

10
ответ дан 27 November 2019 в 04:23
поделиться

Быстрый способ найти совпадения в больших цепочках битов - это вычислить таблицу поиска, которая показывает смещения битов, в которых данный входной байт соответствует шаблону. Затем, комбинируя три последовательных совпадения смещения вместе, вы можете получить битовый вектор, который показывает, какие смещения соответствуют всему шаблону. Например, если байт x соответствует первым 3 битам шаблона, байт x + 1 соответствует битам 3..11, а байт x + 2 соответствует битам 11..16, то есть совпадение в байте x + 5 бит.

Вот пример кода, который делает это, накапливая результаты для двух байтов за раз:

void find_matches(unsigned char* sequence, int n_sequence, unsigned short pattern) {
    if (n_sequence < 2)
        return; // 0 and 1 byte bitstring can't match a short

    // Calculate a lookup table that shows for each byte at what bit offsets
    // the pattern could match.
    unsigned int match_offsets[256];
    for (unsigned int in_byte = 0; in_byte < 256; in_byte++) {
        match_offsets[in_byte] = 0xFF;
        for (int bit = 0; bit < 24; bit++) {
            match_offsets[in_byte] <<= 1;
            unsigned int mask = (0xFF0000 >> bit) & 0xFFFF;
            unsigned int match_location = (in_byte << 16) >> bit;
            match_offsets[in_byte] |= !((match_location ^ pattern) & mask);
        }
    }

    // Go through the input 2 bytes at a time, looking up where they match and
    // anding together the matches offsetted by one byte. Each bit offset then
    // shows if the input sequence is consistent with the pattern matching at
    // that position. This is anded together with the large offsets of the next
    // result to get a single match over 3 bytes.
    unsigned int curr, next;
    curr = 0;
    for (int pos = 0; pos < n_sequence-1; pos+=2) {
        next = ((match_offsets[sequence[pos]] << 8) | 0xFF) & match_offsets[sequence[pos+1]];
        unsigned short match = curr & (next >> 16);
        if (match)
            output_match(pos, match);
        curr = next;
    }
    // Handle the possible odd byte at the end
    if (n_sequence & 1) {
        next = (match_offsets[sequence[n_sequence-1]] << 8) | 0xFF;
        unsigned short match = curr & (next >> 16);
        if (match)
            output_match(n_sequence-1, match);
    }
}

void output_match(int pos, unsigned short match) {
    for (int bit = 15; bit >= 0; bit--) {
        if (match & 1) {
            printf("Bitstring match at byte %d bit %d\n", (pos-2) + bit/8, bit % 8);
        }
        match >>= 1;
    }
}

Основной цикл этого состоит из 18 инструкций и обрабатывает 2 байта за итерацию. Если стоимость установки не является проблемой, это должно быть как можно быстрее.

1
ответ дан 27 November 2019 в 04:23
поделиться
Другие вопросы по тегам:

Похожие вопросы: