程式扎記: [ Algorithm in Java ] 搜尋 : KMP 搜尋法

標籤

2011年9月30日 星期五

[ Algorithm in Java ] 搜尋 : KMP 搜尋法

前言 :
字串搜尋演算法即是在一份文件中尋找一段字串。由於文件的內容可能相當龐大或者複雜,因此有效率的字串搜尋演算法經常扮演著重要的角色.

暴力法 :
我們可以定義一個索引i(或指標)用來指向文件中開始比對的起點字元。當比對過程中遇到某個字元不符合時,就移動此索引到下一個字元,並重新比對。這個類似地毯式搜尋的方法稱為暴力搜尋法. 考慮下面範例, 在 i=0 時,只有前三個字元是相符的,所以該次比對結果為失敗。下一次比對就從T[1](i=1)開始。以此類推,當i=13時,我們找到了與P相符的字串{a, b, c, d, a, d}。總共經過34次比對 :


- 複雜度分析
假設字串P的長度為M,文件長度為N。欲找到相符字串其在最壞情形下,可能需要啟動(N-M+1)次搜尋。如果考慮字串P的長度,那麼最多共需要M(N-M+1)次字元比對,才
能確認字串搜尋的結果。一般而言,M會比N小很多,所以暴力字串搜尋法大概需要經過 MN 次字元比對!

隨著字串處理的需求日益增加,暴力搜尋法在實際應用上的表現O(MN) ,顯得差強人意。於是有些更快速的字串搜尋演算法利用字串的前置處理,減少字串比對的次數. 通常這些演算法在實際應用上,可以達到 O(M+N) 的運算複雜度.

Knuth-Morris-Pratt 演算法 : (wiki)
KMP演算法的原理在當字元比對不符時, 我們可以從比對字串 P 中得知某些字元可以略過不需檢查. 如此就不必從文件T的下一個字元重新開始比對 :


- 演算法說明
KMP 演算法的關鍵在於建構一個部分相符表格,好用來計算比對字串位移的大小. 由於我們是在比對失敗時,才參 考這個表格,所以此表格又被稱為失誤函數. 該函數定義一表格next[M],當比對失敗發生在 P[j] 時,可以拿 P[next[j]] 作為下一個重新比對的起點. 以P={a,b, c, d, a, d}為例,next表格的內容為{-1, 0, 0, 0, 0, 1}.

在建構失誤函數時, 當字元比對失敗在P[j],而且 P[j-k]…P[j-1] 正好等於 P[0]…P[k-1] 時,我們可以得到 next[j]=k, 這樣的過程請參考下面說明 :


而對應的代碼我們使用函數 buildKMP() 來建立失誤表格 (next[]), 代碼如下 : 

