最快的方式来扫描位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 ）填充左边查找表的所有XXX01110 （ 00010000 。 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个字节。 如果安装成本不是问题，那应该是一样快的。
;){kind=link}
;){kind=link}