字串搜尋演算法Boyer-Moore的Java實現

字串搜尋演算法Boyer-Moore的Java實現

由於是畢業後轉行的原因,所以本人在工作之前沒有系統的學過資料結構、演算法導論之類的課。說白了就是沒有這樣的底蘊,哈哈。所以這篇部落格主要是寫給自己看的,因為時間有限,本人寫的內容估計遠遠不會有大家期待的那麼詳細,所以,可以此文可以選擇性的忽略哦。

演算法介紹:關於Boyer-Moore演算法(後面簡稱BM演算法)的概念網上一搜一大把。所以這裡就不做具體闡述了。有疑問的建議參考阮一峰的這篇文章(此文文筆細膩且又通俗易懂):

阮一峰:字串匹配的Boyer-Moore演算法

演算法精髓:這個字串查詢演算法高效的原因在於當字串不能完全匹配的時候可以一次性跳過多個字元。它不需要對被搜尋的字串中的字元進行逐一比較。那麼,如何跳過呢?當然是利用模式字串(pattern)和文字(text)在匹配過程中的已知資訊跳過一些不必要的比較啦。上面推薦博文中的壞字元演算法(bad-character)和好字尾演算法(good-suffix )這兩個啟發式策略就是用於決定如何移動(shift)或者移動多少位的,此處就不細說啦。

完整演算法:由於本文主要是用來助記的,不是循循善誘告訴你如何實現這個演算法的。所以本人先貼出完整的程式碼(Java實現),然後再做進一步的程式碼分析吧。

public class BoyerMoore
{
public static void main(String[] args)
{
String text = "here is a simple example";
String pattern = "example";
BoyerMoore bm = new BoyerMoore();
bm.boyerMoore(pattern, text);
}
public void boyerMoore(String pattern, String text)
{
int m = pattern.length();
int n = text.length();
Map<String, Integer> bmBc = new HashMap<String, Integer>();
int[] bmGs = new int[m];
// proprocessing
preBmBc(pattern, m, bmBc);
preBmGs(pattern, m, bmGs);
// searching
int j = 0;
int i = 0;
int count = 0;
while (j <= n - m)
{
for (i = m - 1; i >= 0 && pattern.charAt(i) == text.charAt(i   j); i--)
{ // 用於計數
count  ;
}
if (i < 0)
{
System.out.println("one position is:"   j);
j  = bmGs[0];
}
else
{
j  = Math.max(bmGs[i], getBmBc(String.valueOf(text.charAt(i   j)), bmBc, m) - m   1   i);
}
}
System.out.println("count:"   count);
}
private void preBmBc(String pattern, int patLength, Map<String, Integer> bmBc)
{
System.out.println("bmbc start process...");
{
for (int i = patLength - 2; i >= 0; i--)
if (!bmBc.containsKey(String.valueOf(pattern.charAt(i))))
{
bmBc.put(String.valueOf(pattern.charAt(i)), (Integer) (patLength - i - 1));
}
}
}
private void preBmGs(String pattern, int patLength, int[] bmGs)
{
int i, j;
int[] suffix = new int[patLength];
suffix(pattern, patLength, suffix);
// 模式串中沒有子串匹配上好字尾,也找不到一個最大字首
for (i = 0; i < patLength; i  )
{
bmGs[i] = patLength;
}
// 模式串中沒有子串匹配上好字尾,但找到一個最大字首
j = 0;
for (i = patLength - 1; i >= 0; i--)
{
if (suffix[i] == i   1)
{
for (; j < patLength - 1 - i; j  )
{
if (bmGs[j] == patLength)
{
bmGs[j] = patLength - 1 - i;
}
}
}
}
// 模式串中有子串匹配上好字尾
for (i = 0; i < patLength - 1; i  )
{
bmGs[patLength - 1 - suffix[i]] = patLength - 1 - i;
}
System.out.print("bmGs:");
for (i = 0; i < patLength; i  )
{
System.out.print(bmGs[i]   ",");
}
System.out.println();
}
private void suffix(String pattern, int patLength, int[] suffix)
{
suffix[patLength - 1] = patLength;
int q = 0;
for (int i = patLength - 2; i >= 0; i--)
{
q = i;
while (q >= 0 && pattern.charAt(q) == pattern.charAt(patLength - 1 - i   q))
{
q--;
}
suffix[i] = i - q;
}
}
private int getBmBc(String c, Map<String, Integer> bmBc, int m)
{
// 如果在規則中則返回相應的值,否則返回pattern的長度
if (bmBc.containsKey(c))
{
return bmBc.get(c);
}
else
{
return m;
}
}
}

