淺談KMP模式匹配算法及研究

1、淺談KMP模式匹配算法及研究               在計算機科學(xué)領(lǐng)域，串的模式匹配（以下簡稱為串匹配）算法一直都是研究焦點之一。在拼寫檢查、語言翻譯、數(shù)據(jù)壓縮、搜索引擎、網(wǎng)絡(luò)入侵檢測、計算機病毒特征碼匹配以及DNA序列匹配等應(yīng)用中，都需要進行串匹配。串匹配就是在主串中查找模式串的一個或所有出現(xiàn)。在本文中主串表示為S=s1s2s3sn，模式串表示為T=t1t2tm。串匹配從方式上可分為精確匹配、模糊匹配、并行匹配等，著名的匹配算法有BF算法、KMP算法

2、、BM算法及一些改進算法。本文主要在精確匹配方面對KMP算法進行了討論并對它做一些改進以及利用改進的KMP來實現(xiàn)多次模式匹配。 1  KMP算法    最簡單的樸素串匹配算法(BF算法)是從主串的第一個字符和模式串的第一個字符進行比較，若相等則繼續(xù)逐個比較后續(xù)字符，否則從主串的第二個字符起再重新和模式串的第一個字符進行比較。依次類推，直至模式串和主串中的一個子串相等，此時稱為匹配成功，否則稱為匹配失敗。樸素模式匹配算法匹配失敗重新比較時只能向前移一個字符，若主串中存在和模式串只有部分匹配的多個子串，匹配指針將多次回溯，而回溯次數(shù)越多算法的效率越低，它的時

3、間復(fù)雜度一般情況下為O(n-m+1)m) （注：n和m分別為主串和模式串的長度），最壞的情況下為O(m*n)，最好的情況下為O(m+n)。KMP模式匹配算法正是針對上述算法的不足做了實質(zhì)性的改進。其基本思想是：當(dāng)一趟匹配過程中出現(xiàn)失配時，不需回溯主串，而是充分利用已經(jīng)得到的部分匹配所隱含的若干個字符，過濾掉那些多余的比較，將模式串向右“滑動”盡可能遠的一段距離后，繼續(xù)進行比較，從而提高模式匹配的效率，該算法的時間復(fù)雜度為O(m+n)。     那么如何確定哪些是多余的比較？ 在KMP算法中通過引入前綴函數(shù)f(x)來確定每次匹配不需要比較的字符，保證了匹配始終向前進

4、行，無須回溯。假設(shè)主串為s1s2，sn.，模式串為t1t2，tm.，其中 mn，從si+1開始的子串遇到一個不完全的匹配，使得：               (1.1)     如果我們能確定一個最小的整數(shù) ，使得：              (1.2)     其中 ，所以確定

5、i' 等價于確定k，這里的k值就是我們要求的前綴函數(shù)f(x)。由式1.1和1.2中K值與主串s無關(guān)，只與給定的模式串t中與主串匹配的q有關(guān)，即k=f(q)， f(q)=maxi|0 i q且t1.i是t1.q的后綴   (1.3)     確定KMP前綴函數(shù)的算法如下 ： #define MAXSIZE  100 Typedef unsigned char  stringMAXSIZE+1;/0號單元用來存放串的長度 void f(sstring  t, int *array)  

6、60;  m=t0;/m為當(dāng)前模式串的長度     array=(int  *)malloc(m+1)*sizeof(int);/0號元不用     array1=0;k=0;     for(q=2;q<=m;q+)         while(k>0&&tk+1!=tq)k=arrayk;         

7、     if(tk+1=tq)k=k+1;             arrayq=k;              關(guān)于KMP算法的前綴函數(shù)f(x)的示例見表1。      表1  模式串a(chǎn)baabcac I12345678Tiabaabcacf(i)00112010 

8、        當(dāng)模式串中有i個字符串匹配成功，第i+1個字符不匹配時，則從i-f(i)個字符重新開始比較，這樣不僅無須回溯，而且一次可以向前滑動i-f(i)個字符，大大提高了模式匹配的效率。下面給出樸素匹配算法和KMP匹配算法的比較，見表2。 表2 樸素匹配算法和KMP匹配算法比較表  樸素算法KMP算法時間復(fù)雜度O(n-m+1)m)O(m+n)向前移動字符個數(shù)1q-f(q)回溯次數(shù)q-1無    其中：n為主串長度，m為模式串長度，q為匹配成功的字符個數(shù)。  &

