字符串匹配shiftand算法
令人驚嘆的Shift-And/Shift-Or
寫在前面：Shift-And/Shift-Or是如此令人驚嘆的算法，在KMP基礎(chǔ)上開始一段神奇之旅。
?
目的：以Shift-And算法為載體，試圖在減少思維斷層情況下學(xué)習(xí)作者算法思想。
?
目錄：
? ????1:主要思想
? ? ? ??2:算法介紹
???3:構(gòu)建輔助表B
? ?4:容器創(chuàng)建和更新
? ?5:過程展示
? ?6: Shift-And VS KMP，展示Shift-And令人驚嘆之處
? ?7:在KMP的基礎(chǔ)上，揭示Shift-And的神器：位并行（精髓）
第一步：主要思想（可以先看第3-5步，更容易理解）
???Shift-And算法和KMP算法一樣，是基于前綴來進(jìn)行字符串匹配。但是它的算法思想要比KMP思路簡單很多。它主要是維護(hù)了一個(gè)集合，該集合中保存的是所有既是模式串的前綴同時(shí)又是目標(biāo)串的后綴的字符串。每次讀入一個(gè)新的文本，本算法就利用位并行的方法更新該集合（神奇之處）。該集合用一個(gè)位掩碼D進(jìn)行表示：dm...d1表示（m表示的是模式串的大小）。
第二步：算法介紹（可以先看第3-5步，更容易理解）
? ??D的第j位為1的時(shí)候（此時(shí)成Dj是活動(dòng)的），表示模式串前綴的p1…pj同時(shí)也是目標(biāo)串t1…ti后綴.而當(dāng)dm是1的時(shí)候，表示有一個(gè)匹配成功。當(dāng)讀入目標(biāo)串的下一個(gè)字符t(i+1)的時(shí)候，需要對D進(jìn)行更新為D’當(dāng)且僅當(dāng)D的第j位是活動(dòng)的，并且t(i+1)和p(j+1)相同的時(shí)候，此時(shí)可以利用位并行的方法在常數(shù)時(shí)間內(nèi)對D進(jìn)行更新。
第三步：構(gòu)建輔助表B
???集合B記錄模式串中每一個(gè)字符位掩碼bm…b1.如果pj=x,則B[x]的第j為設(shè)為1.否則為0.
舉例1：模式串a(chǎn)nnounce共8位
?
?同理可以得到B（其中模式串中不包含的字符*設(shè)為00000000）
?
?第四步：容器創(chuàng)建和更新
???????對于容器D，初始化為00000000（0m?:前m位全為0）.表示當(dāng)前還沒有即使模式串前綴又是目標(biāo)串后綴。
?
???????當(dāng)讀入一個(gè)新的目標(biāo)串字符t(i+1)，可以以如下公式進(jìn)行更新。
?第五步：過程展示
???????下面是整個(gè)過程：目標(biāo)串是’annual_announce’?模式串announce
? ??其實(shí)這個(gè)例子個(gè)人覺得并不是很理想，雖然它能說明情況，但是很難從這個(gè)例子的過程中體會(huì)到這個(gè)過程奇妙發(fā)生的根本所在。
?
例子2：
?
目標(biāo)串是cbcbcbaefd??模式串是cbcba
?
建表B：
?如果你看明白了，就會(huì)發(fā)現(xiàn)上述做法真的很奇妙。
第5)步中，讀取了c，但是模式串中的確實(shí)a，在沒有讀取c之前，結(jié)果是01010，這個(gè)的意思是模式串前4個(gè)字符前兩個(gè)字符cb和前4個(gè)字符cbcb既是模式串的前綴，同時(shí)又是目標(biāo)串的后綴。當(dāng)讀入第5個(gè)字符c后，經(jīng)過更新D后變成了00101，這個(gè)結(jié)果表示前5個(gè)字符中，只有第1個(gè)字符c和前3個(gè)字符cbc既是模式串的前綴又是目標(biāo)串的后綴。
?
這就是它的厲害之處，讀入一個(gè)新的字符之后，經(jīng)過這樣3個(gè)步驟，就計(jì)算出來當(dāng)前模式串前5個(gè)字符中所有的前綴（同時(shí)是目標(biāo)串的后綴）。
?
也許這樣還表現(xiàn)不太明顯，但是如果你很熟悉KMP算法，因?yàn)?/span>KMP的貢獻(xiàn)在于它并不進(jìn)行回溯同時(shí)很巧妙的利用迭代改變指針j。如果說kmp巧妙，它確實(shí)是，但是和Shift-And相比，真是小巫見大巫。因?yàn)?/span>kmp是用迭代，有可能需要迭代很多次，才能達(dá)到效果，此處只是一次位并行操作，就達(dá)到了kmp的效果。效率大大的提高。
?
第六步：Shift-And ?VS ?KMP，展示Shift-And令人驚嘆之處
?
KMP算法的精髓在于不回溯并采用巧妙的迭代方法得到next數(shù)組，將時(shí)間復(fù)雜度理論上降到了o(n)。
?
如果想清楚了解KMP，可以參考
?
http://wlh0706-163-com.iteye.com/blog/1843923
?
以下面這個(gè)案例再次進(jìn)行分析：
?
?
?當(dāng)?shù)?/span>26個(gè)字符，c和f匹配失敗的時(shí)候，kmp使用的方法是：找到了模式串中前25個(gè)字符的所有的既是模式串的前綴同時(shí)又是目標(biāo)串的后綴。
?
?
?
?找到了這4對前綴?a,aca,acabaca,acabacabaca.
?
??上圖中第1步：由于最大的前綴acabacabaca的后面一個(gè)字符t和第26個(gè)字符c并不匹配，執(zhí)行第2步。
?
?
上圖中第2步：由于第二大的前綴acabaca（同時(shí)是最大前綴acabacabaca的最大前綴，這是kmp算法實(shí)施迭代技巧的的根本性質(zhì)）后面的一個(gè)字符b和第26個(gè)字符c并不匹配，執(zhí)行第3步。
?
上圖中第3步同樣面臨這c和b不等的情況，執(zhí)行第4步。
?
上圖中第4步：由于前綴a后一個(gè)字符c和第26個(gè)字符相同，此時(shí)指向目標(biāo)串的指針i= 26和執(zhí)行模式串的指針j由原來的26經(jīng)過一系列改變（12，8，2）最終為2.?然后i++和j++開始匹配下一個(gè)字符.
?
代碼：
?（本段代碼在上篇文章中有）
?
? ??然而在看一下shift-and算法是如何找到這個(gè)kmp進(jìn)行了4次迭代才找到的第2位的c的。
?
此例中：
B[c] =
當(dāng)比較完第25個(gè)字符之后
D? = ?
(這個(gè)是根據(jù)D的定義結(jié)合上述圖片展示的4對前綴寫出來的)
運(yùn)算過程：
?只是一次運(yùn)算就計(jì)算出了kmp中需要4次迭代才能計(jì)算出來的結(jié)果。
那么Shift-And是如何需要1次就做到的KMP?算法4次才能做到的效果呢？下面來演示這個(gè)過程。
第七步:在KMP的基礎(chǔ)上，揭示Shift-And的神器：位并行（精髓）
?
?
? ? ??再來看張圖：其實(shí)這4步操作，目的只有一個(gè)，就是拿目標(biāo)串的c和模式串的4對前綴的后一個(gè)字符相比較（其他字符都不需要比較）。即c和t，b，b，c相比較。
而t,b,b,c的位置是什么？12，8，4，2。
再看看Shift-And中的D左移一位之后是什么呢？
?? 你可以清楚的看到上面的數(shù)字，奇妙之處就在這里。
?（注：26實(shí)際上已經(jīng)比較過了，就是第1次比較c和f）
這個(gè)只是找到了要和c比較的位置，下一步就是比較這些位置是不是c，所以才有了shift-And算法中第三步：相與操作。即從容器B中提取出來c出現(xiàn)的所有的位置即位掩碼B[c]
? ? ??其實(shí)這里為什么能用相與操作呢？如果想要深入理解相與的妙處，可以先看一個(gè)簡單的案例
http://wlh0706-163-com.iteye.com/blog/1393631??這里的c和12，8，4，2這些位置的比較實(shí)際相同或者不相同的比較，而這個(gè)正式‘與’的本質(zhì)特征。
???走到這一步完了嗎？當(dāng)然還沒有，不過已經(jīng)接近重點(diǎn)了。那就是Shift-And的第2步？加1是為了什么？
? ?其實(shí)這個(gè)沒有什么神秘之處，只是如果你對kmp不是特別熟，即便是很熟悉也有可能會(huì)忘記。就是在這幅圖中
?
? ??我們幸運(yùn)的是第4步發(fā)現(xiàn)了相同的c，但是如果沒有發(fā)現(xiàn)呢？例如目標(biāo)串的第26個(gè)字符不是c而是a呢？我們就會(huì)有第5步，和它比較的是誰呢？是第1個(gè)字符。這個(gè)意思是第4步失敗，將要尋找c前面即a的最大前綴再加1的位置（和前3次一樣）而我們默認(rèn)a的最大前綴+1等于0+1=1.也就是很多其他博客中引用原作者說的那句話：空字符串也是目標(biāo)串的后綴。a的前綴還有一個(gè)空字符。實(shí)際上本例也能看出來，第目標(biāo)串第26個(gè)字符是a，顯然有和模式串第一個(gè)字符a比較的需要。
?
???????現(xiàn)在如果看懂了整個(gè)過程，可以去分析第一步和第二步所說是如此經(jīng)典。
???????不得不說，Shift-And算法是看透了KMP基于前綴匹配的本質(zhì)特征，即比較的時(shí)候?qū)嶋H上是非黑即白的比較，使用01這種方法實(shí)在令人佩服。這個(gè)算法效率一般是KMP的2倍以上。當(dāng)然，基于位并行操作實(shí)際和機(jī)器字長有關(guān)系，比如32位限制或者其他，但是它在絕大部分機(jī)器上都能運(yùn)行，除非機(jī)器字長為8（這種機(jī)器應(yīng)該年齡很大了吧..），你所查詢的是大于8位。
???????至于Shift-Or，它所用的原理是一樣的，只不過更加富有技巧性，使用了反碼和取反等操作，加速D’的計(jì)算。有興趣可以自行研究。如果看懂本例，在用點(diǎn)心相信看懂Shift-Or沒什么問題。
? ? ? ??感謝Shift-And算法帶我們走了一段神奇之旅！！！Wonderful！！
總結(jié)
以上是生活随笔為你收集整理的字符串匹配shiftand算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 寿司加盟多少钱啊？
- 下一篇： ccf Markdown