最快的方式来扫描位stream中的位模式

我需要在比特stream中扫描16位字。 不保证在字节或字边界上alignment

什么是实现这个最快的方法? 有各种蛮力方法; 使用表和/或移位,但是有没有什么“bit twiddling shortcuts”,可以减less计算的数量,通过给yes / no /可能包含每个字节或单词的标志结果,因为它到达?

C代码,内部函数,x86机器代码都会很有趣。

我认为要预先把这个单词的所有值转换,并把它们放在16个整数中,所以你得到了一个这样的数组

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[16] = (unsigned int) (0xffff<<i); } 

然后对于每一个无符号短整型stream,将这个短整型和前一个短整型进行比较,并将该无符号整型与16个无符号整型进行比较。 如果它们中的任何一个匹配,就有一个。

所以基本上是这样的:

  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次!

如果两个字符{0,1}的字母表上的Knuth-Morris-Prattalgorithm和reinier的想法都不够快,则这是一个加快search速度32倍的技巧。

您可以首先使用一个有256个条目的表来检查您的位stream中的每个字节,如果它包含在您正在查找的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 

然后您可以使用位stream查找可能的匹配位置

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

由于256个表格条目中至多有8个不是零,平均而言,您只需要仔细观察每32个位置。 只有这个字节(结合前一个字节和后一个字节)才可以使用比特操作或一些屏蔽技术,如重新build议,以查看是否匹配。

该代码假定您使用小端字节顺序。 一个字节中的位的顺序也是一个问题(已经实现了CRC32校验和的所有人都知道)。

我的钱在Knuth-Morris-Pratt上 ,有两个字母的字母表。

我想build议一个解决scheme,使用3个大小为256的查找表。这对大码stream是有效的。 该解决scheme需要3个字节进行比较。 下图显示了3个字节的16位数据的所有可能的安排。 每个字节区域都以不同的颜色显示。

替代文字http://img70.imageshack.us/img70/8711/80541519.jpg

这里检查1到8将在第一个样本中被关注,在下一个样本中被检查9到16等等。 现在当我们正在寻找一个模式 ,我们会find这个模式的所有8种可能的安排(如下),并将存储在3个查找表(左,中,右)。

初始化查找表:

让我们举一个例子0111011101110111作为模式来查找。 现在考虑第四种安排。 左边部分是XXX01110 。 用左边的部分( XXX01110 )填充左边查找表的所有XXX0111000010000 。 1表示input模式的排列的起始位置。 因此,下面8个原始的左查表将被填充16( 00010000 )。

 00001110 00101110 01001110 01101110 10001110 10101110 11001110 11101110 

安排的中间部分将是11101110 。 这个索引(238)在中间查找表中的原始指向将被填充16( 00010000 )。

现在右边的部分将是111XXXXX 。 所有指数为111XXXXX (32 111XXXXX将被填充16( 00010000 )。

填充时不要在查表中覆盖元素。 而是做一个按位或操作来更新已经填充的原始数据。 在上面的例子中,第三排列的所有原料将按第七排列更新如下。

替代文字http://img527.imageshack.us/img527/8807/76437426.jpg

因此,Left查找表中的索引XX011101和中间查找表中的111XXXXX和右查找表中的111XXXXX将通过第七排列更新为00100010

search模式:

以三个字节为例。 查找计数如下所示: 左侧是查找表, 中间是中间查找表, 右侧是右侧查找表。

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

Count中的数字1表示采样中匹配模式的数量。

我可以给一些经过testing的示例代码。

初始化查找表:

  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; } 

search模式:

数据是stream缓冲区, 左边是查找表, 中间是查找表, 右边是查找表。

 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 ); } } 

局限性:

如果上面的循环放置在stream缓冲区的最后,它将无法检测到模式 。 下面的代码需要在循环后添加来克服这个限制。

 Count = Left[Data[StreamLength - 2]] & Middle[Data[StreamLength - 1]] & 128; if( Count ) { TotalCount += GetNumberOfOnes( Count ); } 

优点:

这个algorithm只需要N-1个逻辑步骤就可以在N个字节的数组中find一个模式 。 只有开销是填充在所有情况下始终不变的查找表。 所以这对search巨大的字节stream非常有效。

我会实现一个状态机16个州。

每个状态表示有多less接收的位符合该模式。 如果下一个接收到的位符合该模式的下一位,则机器进入下一个状态。 如果不是这种情况,则机器回到第一状态(或者如果模式的开始可以与较less数量的接收比特匹配,则返回到另一个状态)。

当机器达到最后状态时,这表明该模式已经在比特stream中被识别。

atomice的

  • 克努特莫里斯普拉特

直到我考虑卢克和MSalter的要求更详细的资料。

事实certificate,这些细节可能表明比KMP更快的方法。 KMP文章链接到

  • 博耶摩尔

对于search模式是“AAAAAA”的特定情况。 对于多重模式search,

  • 拉宾,卡普

可能是最合适的。

你可以在这里find进一步的介绍性讨论。

看起来像SIMD指令的一个很好的用法。 SSE2增加了一堆整数指令来同时处理多个整数,但是我不能想象很多的解决scheme,因为你的数据不会被alignment,所以不会有太多的位移。 这实际上听起来像一个FPGA应该做的事情。

我会做的是创build16个前缀和16个后缀。 然后为每个16位input块确定最长的后缀匹配。 如果下一个块具有长度(16-N)的前缀匹配,

后缀匹配实际上不是16比较。 但是,这需要根据模式字进行预先计算。 例如,如果模式字是101010101010101010,则可以先testing16位input块的最后一位。 如果该位为0,则只需要testing… 10101010即可。 如果最后一位是1,则需要testing… 1010101就足够了。 你有8个,总共1 + 8的比较。 如果模式字是1111111111110000,那么您仍然会testinginput的最后一位以进行后缀匹配。 如果这个位是1,你必须做12个后缀匹配(正则expression式:1 {1,12}),但是如果它是0,你只有4个可能的匹配(正则expression式1111 1111 1111 0 {1,4}),再次为一个平均9个testing。 添加16-N前缀匹配,你看到你只需要每16位块10次检查。

对于一个通用的非SIMDalgorithm,你不可能做得比这个更好:

 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 ); 

您可以使用快速傅里叶变换来处理极大的input(n值),以便在O(n log n)时间内find任何位模式。 计算位掩码与input的互相关性。 一个序列x和一个大小为n和n'的掩码y的相互关系由下式定义

 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)时间的FFT实现互相关。

我认为KMP有O(n + k)运行时,所以它击败了这一点。

也许你应该在你的比特stream中的vector(vec_str),在另一个vector(vec_pattern)模式中的stream,然后做类似下面的algorithm

 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++ 

(希望algorithm是正确的)

在大比特串中find匹配的一种快速方法是计算查找表,其显示给定input字节与模式匹配的位偏移量。 然后将三个连续的偏移匹配组合在一起,就可以得到一个显示哪个偏移量匹配整个模式的位向量。 例如,如果字节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个字节。 如果安装成本不是问题,那应该是一样快的。