令人惊叹的Shift-And/Shift-Or

写在前面：Shift-And/Shift-Or是如此令人惊叹的算法，在KMP基础上开始一段神奇之旅。

 

目的：以Shift-And算法为载体，试图在减少思维断层情况下学习作者算法思想。

 

目录：

      1:主要思想

        2:算法介绍

   3:构建辅助表B

   4:容器创建和更新

   5:过程展示

   6: Shift-And VS KMP，展示Shift-And令人惊叹之处

   7:在KMP的基础上，揭示Shift-And的神器：位并行（精髓）

第一步：主要思想（可以先看第3-5步，更容易理解）

   Shift-And算法和KMP算法一样，是基于前缀来进行字符串匹配。但是它的算法思想要比KMP思路简单很多。它主要是维护了一个集合，该集合中保存的是所有既是模式串的前缀同时又是目标串的后缀的字符串。每次读入一个新的文本，本算法就利用位并行的方法更新该集合（神奇之处）。该集合用一个位掩码D进行表示：dm...d1表示（m表示的是模式串的大小）。

第二步：算法介绍（可以先看第3-5步，更容易理解）

    D的第j位为1的时候（此时成Dj是活动的），表示模式串前缀的p1…pj同时也是目标串t1…ti后缀.而当dm是1的时候，表示有一个匹配成功。当读入目标串的下一个字符t(i+1)的时候，需要对D进行更新为D’当且仅当D的第j位是活动的，并且t(i+1)和p(j+1)相同的时候，此时可以利用位并行的方法在常数时间内对D进行更新。

第三步：构建辅助表B

   集合B记录模式串中每一个字符位掩码bm…b1.如果pj=x,则B[x]的第j为设为1.否则为0.

举例1：模式串announce共8位

 

 同理可以得到B（其中模式串中不包含的字符*设为00000000）

 

 第四步：容器创建和更新

       对于容器D，初始化为00000000（0^m :前m位全为0）.表示当前还没有即使模式串前缀又是目标串后缀。

 

       当读入一个新的目标串字符t(i+1)，可以以如下公式进行更新。

 第五步：过程展示

       下面是整个过程：目标串是’annual_announce’ 模式串announce

    其实这个例子个人觉得并不是很理想，虽然它能说明情况，但是很难从这个例子的过程中体会到这个过程奇妙发生的根本所在。

 

例子2：

 

目标串是cbcbcbaefd  模式串是cbcba

 

建表B：


 如果你看明白了，就会发现上述做法真的很奇妙。

第5)步中，读取了c，但是模式串中的确实a，在没有读取c之前，结果是01010，这个的意思是模式串前4个字符前两个字符cb和前4个字符cbcb既是模式串的前缀，同时又是目标串的后缀。当读入第5个字符c后，经过更新D后变成了00101，这个结果表示前5个字符中，只有第1个字符c和前3个字符cbc既是模式串的前缀又是目标串的后缀。

 

这就是它的厉害之处，读入一个新的字符之后，经过这样3个步骤，就计算出来当前模式串前5个字符中所有的前缀（同时是目标串的后缀）。

 

也许这样还表现不太明显，但是如果你很熟悉KMP算法，因为KMP的贡献在于它并不进行回溯同时很巧妙的利用迭代改变指针j。如果说kmp巧妙，它确实是，但是和Shift-And相比，真是小巫见大巫。因为kmp是用迭代，有可能需要迭代很多次，才能达到效果，此处只是一次位并行操作，就达到了kmp的效果。效率大大的提高。

 

第六步：Shift-And  VS  KMP，展示Shift-And令人惊叹之处

 

KMP算法的精髓在于不回溯并采用巧妙的迭代方法得到next数组，将时间复杂度理论上降到了o(n)。

 

如果想清楚了解KMP，可以参考

 

http://wlh0706-163-com.iteye.com/blog/1843923

 

