Toa*_*oad 25
我认为prealc所有移位的单词值并将它们放入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[i] = (unsigned int) (0xffff<<i);
}
然后对于每个unsigned short,你离开流,做一个short和前一个short的int,并将unsigned int与16个unsigned 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次!
Who*_*ver 17
如果两个字符{0,1}的字母表上的Knuth-Morris-Pratt算法和reinier的想法都不够快,那么这是一个加速搜索速度32倍的技巧.
您可以首先使用包含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
}
}
由于256个表条目中最多有8个不为零,因此平均而言,您必须仔细查看每个第32个位置.只有这个字节(结合前一个字节和后一个字节),你才能使用位操作或一些掩盖技术,如reinier建议的那样,看是否有匹配.
该代码假定您使用小端字节顺序.字节中的位的顺序也可能是一个问题(已经实现CRC32校验和的每个人都知道).
Vad*_*ath 10
我想建议使用3个大小为256的查找表的解决方案.这对于大比特流是有效的.该解决方案在样本中占用3个字节用于比较.下图显示了3字节中16位数据的所有可能排列.每个字节区域都以不同的颜色显示.
替代文字http://img70.imageshack.us/img70/8711/80541519.jpg
在第一个样本中检查1到8,在下一个样本中检查9到16,依此类推.现在,当我们搜索模式时,我们将找到此模式的所有8种可能的排列(如下所示),并将存储在3个查找表(左,中,右)中.
初始化查找表:
让我们以一个例子0111011101110111作为模式来寻找.现在考虑第4种安排.左边的部分是XXX01110.用left part(XXX01110)填充左查找表的所有原始数据00010000.1表示输入模式的排列的起始位置.因此,跟随8个原始的左查找表将由16(00010000)填充.
00001110
00101110
01001110
01101110
10001110
10101110
11001110
11101110
安排的中间部分将是11101110.原始指向中间查找表中的索引(238)将由16(00010000)填充.
现在正确的安排部分将是111XXXXX.具有索引的所有原始(32个原始)111XXXXX将由16(00010000)填充.
我们不应该在填充时覆盖查找表中的元素.而是执行按位OR运算来更新已填充的原始数据.在上面的例子中,第3种排列所写的所有原始数据将按第7种排列更新如下.
替代文字http://img527.imageshack.us/img527/8807/76437426.jpg
因此,XX011101在左查找表和11101110中查找表以及111XXXXX右查找表中具有索引的原始数据将被更新为00100010第7个排列.
搜索模式:
取三个字节的样本.查找计数如下,其中左边是查找表,中间是中间查找表,右边是右查找表.
Count = Left[Byte0] & Middle[Byte1] & Right[Byte2];
Count中的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个字节数组中的模式.最初只需要填充查询表,这在所有情况下都是常量.因此,这对于搜索大量字节流非常有效.
小智 9
我的钱在Knuth-Morris-Pratt上,有两个字符的字母.
我将实现一个具有16个状态的状态机.
每个状态表示有多少接收位符合该模式.如果下一个接收的位符合模式的下一位,则机器进入下一个状态.如果不是这种情况,则机器退回到第一状态(或者如果模式的开始可以与较少数量的接收位匹配,则返回到另一状态).
当机器到达最后一个状态时,这表示已在比特流中识别出模式.