9、#160; 2  KMP算法的改進     在KMP算法的實際應(yīng)用中，發(fā)現(xiàn)該算法也存在著不足，結(jié)合下面的表一來論述KMP模式匹配算法的改進。假設(shè)模式串前4個字符與主串的第i+1.i+4匹配成功，第5個字符匹配失敗，此時前綴函數(shù)f(4)=1，下一次匹配將從第i+4開始，并直接將模式串中的第2個字符與主串中的第i+5個字符進行比較，從表1中可知，匹配必將失敗，此次比較是多余的。這說明此時的前綴函數(shù)f(x)并不是最優(yōu)，需要對前綴函數(shù)進行改進。實質(zhì)上，所謂對KMP算法的改進就是對其前綴函數(shù)的改進。     從表1可以看出，

10、當(dāng)t5與主串中的si+5不匹配時，t4+1=tf(4)+1此時f(4)=1，即t5=t2，所以下一次匹配可以跳過i+4-f(f(4)=i+4個字符進行匹配，修改后的前綴函數(shù)記為         實現(xiàn)此前綴函數(shù)的算法是先調(diào)用f()函數(shù)，根據(jù)1.4式對前綴函數(shù)進行修改，算法如下： Void   ff(sstring  t, int *array)      m=t0;      f (t，a

11、rray);     for(q=1 ;q<=m;q+)                  k=fq;            while(k>0&&t k+1=tq+1)           

12、  k=fk;             fq=k            表3 模式串a(chǎn)baabcac關(guān)于改進KMP算法的前綴函數(shù)ff(x)的示例 I12345678Tiabaabcacff(i)00102010        兩表做比較可以發(fā)現(xiàn)：f(4)=1>ff(4)=0  

13、60;  如果前4個字符匹配成功，而第5個字符匹配失敗，那么改進后的重新匹配次數(shù)要減少一次，提高了效率。 3  利用改進算法實現(xiàn)多次模式匹配    在實際應(yīng)用中，模式串與主串一般要進行多次匹配，以便找到在主串含有多少個這樣的子串，典型的應(yīng)用就是在數(shù)據(jù)庫中的查找。例如輸入某人的姓名，然后在姓名這一主串內(nèi)查找有多少個這樣的子串。下面結(jié)合前綴函數(shù)ff(x)的求解算法給出多次模式匹配的算法： void  match(string s，string t, int a)      n=s0;/主串的長度 &

14、#160;   m=t.0;/模式串的長度     ff(t，f)/求出模式串中各個字符的前綴函數(shù)ff(x)     d=0;/該變量用來統(tǒng)計與模式串匹配成功的子串的個數(shù)     q=0/該變量表示模式串中與主串匹配成功的字符的個數(shù) for(i=1;i<=n;i+)         while(q>0&&tq+1!=si)       &#

15、160;q=fq;       if(tq+1=si)  q=q+1;       if(q=m) d=d+1;   ad=i-m+1;   4  結(jié) 語    本文給出的算法較樸素匹配算法在效率上有了較大的提高，尤其是對重復(fù)字符出現(xiàn)較少的數(shù)據(jù)段進行模式匹配可取得較高的查找效率。應(yīng)用于大型數(shù)據(jù)庫的數(shù)據(jù)查詢，會更加有效地縮短查找時間。 參考文獻1嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)M.清華大學(xué)出版社， 2001 2傅清祥，王曉東.

16、算法與數(shù)據(jù)結(jié)構(gòu)M電子工業(yè)出版社，1998 3D.Wood，DataStructures，AlgorithmsAndPerfomance，Reading，MA:AddisonWesley，1993 4onnetGH.HandbookofAlgorithmsAndDataStructureM.Addison-WesleyPublishingCompany,1999   “淺談KMP模式匹配算法及研究”版權(quán)歸作者所有，轉(zhuǎn)載請著名出處。    一、概述    本設(shè)計針對目前暖氣泄漏檢測的現(xiàn)狀及其存在的主要問題，設(shè)計了一種基于AT89

