Java中BM(Boyer-Moore)算法的圖解與實現(xiàn)
簡介
本篇文章主要分為兩個大的部分,第一部分通過圖解的方式講解BM算法,第二部分則代碼實現(xiàn)一個簡易的BM算法。
基本概念
bm是一個字符串匹配算法,有實驗統(tǒng)計,該算法是著名kmp算法性能的3~4倍,其中有兩個關鍵概念,壞字符和好后綴。
首先舉一個例子
需要進行匹配的主串:a b c a g f a c j k a c k e a c
匹配的模式串:a c k e a c
壞字符
如下圖所示,從模式串最后一個字符開始匹配,主串中第一個出現(xiàn)的不匹配的字符叫做壞字符。
好后綴
如下圖所示,從模式串最后一個字符開始匹配,匹配到的主串中的字符為好后綴。
工作過程
壞字符
依舊是這張圖,接下來我們按從簡單情況到復雜情況進行分析。
step1: 找到壞字符f,該字符對應模式串中位置si=5,如果當前沒有找到壞字符,即完全匹配,直接返回。
step2: 查找字符f在模式串中出現(xiàn)位置,在當前模式串中,f沒有出現(xiàn),證明之前沒有情況可以匹配,模式串直接滑到f后面位置。此次結(jié)束,否則step3。
step3: 舉個例子吧,如果主串和模式串如下,f為壞字符,模式串中存在f,記位置xi=3,這時候不能直接滑到f的后面,這時候應該將模式串中的f和主串中的f對齊,如果是下面這個例子,此時直接匹配成功。如果模式串中不止存在一個f我們?nèi)绾芜x擇呢?用哪個f與模式串f對齊?答案是模式串中靠后的,如果使用靠前的,可能會多滑。
在壞字符匹配方法中,模式串往后滑動的距離應該是si-xi(如果壞字符在模式串中不存在,xi=-1)。
但是壞字符方法可能存在一個問題,看下面這個例子,壞字符a,對應匹配串中位置si=0,但是在匹配串中靠后出現(xiàn)位置xi=2,si-xi=-2,匹配串還往前移動,這樣就會出現(xiàn)問題,但是當我們把下面的好后綴講了之后,這個問題就迎刃而解了。
好后綴
首先看這張圖,這時候我們暫時不管壞字符方法(壞字符為k),由簡單情況到復雜情況進行分析。
step1:找到好后綴ac,起始位置si=4
step2:在模式串中查找其他位置是否存在好后綴ac(如果存在多個,為了不過度滑動,仍然選擇靠后的一個),找到開頭的ac,起始位置xi=0,滑動模式串使得找到的開頭ac與好后綴ac匹配,滑動距離si-xi=4。此次結(jié)束,否則step3。
step3:還是先舉個例子,假設模式串如下圖所示,此時好后綴為ac,但是在整個模式串其他地方不存在ac,此時如果我們直接將模式串滑到ac之后,則會出現(xiàn)問題,實際上我們只需要滑到c的位置即可。一般化的場景我們需要怎么操作呢?對于好后綴,如果匹配串的前綴能夠和好后綴的后綴匹配上,則我們直接滑到匹配位置。計算方式:好后綴后綴起始位置-0。
思考一下:如果匹配串中間出現(xiàn)與好后綴后綴匹配的情況,是否需要考慮?答案是否定的,當中間出現(xiàn)的時候,滑動過去肯定匹配不上。
BM算法
說完了BM算法中的兩個重要概念之后,BM算法具體怎樣實現(xiàn)的呢?
其實BM算法就是壞字符和好后綴的結(jié)合,具體就是匹配串向前滑動距離取兩者計算出來的較大值。
具體步驟我們用圖來演示一遍
代碼實現(xiàn)
在上面,我們說到了,在BM算法中有兩個關鍵概念--壞字符和好后綴,所以我們的代碼實現(xiàn)將分為三個步驟。
- 利用壞字符算法,計算匹配串可以滑動的距離
- 利用好后綴算法,計算匹配串可以滑動的距離
- 結(jié)合壞字符算法和好后綴算法,實現(xiàn)BM算法,查看匹配串在主串中存在的位置
step1: 壞字符算法,經(jīng)過之前的分析,我們找到壞字符之后,需要查找匹配串中是否出現(xiàn)過壞字符,如果出現(xiàn)多個,我們滑動匹配串,將靠后的壞字符與主串壞字符對齊。如果不存在,則完全匹配。如果我們每次找到壞字符都去查找一次匹配串中是否出現(xiàn)過,效率不高,所以我們可以用一個hash表保存匹配串中出現(xiàn)的字符以及最后出現(xiàn)的位置,提高查找效率。
我們設定的只有小寫字母,可以直接利用一個26大小的數(shù)組存儲,數(shù)組下標存儲出現(xiàn)的字符(字符-‘a’),數(shù)組值存儲出現(xiàn)的位置。
int[] modelStrIndex; private void badCharInit(char[] modelStr) { modelStrIndex = new int[26]; //-1表示該字符在匹配串中沒有出現(xiàn)過 for (int i = 0 ; i < 26 ; i ++) { modelStrIndex[i] = -1; } for (int i = 0 ; i < modelStr.length ; i++) { //直接依次存入,出現(xiàn)相同的直接覆蓋, //保證保存的時候靠后出現(xiàn)的位置 modelStrIndex[modelStr[i] - 'a'] = i; } }
查找壞字符出現(xiàn)位置badCharIndex,未出現(xiàn),匹配成功,直接返回0。
查找匹配串中出現(xiàn)的壞字符位置modelStrIndex,未出現(xiàn),滑動到壞字符位置之后,直接返回匹配串的長度。
返回badCharIndex - modelStrIndex。
注:壞字符是指與匹配串字符不匹配的主串字符,是看的主串,但是我們計算的位置,是匹配串中的位置。
/** * @param mainStr 主串 * @param modelStr 模式串 * @param start 模式串在主串中的起始位置 * @return 模式串可滑動距離,如果為0則匹配上 */ private int badChar(char[] mainStr, char[] modelStr, int start) { //壞字符位置 int badCharIndex = -1; char badChar = '\0'; //開始從匹配串后往前進行匹配 for (int i = modelStr.length - 1 ; i >= 0 ; i --) { int mainStrIndex = start + i; //第一個出現(xiàn)不匹配的即為壞字符 if (mainStr[mainStrIndex] != modelStr[i]) { badCharIndex = i; badChar = mainStr[mainStrIndex]; break; } } if (-1 == badCharIndex) { //不存在壞字符,需匹配成功,要移動距離為0 return 0; } //查看壞字符在匹配串中出現(xiàn)的位置 if (modelStrIndex[badChar - 'a'] > -1) { //出現(xiàn)過 return badCharIndex - modelStrIndex[badChar - 'a']; } return modelStr.length; }
step2:好后綴算法,經(jīng)過之前的分析,我們在實現(xiàn)好后綴算法的時候,有一個后綴前綴匹配的過程,這里我們?nèi)匀豢梢允孪冗M行處理。將匹配串一分為二,分別匹配前綴和后綴字串。ps:開始我的處理是兩個數(shù)組,將前綴后綴存下來,需要的時候進行匹配,但是在寫文章的時候,我突然回過神來,我已經(jīng)處理了一遍了,為什么不直接標記是否匹配呢?
初始化匹配串前綴后綴是否匹配數(shù)組,標志當前長度的前綴后綴是否匹配。
//對應位置的前綴后綴是否匹配 boolean[] isMatch; public void goodSuffixInit(char[] modelStr) { isMatch = new boolean[modelStr.length / 2]; StringBuilder prefixStr = new StringBuilder(); List<Character> suffixChar = new ArrayList<>(modelStr.length / 2); for (int i = 0 ; i < modelStr.length / 2 ; i ++) { prefixStr.append(modelStr[i]); suffixChar.add(0, modelStr[modelStr.length - i - 1]); isMatch[i] = this.madeSuffix(suffixChar).equals(prefixStr.toString()); } } /** * 組裝后綴數(shù)據(jù) * @param characters * @return */ private String madeSuffix(List<Character> characters) { StringBuilder sb = new StringBuilder(); for (Character ch : characters) { sb.append(ch); } return sb.toString(); }
step3: 結(jié)合壞字符和好后綴算法實現(xiàn)BM算法,起始就是每一次匹配,同時調(diào)用壞字符和好后綴算法,如果返回移動距離為0,表示已經(jīng)匹配成功,直接返回當前匹配的起始距離。其余情況下,滑動壞字符和好后綴算法返回的較大值。如果主串匹配完還沒有匹配成功,則返回-1。
注:加了一些日志打印匹配過程
public int bmStrMatch(char[] mainStr, char[] modelStr) { //初始化壞字符和好后綴需要的數(shù)據(jù) this.badCharInit(modelStr); this.goodSuffixInit(modelStr); int start = 0; while (start + modelStr.length <= mainStr.length) { //壞字符計算的需要滑動的距離 int badDistance = this.badChar(mainStr, modelStr, start); //好后綴計算的需要滑動的距離 int goodSuffixDistance = this.goodSuffix(mainStr, modelStr, start); System.out.println("badDistance = " +badDistance + ", goodSuffixDistance = " + goodSuffixDistance); //任意一個匹配成功即成功(可以計算了壞字符和好后綴之后分別判斷一下) //減少一次操作 if (0 == badDistance || 0 == goodSuffixDistance) { System.out.println("匹配到的位置 :" + start); return start; } start += Math.max(badDistance, goodSuffixDistance); System.out.println("滑動至:" + start); } return -1; }
最后
使用前面使用的例子,我們來實際調(diào)用一下
public static void main(String[] args) { BoyerMoore moore = new BoyerMoore(); char[] mainStr = new char[]{'a','b', 'c', 'a', 'g', 'f', 'a', 'c', 'j', 'k', 'a', 'c', 'k', 'e', 'a', 'c'}; char[] modelStr = new char[]{'a', 'c', 'k', 'e', 'a', 'c'}; System.out.println(moore.bmStrMatch(mainStr, modelStr)); }
調(diào)用結(jié)果
以上就是Java中BM(Boyer-Moore)算法的圖解與實現(xiàn)的詳細內(nèi)容,更多關于Java BM算法的資料請關注腳本之家其它相關文章!
相關文章
使用spring實現(xiàn)郵件的發(fā)送實例(含測試,源碼,注釋)
本篇文章主要介紹了使用spring實現(xiàn)郵件的發(fā)送實例,詳細的介紹了使用spring配置實現(xiàn)郵件發(fā)送,含測試,源碼,注釋,有興趣的可以下2017-05-05Java 中文字符按Unicode排序的實現(xiàn)方法
這篇文章主要介紹了Java 中文字符按Unicode排序的實現(xiàn)方法,非常不錯,具有一定的參考借鑒價值,需要的朋友可以參考下2018-10-10Java springboot 配置文件與多環(huán)境配置與運行優(yōu)先級
這篇文章主要介紹了Java springboot如何配置文件,進行多環(huán)境配置,以及運行優(yōu)先級,感興趣的小伙伴可以借鑒一下2023-04-04Apache?Commons?CLI構(gòu)建命令行應用利器教程
這篇文章主要為大家介紹了構(gòu)建命令行應用利器Apache?Commons?CLI的使用教程詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-12-12springBoot 過濾器去除請求參數(shù)前后空格實例詳解
這篇文章主要為大家介紹了springBoot 過濾器去除請求參數(shù)前后空格實例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2022-11-11