【字符串系列】字符串匹配中的位并行算法
最近一段時間看了一點"柔性字符串匹配", 發(fā)現(xiàn)位并行算法在字符串匹配這個領(lǐng)域還是很有用的, 下面抒發(fā)一下鄙見.
首先, 字符串位并行算法在acm界用的貌似并不多, 這跟算法本身的局限和人們對算法的了解有關(guān).
字符串位并行算法受限于機器字長, 所以不能用于模式串長度超過機器字長的情況, 這局限了該類算法的推廣.
但是由于位并行算法思想比較簡單, 一般易于實現(xiàn), 而且, 位并行這種手段本身也能保證算法性能相當可觀.
在字符串中的位并行算法, 基本是以單字符串匹配中的ShiftAnd算法和BNDM算法為基礎(chǔ), 擴展衍生的, 延伸到了多字符串匹配, 擴展字符串匹配和正則匹配里面.(這里的分類依據(jù)柔性字符串匹配)
做一些變量的聲明, 模式串p, p的長度是m, 文本是t.
ShiftAnd算法, 是單字符串匹配里面的一種前綴匹配算法. 算法維護一個字符串的集合, 集合中的每個字符串既是p的前綴, 同時也是已讀文本的后綴.
而在kmp算法里面, 就是用一個預(yù)計算出來的next數(shù)組, 來求已讀入文本同p的最長后綴, 而ShiftAnd算法里面的集合也是完成類似的功能.
而, 二進制位是表達集合的一種很好的方式, 只要這樣表達恰當?shù)脑?
用一個位掩碼D來表示這個集合, D的第j位被置為1, 當且僅當p1...pj是t1...ti的后綴, 而當Dm也是1的時候, 就是說, p本身是t1...ti的后綴, 找到了一個匹配.
那么在從t中讀入一個新的字符時, 如何更新這個后綴集合(即位掩碼D)呢?
首先構(gòu)造一個表B, 記錄字母表(a-z,A-Z)里面每個字符的位掩碼, 如果pj==c, 則掩碼B[c]的第j位是1, 這里的1, 用于后面說的"與"運算, 這也正是ShiftAnd算法的得名.
上面這個式子, 就是集合更新過程的本質(zhì), 每讀入一個新字符t(i+1), 就利用上面這個公式對位掩碼D進行更新.
式子中D<<1, 是要利用讀入的新字符, 來構(gòu)造更長的后綴, 如果能一直構(gòu)造出更長的串, 那么最終Dm==1, 就找到了一個匹配.
利用B[t(i+1)]和移位后的D的&運算, 來找那些滿足t(i+1)==p(j+1)的位置并置為1.
位運算可以在常數(shù)時間內(nèi)完成, 那么ShiftAnd的時間復(fù)雜度就是O(n).
下面是偽代碼, 來自<<柔性字符串匹配>>:
其實上面的東西大部分就是從"柔匹"里面抄來的 XDD。
ShiftAnd算法的一個變體, 就是ShiftOr算法, 你可以看到上面的那個式子里面, D以為的同時, 與1進行了"或"運算, 這是因為空字符串也是文本的后綴, 即空字符串無條件地可以匹配.
而ShiftOr就是通過使用對位去翻去掉了這個"或"運算的過程,詳情見"柔匹"原書.
在"柔匹"里面, 對單模式串匹配分了3類, 前綴匹配(如kmp和ShiftAnd), 后綴(如BM), 子串(如BNDM, BDM), 當然, 對于多模式串這個分類也適用.
但是, 后綴匹配分類里面卻沒有位并行算法的影子, 這是為什么?
那么, 首先, 字符串算法為什么存在? 為了加速匹配, 盡量在趨近O(n)的時間復(fù)雜度內(nèi)完成匹配, 那么kmp里面的next或者ShiftAnd里面的集合的作用呢, 是為了加速搜索窗口的移動.
可以理解為, ShiftAnd就是kmp的一個位并行版本, 因為兩者都在找p和已讀入文本的最長后綴.(關(guān)于兩者的實質(zhì)區(qū)別, 可以從自動機的角度來考慮.)
那么反觀后綴匹配里面的BM算法, BM本身比較復(fù)雜, 即使d1(后綴u在p中出現(xiàn)的位置)可以利用位并行也沒什么好說的.
而Horspool沒有利用d1, 即后綴u在模式串p中的出現(xiàn)的位置, 而另外的兩個d的計算基本不需要用位并行算法.
改天再繼續(xù)介紹一下BNDM(子串匹配里面的位并行算法)..
在討論BNDM之前, 從自動機的角度來討論一下并行算法, 其實并行算法在做的就是個NFA(非確定性自動機), 用位掩碼的方式來表達不同的跳轉(zhuǎn)狀態(tài), 而通過位運算的方法, 就可以輕易實現(xiàn)多個狀態(tài)同時進行跳轉(zhuǎn). 本來NFA就比DFA好理解, 但是NFA編程不好操作, 所以有了DFA, 而位并行算法卻可以在一定程度上很好地解決這個問題...
BNDM算法，其實實現(xiàn)手法， 跟BM里面求d1的方式一樣， 利用位并行, 構(gòu)造出來的自動機, 可以找到已讀入的后綴u在p里面的所有子串, 用位1標示.
那如果讀入的后綴的長度==p的長度了, 而且子串集合不為空(即位掩碼最高位是1), 那么就是找到了一個匹配.
下面我最想貼出來的就是不同算法的性能分析表了:
解釋見"柔匹".
平均時間復(fù)雜度最優(yōu)的是子串匹配, 即BNDM和BOM.
對于多模式串的匹配, 位并行算法很容易拓展, 這也體現(xiàn)了位并行算法的靈活性.
但是, 有一個前提是, 所有子串的長度和不要超過一個機器字的長度限制.
Multiple Shift-And算法的思想, 就是在一個機器字里面對r個模式串進行Shift-And算法的位操作.
因為位并行可以處理NFA中多個狀態(tài)的同時跳轉(zhuǎn), 那么處理多個模式串的匹配自然也是不在話下, 只是需要特殊的掩碼來測試一下哪一個模式串被匹配到了, 其實這個掩碼就是Shfit-And里面測試掩碼的拼接而已.
但是, 卻沒有Multiple Shift-Or算法, 因為, Shift-Or需要在末尾給掩碼引入0, 可以構(gòu)造出一個掩碼 , 然后拼接一下, 但是這樣就沒有Shift-Or原來那種只通過移位就引入0的意味了, 也就是, Multi Shift-Or沒有存在的意義, so...
單模式串中的子串匹配也可以擴展到多模式串來, 這就是Multiple BNDM, 基本思想也是對于子串匹配的拼接, 不贅述了XDD.
?PS: 在模式串完全隨機的情況下, 其實暴力匹配是最快的, 因為可以做到概率上為O(n)的效率, 而一般的匹配算法都會有比較大的常數(shù).
下面是證明:
假定text的長度是n, 而模式串的長度是p, 設(shè)字符集為S, |S|=s.
對于text里面的某個位置i, 從i開始匹配1個格的概率是1/s, 匹配2個格的概率是1/s^2, ..., 匹配p個格的概率是1/s^p.
那么對于i位置, 如果這個位置匹配失敗的話, 需要的代價是, 1+1/s+1/s^2+...+1/s^(p-1)+(s-1)/s^p, 而這是個常數(shù).
對于某個位置, 從這個位置匹配失敗的代價是O(1), 那么最壞情況, 就是跑完了整個text, 代價是O(n).
而剩下的就是比較哪個算法的常數(shù)更大的問題了, 而在絕對隨機的情況下, 一般是暴力的常數(shù)最小~!~~
~~~
posted on 2013-03-11 22:48?Jackiesteed 閱讀(...) 評論(...) 編輯 收藏轉(zhuǎn)載于:https://www.cnblogs.com/jackiesteed/articles/2954817.html
總結(jié)
以上是生活随笔為你收集整理的【字符串系列】字符串匹配中的位并行算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 黑客必须掌握的基本技能
- 下一篇： linux服务器上文件编码格式转化she