- 函數 buildKMP() 代碼 :
  1. public static int[] buildKMP(char[] ptnChars)  
  2. {  
  3.     int kmpMtx[] = new int[ptnChars.length+1];  
  4.     int i=0, j=kmpMtx[0]=-1;  
  5.     while(i
  6.     {  
  7.         /*Reset j*/  
  8.         while(j>-1 && ptnChars[i]!=ptnChars[j])  
  9.         {  
  10.             j = kmpMtx[j]; /*Total match matched j time, let j = match_next[j]*/                  
  11.         }  
  12.         i++;  
  13.         j++;  
  14.         if(i
  15.         {  
  16.             /*If ptnChars[i]==ptnChars[j], keep increasing j (matched j time)*/  
  17.             /*Let kmpMtx[i]=kmpMtx[j], so */  
  18.             kmpMtx[i] = j>0?kmpMtx[j]:0;  
  19.         }  
  20.         else  
  21.         {  
  22.             kmpMtx[i] = j;  
  23.         }  
  24.     }  
  25.     return kmpMtx;  
  26. }  

有了失誤表格, 接著我們就可以繼續 KMP 搜尋演算法的說明, 接著我們使用一個 類別 KMPSearchAlg 並將目的字串傳入建構子, 接著便可以呼叫函示 search() 並傳入搜尋的 Pattern 字串 (P[]) 找尋目的字串是否含 Pattern 字串, 如果有則傳回 Pattern 字串在目的字串中出現的第一個位置, 否則傳回 -1. 完整代碼如下 :
- KMPSearchAlg.java :
  1. package alg.ssearch;  
  2.   
  3. public class KMPSearchAlg {  
  4.     public String str;  
  5.     public KMPSearchAlg(String oStr)  
  6.     {  
  7.         str = oStr;  
  8.     }  
  9.     public static int[] buildKMP(char[] ptnChars)  
  10.     {  
  11.         System.out.println("\t[Test] Ptn="+String.valueOf(ptnChars));  
  12.         int kmpMtx[] = new int[ptnChars.length+1];  
  13.         int i=0, j=kmpMtx[0]=-1;  
  14.         while(i
  15.         {  
  16.             /*Reset j*/  
  17.             while(j>-1 && ptnChars[i]!=ptnChars[j])  
  18.             {  
  19.                 System.out.printf("\t[Reset] j=kmpMtx[%d]=%d...\n", j, kmpMtx[j]);  
  20.                 j = kmpMtx[j]; /*Total match matched j time, let j = match_next[j]*/                  
  21.             }  
  22.             i++;  
  23.             j++;  
  24.             System.out.printf("\t[Test] Comparing p[i=%d]=%c with p[j=%d]=%c...", i, i'*',j,ptnChars[j]);  
  25.             if(i
  26.             {  
  27.                 /*If ptnChars[i]==ptnChars[j], keep increasing j (matched j time)*/  
  28.                 /*Let kmpMtx[i]=kmpMtx[j], so */  
  29.                 //kmpMtx[i] = j>0?kmpMtx[j]:0;  
  30.                 kmpMtx[i] = kmpMtx[j];  
  31.                 System.out.printf("(1)kmpMtx[%d]=%d\n", i, kmpMtx[i]);  
  32.             }  
  33.             else  
  34.             {  
  35.                 kmpMtx[i] = j;  
  36.                 System.out.printf("(2)kmpMtx[%d]=%d\n", i, kmpMtx[i]);  
  37.             }  
  38.         }  
  39.         return kmpMtx;  
  40.     }  
  41.       
  42.     public int search(String ptn)  
  43.     {  
  44.         char[] oStrChars = str.toCharArray();  
  45.         char[] ptnChars = ptn.toCharArray();  
  46.         int main_index=0;  
  47.         int match_index=0;  
  48.           
  49.         /*First round comparing*/  
  50.         while(main_index
  51.         {  
  52.             if(oStrChars[main_index]==ptnChars[0])  
  53.             {  
  54.                 main_index++;  
  55.                 match_index=1;  
  56.                 while(main_index
  57.                 {  
  58.                     if(oStrChars[main_index]!=ptnChars[match_index]) break;  
  59.                     main_index++;  
  60.                     match_index++;  
  61.                 }  
  62.                 break;  
  63.             }  
  64.             main_index++;  
  65.         }  
  66.         if(match_index==ptn.length()) return main_index-match_index; /*Already matched*/  
  67.         int kmpMtx[] = KMPSearchAlg.buildKMP(ptn.toCharArray());  
  68.           
  69.         /*Second round comparing*/  
  70.         while(main_index
  71.         {  
  72.             char c = oStrChars[main_index];  
  73.             while(ptnChars[match_index]!=c)  
  74.             {  
  75.                 match_index=kmpMtx[match_index];  
  76.                 if(match_index<0break;  
  77.                 if(ptnChars[match_index]==c)System.out.printf("\t[KMP] Start searching on match_index=%d...\n", match_index);  
  78.             }             
  79.             main_index++;  
  80.             match_index++;  
  81.             if(match_index==0)  
  82.             {  
  83.                 /*Simple string matching*/  
  84.                 while(main_index
  85.                 {  
  86.                     if(oStrChars[main_index]==ptnChars[0])  
  87.                     {  
  88.                         main_index++;  
  89.                         match_index=1;  
  90.                         while(main_index
  91.                         {  
  92.                             if(oStrChars[main_index]!=ptnChars[match_index]) break;  
  93.                             main_index++;  
  94.                             match_index++;  
  95.                         }  
  96.                         break;  
  97.                     }  
  98.                     main_index++;  
  99.                 }  
  100.             }  
  101.         }  
  102.           
  103.         if(match_index==ptn.length()) return main_index-match_index; /*Matched*/  
  104.         return -1;  
  105.     }  
  106.       
  107.     public static void testSearch()  
  108.     {  
  109.         //testKMPMtx();  
  110.         KMPSearchAlg kmpAlg = new KMPSearchAlg("ABCABCDABABCDABCDAD");  
  111.         int mIndex = kmpAlg.search("ABCDAD");  
  112.         if(mIndex>0)  
  113.         {  
  114.             System.out.println("\t[KMP] Match!");  
  115.             System.out.println(kmpAlg.str);  
  116.             for(int i=0; i" ");  
  117.             System.out.println("^");  
  118.         }  
  119.         else  
  120.         {  
  121.             System.out.println("\t[KMP] Mismatch!");  
  122.         }  
  123.     }  
  124.       
  125.     public static void main(String args[])  
  126.     {  
  127.         testSearch();  
  128.     }  
  129. }  

執行結果如下 :


- 演算法分析
建構next表格的複雜度為O(M),所以 KMP 演算法的整體效率為 O(M+N)!
在實際應用上,KMP演算法可能不會比暴力法快多少。原因在於很少有文件具備重複的內容,而且字串P的內容也很少有重疊的樣式。KMP法在搜尋存放在硬碟的大型文件時,還是有顯著的好處。因為索引i不會遞減的特性,就可以減少在搜尋字串時,存取硬碟的次數.

沒有留言:

張貼留言

網誌存檔