以下面这个案例再次进行分析：

 

 

 当第26个字符，c和f匹配失败的时候，kmp使用的方法是：找到了模式串中前25个字符的所有的既是模式串的前缀同时又是目标串的后缀。

 

 

 

 找到了这4对前缀 a,aca,acabaca,acabacabaca.

 

  上图中第1步：由于最大的前缀acabacabaca的后面一个字符t和第26个字符c并不匹配，执行第2步。

 

 

上图中第2步：由于第二大的前缀acabaca（同时是最大前缀acabacabaca的最大前缀，这是kmp算法实施迭代技巧的的根本性质）后面的一个字符b和第26个字符c并不匹配，执行第3步。

 

上图中第3步同样面临这c和b不等的情况，执行第4步。

 

上图中第4步：由于前缀a后一个字符c和第26个字符相同，此时指向目标串的指针i= 26和执行模式串的指针j由原来的26经过一系列改变（12，8，2）最终为2. 然后i++和j++开始匹配下一个字符.

 

代码：

 （本段代码在上篇文章中有）

 

    然而在看一下shift-and算法是如何找到这个kmp进行了4次迭代才找到的第2位的c的。

 

此例中：

B[c] =

当比较完第25个字符之后

D  =  

(这个是根据D的定义结合上述图片展示的4对前缀写出来的)

运算过程：

 只是一次运算就计算出了kmp中需要4次迭代才能计算出来的结果。

那么Shift-And是如何需要1次就做到的KMP 算法4次才能做到的效果呢？下面来演示这个过程。

第七步:在KMP的基础上，揭示Shift-And的神器：位并行（精髓）

 

 

      再来看张图：其实这4步操作，目的只有一个，就是拿目标串的c和模式串的4对前缀的后一个字符相比较（其他字符都不需要比较）。即c和t，b，b，c相比较。

而t,b,b,c的位置是什么？12，8，4，2。

再看看Shift-And中的D左移一位之后是什么呢？

   你可以清楚的看到上面的数字，奇妙之处就在这里。

 （注：26实际上已经比较过了，就是第1次比较c和f）

这个只是找到了要和c比较的位置，下一步就是比较这些位置是不是c，所以才有了shift-And算法中第三步：相与操作。即从容器B中提取出来c出现的所有的位置即位掩码B[c]

      其实这里为什么能用相与操作呢？如果想要深入理解相与的妙处，可以先看一个简单的案例

http://wlh0706-163-com.iteye.com/blog/1393631  这里的c和12，8，4，2这些位置的比较实际相同或者不相同的比较，而这个正式‘与’的本质特征。

   走到这一步完了吗？当然还没有，不过已经接近重点了。那就是Shift-And的第2步？加1是为了什么？

   其实这个没有什么神秘之处，只是如果你对kmp不是特别熟，即便是很熟悉也有可能会忘记。就是在这幅图中

 

    我们幸运的是第4步发现了相同的c，但是如果没有发现呢？例如目标串的第26个字符不是c而是a呢？我们就会有第5步，和它比较的是谁呢？是第1个字符。这个意思是第4步失败，将要寻找c前面即a的最大前缀再加1的位置（和前3次一样）而我们默认a的最大前缀+1等于0+1=1.也就是很多其他博客中引用原作者说的那句话：空字符串也是目标串的后缀。a的前缀还有一个空字符。实际上本例也能看出来，第目标串第26个字符是a，显然有和模式串第一个字符a比较的需要。

 

       现在如果看懂了整个过程，可以去分析第一步和第二步所说是如此经典。

       不得不说，Shift-And算法是看透了KMP基于前缀匹配的本质特征，即比较的时候实际上是非黑即白的比较，使用01这种方法实在令人佩服。这个算法效率一般是KMP的2倍以上。当然，基于位并行操作实际和机器字长有关系，比如32位限制或者其他，但是它在绝大部分机器上都能运行，除非机器字长为8（这种机器应该年龄很大了吧..），你所查询的是大于8位。

       至于Shift-Or，它所用的原理是一样的，只不过更加富有技巧性，使用了反码和取反等操作，加速D’的计算。有兴趣可以自行研究。如果看懂本例，在用点心相信看懂Shift-Or没什么问题。

        感谢Shift-And算法带我们走了一段神奇之旅！！！Wonderful！！