位并行算法与shift-and、shift-or算法

目录
[隐藏]

一、关于位并行算法

二十世纪90年代初,在Baez-aYates的博士论文11[1]中最早出现了采用位并行方法(BitParallelism)进行字符串匹配的思想,而后出现了经典的shift-or算法,以及又在此基础上进行了改进和提高的shift-and算法[2]shift-and算法又称为BAP(BitParallelAutomaton)算法。

       位并行算法用来模拟经典算法,是一种加速算法实现的手段。在搜索中,通过并行模拟,可以加快经典算法的运行速度。位并行算法非常适合模式串比较短的情况。

位并行利用了计算机机器字位运算的内在并行性,可以把多个值装入同一个长度为w的机器字内,然后只需一次运算就能更新所有值。利用位并行,一个算法所执行的运算次数最多能减少到原来的1/W,这里W是机器字的位数。

二、Shift-and算法

Shift-And算法是一种基于前缀的单字符串匹配算法,采用位运算。其算法思想比KMP简单得多。

在最简单的brute force算法中,在文本串的每个位置都要进行m(模式串长度)次比较,而SHIFT AND算法则是利用位运算提高这个过程。现在计算机的字长一般为3264位也开始流行了。一次比较的值为true or false,只需要一位即可存储,所以计算机可以在一次运算里完成 位长 次的比较。通过此思路可以把brute force的速度提高 位长 倍。

2.1 算法思想

Shift-And算法思想:设模式字符串为P,文本为text。它主要通过维护一个字符串集合DD中记录了P中所有与当前已读text的某个后缀相匹配的前缀),集合D中的每个字符串既是模式串p的前缀,同时也是已读入文本的后缀,每当从text中读入一个新的字符,算法立即利用位并行机制来更新集合D[3]

 我们可以这么具体理解:

  •  P长度为m,则集合D可表示为D = dmd1 而用D[j]代表dj
  • D[j]=1,当且仅当p1pj t1ti 的某个后缀;
  • D[m]=1时,就认为P已经于text匹配;
  • 当读入下一个字符 ti+1, 需要计算新的集合 D′;
  • 当且仅当D[j]=1并且  ti+1等于pj+1D'[j+1]=1。这是因为D[j]=1时有 p1pj t1ti 的一个后缀,而当ti+1 等于 pj+1可推出p1pj +1 t1ti+1 的一个后缀。这个集合可通过位运算来更新。

Shift-and算法首先建立一个数组B, 数组长度为字符集长度(例如A-Z的话数组B的长度为26),如果P的第j位等于c(P[j]=c),则将B中第j位置为1,否则为0

首先D=0m,对于每个新读入的文本字符ti+1,可以用如下公式对D进行更新:

公式(1)D’  ß ((D << 1) | 0m-11) & B[ti+1]       (1)

直观上来讲,左移位操作<<D’的第i+1位的值置为D的第i位。因为空字符串也是文本的后缀,所以D<<1需要在最低位与0m-11进行位或操作。因为要找到那些满足ti+1=pm+1的位置,所以需要再讲上面的结果与B[ti+1]进行位与操作。

当模式串的长度不超过几个机器字长时,公式(1)中的操作能够在常数时间内完成,这是shift-and算法的时间复杂度为O(n)[2]

举例说明:

假如P=announce,则构建b[]的过程:

B[a]=1; b[n]=10; b[n]=110; b[o]=1000; b=10000; b[n]=100110; b=1000000; b[e]=10000000;

初始状态:D=00000000

读入字符,通过公式(1)更改D结果。于是,D的每个时刻代表的字符集合,都是p的前缀,同时是已匹配文本的后缀。匹配过程如图2示例。

Shift-And算法
1 匹配示例

因为要预处理计算B,如果字符集很大的话,并不划算。如果m很长的话(大于机器字长),也很不方便。所以这种算法适用于字符集较小,模式串小于机器字长的情况。当然对于模式串较长的情况,也是比brute force要快的,只是逻辑上要复杂些。

2.2 Shift-And算法示例

Shift-And算法示例代码如下,这里假设字符集的大小为128

XML/HTML代码
  1. int shift_and(char * s, int len_s, char * p, int len_p)   
  2. {   
  3.     int B[128];   
  4.     memset(B, 0, sizeof(B));   
  5.     int i;   
  6.     for (i=0; i<len_p; i++)   
  7.         B[p] |= 1<<i;   
  8.     int D = 0;   
  9.     for (i=0; i<len_s; i++)   
  10.     {   
  11.         D = ((D<<1) | 1) & B[s];   
  12.         if (D & (1<<(len_p-1)))   
  13.         return i – len_p+1;   
  14.     }   
  15.     return -1;   
  16. }  