演算法理論探討與程式碼分析:
A1:壞字元演算法理論探討
當出現一個壞字元時, BM演算法向右移動模式串, 讓模式串中最靠右的對應字元與壞字元相對,然後繼續匹配。壞字元演算法有兩種情況。

1.模式串中有對應的壞字元時,讓模式串中最靠右的對應字元與壞字元相對(由於是讓壞字元與模式串中最靠右的對應字元對其,所以模式串有可能出現左移的情況,也即可能出現走回頭路的情況,但若是走回頭路,則移動距離就是負數了,肯定不是最大移動步數了)。

2.模式串中不存在壞字元,很好,直接右移整個模式串長度這麼大步數。

A2:壞字元演算法具體執行步驟:
BM演算法子串比較失配時,按壞字元演算法計算pattern需要右移的距離,要藉助bmBc陣列,而按好字尾演算法計算pattern右移的距離則要藉助bmGs陣列。下面講下怎麼計算bmBc陣列。

bmbc[]陣列中,某個字元索引,比如bmbc[‘v’]表示字元v在模式串中最後一次出現的位置距離模式串串尾的長度。

計算壞字元陣列bmBc[]:
這個計算應該很容易,似乎只需要bmBc[i] = m – 1 – i就行了,但這樣是不對的,因為i位置處的字元可能在pattern中多處出現(如下圖所示),而我們需要的是最右邊的位置,這樣就需要每次迴圈判斷了,非常麻煩,效能差。這裡有個小技巧,就是使用字元作為下標而不是位置數字作為下標。這樣只需要遍歷一遍即可,這貌似是空間換時間的做法,但如果是純8位字元也只需要256個空間大小,而且對於大模式,可能本身長度就超過了256,所以這樣做是值得的(這也是為什麼資料越大,BM演算法越高效的原因之一)。

壞字元在模式串中有出現時候的移動位數圖示

如前所述,bmBc[]的計算分兩種情況,與前一一對應。
Case1:字元在模式串中有出現,bmBc[‘v’]表示字元v在模式串中最後一次出現的位置,距離模式串串
尾的長度,如上圖所示。
Case2:字元在模式串中沒有出現,如模式串中沒有字元v,則BmBc[‘v’] = strlen(pattern)。

將Case1寫成虛擬碼也很簡單:

void PreBmBc(char *pattern, int m, int bmBc[])
{
int i;
for(i = 0; i < 256; i  )
{
bmBc[i] = m;
}
for(i = 0; i < m - 1; i  )
{
bmBc[pattern[i]] = m - 1 - i;
}
}

當然在本人貼出來的完整程式碼中使用Map作為bmbc的儲存結構,所以Case1的java表述如下:

private void preBmBc(String pattern, int patLength, Map<String, Integer> bmBc)
{
System.out.println("bmbc start process...");
{
for (int i = patLength - 2; i >= 0; i--)
if (!bmBc.containsKey(String.valueOf(pattern.charAt(i))))
{
bmBc.put(String.valueOf(pattern.charAt(i)), (Integer) (patLength - i - 1));
}
}
}

那麼,如何表述Case2呢,不可思議的簡單,見下:可見使用Map作為bmbc儲存容器在text字元不能窮盡256的情況下更加節省空間:

private int getBmBc(String c, Map<String, Integer> bmBc, int m)
{
// 如果在規則中則返回相應的值,否則返回pattern的長度, 引數m恆等於pattern的長度
if (bmBc.containsKey(c))
{
return bmBc.get(c);
}
else
{
return m;
}
}

