分享一下字符串匹配BM算法学习心得。
字符串匹配BM（Boyer-Moore）算法學習心得
BM算法 是 Boyer-Moore算法 的縮寫，是一種基于后綴比較的模式串匹配算法。BM算法在最壞情況下可以做到線性的，平均情況下是亞線性的（即低于線性）。這也是他在實際應用中優(yōu)于KMP算法的一個原因吧。
最近突然在看[柔性字符串匹配].[Flexible.Pattern.Matching.in.Strings](Gonzalo.Navarro,.Mathieu.Raffinot)，想了解一下字符串匹配的一些算法，以前使用的算法基本都只是和ACM有關(guān)的，而且在單串匹配的情況下一般都只用KMP算法，而在這本書中對KMP算法的評價并不是很好，原因主要是出于工程上的“實用”上的原因吧。KMP算法雖然在理論上最壞復雜度也是線性的，可是在實際應用中并沒有那么多最壞情況，而且如果用于模式匹配的話，很多情況下模式串也是很短的。
下面來說一說我寫這個的原因吧，我搞了兩年ACM嘛，現(xiàn)在看書肯定還是和ACM有一定關(guān)系的，而且很自然的會將一些事情和ACM中做對比的。[柔性字符串匹配]說KMP在實際應用中不好，那我就想反過來看一下在實際應用中比較好的算法在ACM中效果怎么樣了，最先看到的就是BM算法（當然在書中還看到了Shift-or 和Shift-and 算法，但由于長度限制差別太大，實在不具可比性，不過這兩個算法個人感覺是相當優(yōu)雅的）。由于這本書太實用了，對于“不實用”的算法都只做基本介紹（對于KMP算法也一樣，只做了一點大概的介紹，其實我非常不明白為什么會出現(xiàn)這種現(xiàn)象，難道理論和應用的差別有這么大么?）。書上說原始BM算法在最壞情況下復雜度是O(n*m)的，O(n*m)的算法在ACM中必然是不“實用”的，但它說BM算法有兩個優(yōu)化版本可以在最壞情況下也能達到線性的。這樣一來我覺得就有一定可比性了，于是就想仔細看一下BM算法。
書上說的兩個算法是：the Boyer-Moore-Galil [Gal79] and the Turbo-BM[CGR92] algorithms。
我找了找，也沒找到什么相關(guān)資料，但是回頭一想這個算法都出來這么久了，直接搜BM算法應該也能搜出優(yōu)化過的BM算法吧。
下面是我找到的一些文章。
?
字符串匹配那些事（一）
這篇文章好像是淘寶的吧，其中沒有明確指出BM算法的時間復雜度。
M模式匹配算法原理（圖解）
這篇文章對BM進行了大致的講解，文中分析到了時間復雜度，
文中為：最好情況下的時間復雜度為O(n/m)，最壞情況下時間復雜度為O(m·n)。
精確字符串匹配（BM算法）??BM 算法中“好后綴”預處理
在第一篇文章中提到了時間復雜度：整個算法的時間復雜度最壞的情況是 O(m)，m 是 T 的長度。
可有一點我不明白，按這篇文章中的作法，好像并沒有對原始的BM算法進行優(yōu)化，而原始的BM算法確實是O(m·n)的。
?
又重新去搜論文了。
A Fast String Searching Algorithm?- The University of Texas at Austin
Boyer-Moore-Galil?[Gal79]?Z. Galil. On improving the worst case running time of the Boyer-Moore string searching algorithm. Communications of the ACM, 22(9):505–508, 1979.
看了一下這兩篇論文，看一下第一篇，實在太長了（其實只有11頁但相對于第二篇只有4頁）。然后果斷看第二篇，雖然已經(jīng)是三十多年前的論文了。
在這里費話兩句，之前我因為《柔性字符串匹配》這本書說KMP不怎么實用，心里還感覺有點不爽，你說KMP不實用，那你拿一個實用且理論最壞復雜度為線性的算法讓我看看。再加上找了一天多也只有一些BM算法的原始版。看了上面的第二篇文章，實現(xiàn)了一下其中的算法并在POJ上試了試，果然沒問題。在這一刻我深深的折服于《柔性字符串匹配》了。這本書果然名副其實。值得推薦。
好了，費話也就說這么多，接下來說點技術(shù)性的吧，看看Z. Galil. 是如何將BM的最壞情況復雜度降到線性的。在這里，我默認大家是明白BM算法原理的。加上上面已經(jīng)有那么多文章是寫B(tài)M算法的了（如果需要，建議閱讀淘寶的那篇），我這里只討論的優(yōu)化了。
以下討論中，文本串用T表示，模式串用p表示。|S|表示字符串S的長度。默認情況下，n=|T|，m=|p|
?
為什么原始的BM算法在最壞情況下是O(n*m)的呢？一個最簡單的實例就是 p=a^m，T=a^n。就是說模式串是由m個a組成，文本是由n個a組成，在這種情況下，找出所有匹配復雜度就是O(n*m)的。造成這種情況最主要的就是BM算法在向后滑動的時候?qū)χ捌ヅ溥^的字符的利用率并不高，不像KMP，一旦匹配過，就不會再回過頭再匹配一次，這也是我感覺KMP相當神的一點。
在此之前先討論幾個概念，一個是字符串的周期性。
直觀的理解就是類似：abcabcabcabc,aabaabaab...這樣的串，都是有周期性的。我們在這里認為這種模式串也具有周期性的——abcabcab，就是最一個重復單元是不完整的。這里的周期性指至少重復一次以上，這種串不算有周期性——abcdabc。隨便提一下，這樣的串不具有周期性——ababababc，這里的周期性是針對于整個字符串來說的。
對于具用周期性的模式串，記模式串的最小正周期長度為ord。
再引出一個定義：匹配塊，T中的一段匹配塊是一段連續(xù)的字符串，其中包含有匹配上的匹配串，并且這些匹配上的區(qū)域是相互重疊的并且盡可能向左右延伸。當然在匹配塊中不包含多余的字符。舉一個例子。（這里對匹配塊的定義不準確，大家明白這個意思就行了。）
p = aba
T = abababaabaaba
其中前面一部分就是一個匹配塊：abababa，后面的abaaba不算，因為匹配上匹配串沒有相互重疊。
基于以下幾點討論，我們可以對BM算法進行優(yōu)化。
（1）如果文本串中不含模式串，那么BM算法在最壞情況下的比較次數(shù)為7n次。
（2）BM算法的最壞情況復雜度為O(n+r*m)，其中n為|T|，m為|p|，r為p在T中出現(xiàn)次數(shù)。
（3）如果在上式中r>2n/m，則p是具有周期性的。
（4）如果p不具周期性，那么BM算法在最壞情況下是線性的。
（5）記一個匹配塊中所有匹配上的位置為p0,p1,...,pk（以遞增方式排列），
那么對于0<i<=k,pi - p(i-1)=ord。而且每個匹配塊中的匹配可以做到線性。
（6）優(yōu)化之后的BM' 算法是O(n)的。
優(yōu)化方法：每次成功匹配以后，向右移ord，并且在這種情況下只匹配那ord個字符。
偽代碼如下：
2 for(k=0; k+|p|<=|T|; )
3 {
4 for(i=pn-1; i>=last && T[k+i]==p[i]; )
5 i--;
6 if( i<last )
7 { /// 成功匹配
8 last = |p| - ord;
9 k += ord;
10 }
11 else
12 { /// 匹配失敗
13 last = 0;
14 k += (BM算法中的移動距離);
15 }
16 }
這里就是算法的核心了。這里 hust 有BM實現(xiàn)poj 3461的完整代碼。
這個優(yōu)化只要知道的話就很好做了，在已有的BM代碼上加兩行就實現(xiàn)了。
這個改進之后的BM' 算法在最壞情況下是線性的。
下面是相關(guān)說明，論文上也有證明。這里以比較直白的方式對其進行一些分析。
（1）如果文本串中不含模式串，那么BM算法在最壞情況下的比較次數(shù)為7n次。
這一條我也不知道怎么證明的，這里默認他是正確的吧。論文上說比較復雜沒有介紹。
（2）BM算法的最壞情況復雜度為O(n+r*m)，其中n為|T|，m為|p|，r為p在T中出現(xiàn)次數(shù)。
這里我們把所有的r次完整匹配取出來，總共r*m次比較。這里我們想像用這r次匹配上的位置（取最左端）把T分割成了r+1個部分。對于前r個部分，我們還需要在其右端加上(m-1)字符。這里的r+1個文本串已經(jīng)無法匹配上p了。所以這里可以直接使用（1）了。而這時的總長度約為（n+r*m），代入第一條可得總比較次數(shù)少于：
7*n + 8*r*m <- ( 7*(n+r*m) + r*m )
（3）如果在上式中r>2n/m，則p是具有周期性的。
這里可以用鴿籠原理。先討論當r>n/m時，即r*m>n。所有匹配的長度之和已經(jīng)大于了|T|，這時，至少有兩個匹配上的串是互相重疊的。這樣，r>2*n/m就很好理解了吧，r*(m/2)>n，至少存在兩次匹配上的串是互相重疊的，并且，重疊部分大于m/2。這代表了什么含意呢？想像一下，一個字符串，可以通過平移一小段距離，使重疊的那一部分互相匹配。這可以推出這個串是具有周期性的。
（4）如果p不具周期性，那么BM算法在最壞情況下也是線性的。
這條可以用（3）的逆否命題得到：如果p不具有周期性，那么在上式中r<=2n/m。再代入（2）中表達式O(n+r*m)。可得此時BM算法復雜度O(3*n)即O(n)。
（5）記一個匹配塊中所有匹配上的位置為p0,p1,...,pk（以遞增方式排列）。那么對于0<i<=k,pi - p(i-1)=ord。
這一點顯然吧。其實我并不是特別明白論文中特意指出這一點的意義何在。
（6）BM' 算法是O(n)的。
在這一點的理解上，很接近第二步的分析。把所有的匹配塊提取出來，對于匹配塊來說匹配是線性的，匹配塊的總長是在O(n)級別的。這里需要說明一點的是匹配塊是可以相互重疊的，但重疊部分不會大于m/2。而在剩下部分的匹配依然是O(n)級別的，所以總的時間復雜度也是O(n)的。
?
最后加一點關(guān)于（4）點的討論：我之前有一個錯誤的認識，我以為當p=b+a^m,T=a^n 時BM算法也是O(n*m)的，但我分析錯了一個地方，我以為當每次匹配到p的最左邊的b時，失敗后只向右跳一個字符，而實際情況是向右跳了串長這么多。對BM的理解不夠啊。
附上poj測試圖，雖然從這里看BM算法跑得比kmp慢了一點，但我已經(jīng)很滿足了。
上面的兩份代碼是用BM實現(xiàn)的，下面兩份是用KMP實現(xiàn)的。
?
轉(zhuǎn)載于:https://www.cnblogs.com/a180285/archive/2011/12/15/BM_algorithm.html
《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀總結(jié)
以上是生活随笔為你收集整理的分享一下字符串匹配BM算法学习心得。的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Oracle VARRAY的实际应用简介
- 下一篇： 关于HtmlParser中Parser【