三、关于shift-or算法

Shift-Or算法是Shift-And的一种技巧性的改进实现,其算法思想跟Shift-And类似,只是在通过对位取反以去掉公式中的掩码0m-11,这样减少了位运算的次数,从而实现加速。Shift-Or作的修改是,使用反码表示B中的位掩码和位向量,即用0表示一个数在集合里,1表示不在,所以将

D = ((D<<1) | 1) & B[s];

修改为

D=D<<1 | B[s];

这样就省了一次位运算,当然BD的初始化的时候,也要作相应的修改。

3.1 一个shift-or算法示例程序

C++代码
  1. // 位并行算法Shift-Or算法   
  2. // 1、对模式串构造掩码表设模式串为abacb   
  3. //   a b a c b的掩码表为   
  4. // a 1 0 1 0 0   
  5. // b 0 1 0 0 1   
  6. // c 0 0 0 1 0   
  7. // 2、置D = 0, 对于新输入文本字符szMsg[j],   
  8. // 用公式D >> 1 | 2^(len-1) & Bset[Index]-> D   
  9. // if szMsg[j] = a or A Then Index = 0 Bset[Index] = 20   
  10. // 3、如果D&1==1当前的模式串与文本的以j个为结尾   
  11. // 的最后len个字符匹配.str[0]…str[len-1] = szMsg[j-len+1]..szMsg[j]   
  12.   
  13. #include <stdio.h>   
  14. #include <string.h>   
  15. #include <math.h>   
  16. const int MAX_LEN = 256;   
  17. // 创建位掩码集合   
  18. void CreateBset(char *str, int Bset[])   
  19. {   
  20.     int len = strlen(str);   
  21.     int i;   
  22.     int j;   
  23.     for (i=0; i<26; i++)// 行26 a到z   
  24.     {   
  25.          
  26.         for (j=0; j<len; j++)   
  27.         {   
  28.             if (i == (str[j] – 'A')%32)//大小写一样匹配字母对应数字映射   
  29.             {   
  30.                 Bset += (int)pow((double)2, (double)(len-1-j)); //出现的就是1   
  31.             }   
  32.         }   
  33.     }   
  34. return;   
  35. }   
  36. int main()   
  37. {   
  38.     char str[256] = {0};   
  39.     char szMsg[1024] = {0};   
  40.     //输入模式串   
  41.     gets(str);   
  42.     //输入文本   
  43.     gets(szMsg);   
  44.     int len = strlen(str);   
  45.     int Bset[26] = {0};   
  46.     int D = 0;//位掩码   
  47.     int Index;   
  48.     //创建掩码表集合   
  49.     CreateBset(str, Bset);   
  50.     int j = 0;   
  51.     int count = 0;   
  52.     while(j<strlen(szMsg))   
  53.     {   
  54.         D = (D >> 1) | (int)pow((double)2, (double)(len – 1));//右移1或上最高位为1   
  55.         Index = szMsg[j] – 'A';   
  56.         D = D & Bset[Index%32];//读入的文本的掩码集&上D   
  57.         if (1 == (D&1))//如果D的二进制第一位为1目标匹配   
  58.         {   
  59.             count++;//匹配的个数   
  60.         }   
  61.         j++;   
  62.     }   
  63.     printf("匹配的个数%dn", count);   
  64.     return 0;   
  65. }  

四、分析

Shift-andshift-or算法可看做是使用一个非确定性自动机对扫描文本的过程进行模拟。我们参考示例图2和图3进行分析,公式(1)对应于读入每个新字符时自动机的状态转移可如此来看:当文本字符与相应的箭头匹配时,当前状态转移到下一个状态。


2 自动机模拟匹配示意图

3 非确定性自动机模拟

参考文献

 

[1] R.A. Baeza-Yates. Efficient Text Searching. PhD thesis, Dept. of Computer Science, University of Waterloo, May 1989. Also as Research Report CS-89-17.

[2] S.WUU.Mnab.erFast text searhing allowing errors. Communieations of the ACM 19923510:83- 91.

[3] G. Navarro and M. Raffinot. Flexible Pattern Matching in Strings:Practical on-line search algorithms for texts and biological sequence[M].Cambridge: Cambridge University Press, 2002.

 

点赞 (1)
  1. 情侣对戒说道:

    好文章啊,就是看不懂

  2. 潮人蛤蟆镜说道:

    我猛点进来 沙发真的是我的了

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

Captcha Code