B1:好字尾演算法理論探討
如果程式匹配了一個好字尾, 並且在模式中還有另外一個相同的字尾或字尾的部分, 那把下一個字尾或部分移動到當前字尾位置。假如說,pattern的後u個字元和text都已經匹配了,但是接下來的一個字元不匹配,我需要移動才能匹配。如果說後u個字元在pattern其他位置也出現過或部分出現,我們將pattern右移到前面的u個字元或部分和最後的u個字元或部分相同,如果說後u個字元在pattern其他位置完全沒有出現,很好,直接右移整個pattern。這樣,好字尾演算法有三種情況:

1.模式串中有子串和好字尾完全匹配,則將最靠右的那個子串移動到好字尾的位置繼續進行匹配。

2.如果不存在和好字尾完全匹配的子串,則在好字尾中找到具有如下特徵的最長子串,使得P[m-s…m]=P[0…s]。

3.如果完全不存在和好字尾匹配的子串,則右移整個模式串。

綜上可知,完整的BM演算法的移動規則是:模式字串每次比較的移動步長為 MAX(shift(好字尾),shift(壞字元)),即BM演算法是每次向右移動模式串的距離是,按照好字尾演算法和壞字元演算法計算得到的最大值。壞字元演算法的預處理陣列是bmBc[],好字尾演算法的預處理陣列是bmGs[]。

B2:好字尾演算法具體執行步驟:
這裡bmGs[]的下標是數字而不是字元了,表示字元在pattern中位置。如前所述,bmGs陣列的計算分三種情況,與前一一對應。假設圖中好字尾長度用陣列suff[]表示。
Case1:對應好字尾演算法case1,如下圖,K是好字尾之前的那個位置。
"好字尾Case1圖示"

Case2:對應好字尾演算法case2:如下圖所示:
"好字尾Case2圖示"

Case3:對應與好字尾演算法case3,bmGs[i] = strlen(pattern)= m
這裡寫圖片描述

根據上面的圖示,給出的程式碼如下:

private void preBmGs(String pattern, int patLength, int[] bmGs)
{
int i, j;
int[] suffix = new int[patLength];
suffix(pattern, patLength, suffix);
// 先全部賦值為m,包含Case3
for (i = 0; i < patLength; i  )
{
bmGs[i] = patLength;
}
// Case2
j = 0;
for (i = patLength - 1; i >= 0; i--)
{
if (suffix[i] == i   1)
{
for (; j < patLength - 1 - i; j  )
{
if (bmGs[j] == patLength)
{
bmGs[j] = patLength - 1 - i;
}
}
}
}
// 模式串中有最長好字尾,也即Case1
for (i = 0; i < patLength - 1; i  )
{
bmGs[patLength - 1 - suffix[i]] = patLength - 1 - i;
}
System.out.print("bmGs:");
for (i = 0; i < patLength; i  )
{
System.out.print(bmGs[i]   ",");
}
System.out.println();
}

上面的程式碼中用到了suffix陣列,這個陣列咋求呢?實際上suffix[i]就是求pattern中以i位置字元為字尾和以最後一個字元為字尾的公共字尾串的長度。所以,其實現如下:

private void suffix(String pattern, int patLength, int[] suffix)
{
suffix[patLength - 1] = patLength;
int q = 0;
for (int i = patLength - 2; i >= 0; i--)
{
q = i; 
while (q >= 0 && pattern.charAt(q) == pattern.charAt(patLength - 1 - i   q))
{
q--;
}
suffix[i] = i - q;
}
}

至此,BM演算法的關鍵程式碼基本講完了。完整程式碼在最開始也已經給出。在這裡,本人想說的是,此處給出的程式碼還有許多可以優化和改進的地方,有興趣的讀者,可以參考下面這篇博文(用C#實現)哦:

grep之字串搜尋演算法Boyer-Moore由淺入深(比KMP快3-5倍)