17、C51單片機的多路溫度巡檢系統(tǒng)，采用DALLAS公司的單總線智能溫度傳感器DS18B20來采集溫度采集，采用ATMEL公司生產(chǎn)的的低功耗CMOS串行EEPROM AT24C02來進行采集數(shù)據(jù)的保存，采用T6963C液晶控制器來進行采集溫度的顯示，并通過自定義的鍵盤對本系統(tǒng)進行控制。二、電路設(shè)計（一）測溫電路的設(shè)計本設(shè)計是用七個 DS18B20 組成的測溫電路，DS18B20 的主要特性：適應(yīng)電壓范圍更寬，電壓范圍：3.05.5V，在寄生電源方式下可由數(shù)據(jù)線供電；獨特的單線接口方式，DS18B20在與微處理器連接時僅需要一條口線即可實現(xiàn)微處理器與 DS18B20 的雙向通訊；DS18B20支持多

18、點組網(wǎng)功能，多個 DS18B20可以并聯(lián)在唯一的三線上，實現(xiàn)組網(wǎng)多點測溫；DS18B20在使用中不需要任何外圍元件，全部傳感元件及轉(zhuǎn)換電路集成在形如一只三極管的集成電路內(nèi)；溫度范圍-55+125，在-10+85時精度為±0.5；可編程的分辨率為 912 位，對應(yīng)的可分辨溫度分別為 0.5、0.25、0.125和 0.0625，可實現(xiàn)高精度測溫；在 9 位分辨率時最多在 93.75ms 內(nèi)把溫度轉(zhuǎn)換為數(shù)字，12 位分辨率時最多在 750ms 內(nèi)把溫度值轉(zhuǎn)換為數(shù)字，速度更快；測量結(jié)果直接輸出數(shù)字溫度信號，以“一線總線”串行傳送給 CPU，同時可傳送 CRC 校驗碼，具有極強的抗干擾糾錯能

19、力；負壓特性：電源極性接反時，芯片不會因發(fā)熱而燒毀，但不能正常工作。（二）存儲器電路的設(shè)計由于單片機內(nèi)部的存儲容量有限，又由于本設(shè)計所要儲存的數(shù)據(jù)大于單片機內(nèi)部的存儲容量，所以說外擴一個存儲器對本設(shè)計而言是非常必要的。本設(shè)計采用 ATMEL 公司生產(chǎn)的的低功耗CMOS串行EEPROM AT24C02來進行采集數(shù)據(jù)的保存，它內(nèi)含256×8位存儲空間，具有工作電壓寬（2.55.5V）、擦寫次數(shù)多（大于 10000 次）、寫入速度快（小于 10ms）等2特點，24C02采用的 I C 總線，它通過 SDA（串行數(shù)據(jù)線）及 SCL（串行時鐘線）兩根線在連到總線上的器件之間傳送信息，并根據(jù)地址

20、識別每個器件。（三）按鍵電路的設(shè)計 鍵盤是單片機應(yīng)用系統(tǒng)中一個至關(guān)重要的部件。它能實現(xiàn)輸入數(shù)據(jù)、傳送命令等功能，是人工干預(yù)計算機的主要手段。鍵盤可分為編碼鍵盤和非編碼鍵盤兩種。前者用軟件來識別和產(chǎn)生代碼，后者用硬件來識別。（四）顯示電路的設(shè)計LCD顯示器有分段式和點陣式兩種結(jié)構(gòu)。點陣式是在上下兩個電極基板上噴上大小和間隔相等、上下對應(yīng)的電極點陣。其中上電極基板上的每個電極對外均有引線，用于接驅(qū)動電壓，而下電極基板上的所有電極均接到一個公共電極 COM 上，電極由二氧化錫透明導(dǎo)電材料組成。點陣式可用于文字、圖形以及數(shù)字顯示。分段式 LCD 顯示器與 LED 顯示器相似，也采用七段式顯示。不同的是 LCD 顯示器的結(jié)構(gòu)除在上電極基板上噴上 ag 這七個