KMP算法的FPGA實現(xiàn)-科技大學(xué)本科畢業(yè)設(shè)計

1、本科畢業(yè)設(shè)計（2011 屆）題目 kmp算法的fpga實現(xiàn)學(xué)院電子信息學(xué)院專業(yè)集成電路設(shè)計與集成系統(tǒng)班 級學(xué) 號學(xué)生姓名指導(dǎo)教師 完成日期誠信承諾我謹(jǐn)在此承諾：本人所寫的畢業(yè)論文kmp算法的fpga實現(xiàn)均 系本人獨立完成，沒有抄襲行為，凡涉及其他作者的觀點和材料，均 作了注釋，若有不實，后果由本人承擔(dān)。承諾人（簽名：隨著網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展，所要檢測的數(shù)據(jù)包越來越多，單純的依靠軟件來 檢測，越來越顯得力不從心。伴隨著fpga技術(shù)的發(fā)展，在碩件上實現(xiàn)模式匹配， 來提高網(wǎng)絡(luò)數(shù)據(jù)處理速度的需求越來越普遍。把搜索算法固化到fpga里，從而可 以大大提高算法的速度，適應(yīng)科技的迅速發(fā)展。本文重點分析了幾種典

2、型的模式匹配算法。包括：bf算法、kmp算法、bm算法、 bmh算法、ac算法和ac-算法。另外文章還介紹了fpga的的相關(guān)基木知識以及硬 件描述語言的選擇。綜合考慮現(xiàn)有的比較成熟的模式匹配算法，并且追蹤國外基于fpga技術(shù)來實 現(xiàn)模式兀配的研究成果，認(rèn)為在硬件實現(xiàn)方面，kmp算法效率較高，結(jié)構(gòu)簡單，可 行性強，而且易于對主串進行多模式的匹配，所以選其作為模式匹配硬件模塊的 核心算法，通過便線邏輯來進一步提高串模式匹配的效率。本文kmp算法程序設(shè)計 部分主要分為三個部分：模式串輸入、next函數(shù)的計算、字符串的匹配。具體情 況會在第四章中介紹。關(guān)鍵詞：模式兀配算法；kmp算法；fpgaabst

3、ractwith the rapid development of network technology, have to text more and more packets. thus, simply relying on software to detect becomes more and more inadequate.as the development of fpga technology, it" s becomes increasingly popular to realize the pattern matching on hardware to meet the

4、 demand for the improvement of the processing speed of network data. putting the search algorithm to the fpga, which can greatly improve the speed of the algorithm, is adapt to the quick development of technology.this paper focuses on several typical patterns matching algorithm involving: bf algorit

5、hm, kmp algorithm, bm algorithm, bmh algorithm, ac algorithm and the ac-bm algorithm.besides, this paper will also introduce the basic knowledge related to fpga as well as the selection of the description language of hardware.considering the current pattern matching algorithms which are relatively t

6、hrough and the reseaching findings from abroad of using fpga to achieve pattern mactching, kmp has advantages of efficient arithmetic, simple organization, strong feasibility and easy multi-pattern macthing to primary string in realizing hardware.that!s the reason why choose it to be the core arithm

7、etic of matching pattern and hardware module, which makes further improvement on effiency of pattern maching in string by via hard wire logic.this part of kmp algorithm programming is divided into three parts: the pattern string entered, next function calculation, string matching. the circumstances

8、described in the fourth chapter.key words： pattern matching algorithm； kmp algorithm； fpga目 錄第1章引言111研究背景112模式匹配算法的發(fā)展與研究現(xiàn)狀1第2章 模式兀配算法32.1模式匹配定義32. 2單模式匹配32. 2. 1bf 算法32. 2. 2kmp 算法42. 2. 3bm 算法62. 2. 4bmh 算法72. 3多模式匹配72. 3. 1ac 算法72. 3. 2ac-bm 算法82. 4影響模式匹配算法的因素9第3章fpga基本的知識103. 1fpga簡介103. 2fpga與cp

9、ld的關(guān)系以及工作原理103. 3硬件語言選擇11第4章kmp算法veriloghdl實現(xiàn)134.1模式串輸入134. 2next函數(shù)的計算144. 3字符串兀配184. 4代碼通用性的驗證21第5章結(jié)束語26致謝27附錄30第偉引言研究背景在網(wǎng)絡(luò)處理中，模式匹配是指將分組各域進行比特位的匹配處理。一般，模 式匹配模塊有兩個輸入，一個是規(guī)則的模式表達(dá)式，另一個是分組域。它的輸出 是輸入分組的各域是否與輸入模式的布爾值兀配。這類模式兀配的實質(zhì)還是字符 串匹配，它的基本運算就是從一個主字符串中找到某個特定模式串出現(xiàn)的位置。目前，串匹配算法一般是以模式串的長度為掃描窗口大小，在窗口中使用不 同的掃描

10、策略來進行匹配。假設(shè)模式串長為ni,主串長為n,串兀配算法根據(jù)策略 的不同，大致可以分為以下3類：從前往后匹配模式前綴的kmp算法，從后往前 匹配模式后綴的bm算法及其各種變形，以及從后往前匹配模式前綴的rf算法等等。kmp算法是從前往后進行掃描，使用自動機記住己匹配模式前綴的正文內(nèi)容, 并依據(jù)這些內(nèi)容來確定是否已經(jīng)匹配成功。換句話說，就是先對模式串進行預(yù)計 算，然后再與主串匹配，而且主串不需要回溯，它的吋間復(fù)雜度比較好，一般是 0(m+n) o bm算法及其變形是在掃描窗口中從后往前進行掃描，記住已兀配模式后 綴的正文內(nèi)容，并依據(jù)這些內(nèi)容來進行窗口移動，這種方法雖然簡單易行，但是 時間復(fù)雜度

11、比較差，最壞情況下為0(m+n),所以當(dāng)串比較長吋，效率就會很低。rf算法等是在從后往前進行掃描時，反向使用模式逆串的后綴自動機來兀配 模式的前綴，這樣可以增大窗口移動的距離，從而獲得更好的平均時間復(fù)雜度， 達(dá)到理論最優(yōu)結(jié)果。該方法效率較高，但是比較復(fù)雜，硬件實現(xiàn)難度大。綜合考慮現(xiàn)有的比較成熟的模式兀配算法，認(rèn)為在硬件實現(xiàn)方面，kmp算法具 有其他算法沒有的優(yōu)勢，所以本文選擇kmp算法作為研究的主要對象。2模式匹配算法的發(fā)展與研究現(xiàn)狀兇bf算法是最早提出來的模式兀配算法，也是最簡單的一個算法。該算法的最 壞時間復(fù)雜度為o(m*n)。1970年，sa. cook從理論上證明了串匹配問題可以在0(

12、m+n) oj*間內(nèi)解決， 同一年，morris和pratt仿照cook的證明構(gòu)造了一個算法，隨后，knuth對這個算 法進行了一些改進，在1976年，knuth提出了第一個在線性時間內(nèi)解決字符串的模 式匹配算法，這個算法被稱為kmp算法它的吋間復(fù)雜度為own) o1977年，boyer和moore提出了另一個與kmp算法截然不同的卻同樣擁有線性時 間復(fù)雜度的算法(bm算法)。bm算法在實際的模式匹配中，跳過了很多無用的字符, 這種跳躍式的比較方式，使bm算法獲得了極高的效率，特別是在大字符集上進行 字符串的模式兀配時。在實際的應(yīng)用中，bm算法比kmp算法更有效率。多模式匹配是另一個研究熱點。

13、aho-corasie算法(ac算法)是第一個在0(n)± 解決這個問題的算法。ac算法可以被看作是kmp算法的更一般化形式。此后，bm算 法跳躍的思想也被應(yīng)用到了多模式匹配上，1979年comments .walter提出了一種 新的多模式匹配算法，稱為cw算法，這個算法將ac算法和bm算法的思想結(jié)合起來, 獲得了更好的執(zhí)行效率。沿著ac算法這條路線，crochemore等人將ac算法和dawg 結(jié)合，獲得了一種新的算法，稱為dawg71atch。實驗結(jié)果表明，該算法比 comment s-wal ter的算法更有效率。此外，人們還提搬了其它一些多模式匹配算法。1994年，sun

14、wu和lanber提 岀了第一個基于過濾思想的多模式匹配算法。這個算法將過濾思想和bm思想結(jié)合 起來，在實際的應(yīng)用中獲得了極其高的效率。實驗表明，在sun sparc 10±,他們 的算法可以于10秒內(nèi)完成在15. 8m的文本中搜索10000個模式的工作。在wm算法的 基礎(chǔ)上，sun wu和manber實現(xiàn)了一個用丁模糊匹配的工具agrep和一個文本檢索的 工具glimpse,在實際的應(yīng)用中都獲得了良好的效率。1996年，robert muth和udi manber給岀了一個快速的多模式模糊匹配算法， 這個算法也是基于過濾的思想，同時采用了兩級散列的技術(shù)，從而獲得了極高的 執(zhí)行效率，

15、實驗數(shù)據(jù)表明，該算法能在小于1秒的時間內(nèi)完成在1m文本中對1000個 模式的搜索和模糊匹配的過程。但是不幸的是，該算法只允許模式和文本子串之 間存在1個不同點，這樣的約束限制了該算法在實際中的應(yīng)用。1999年，在數(shù)據(jù)壓縮和位操作的思想上，sun kim和yanggon kim設(shè)計出了一 個新的多模式匹配算法，實驗證明，該算法比sun wu和manber的算法有更好的表 現(xiàn)，特別是在小字符集上。目前對模式匹配算法的研究一部分還停留在單模式匹配算法，而對多模式匹 配算法的研究主要集中在算法的綜述、測試以及對現(xiàn)有算法的一些相應(yīng)改進上。 這些改進的算法雖然也取得一定的成果，但是總體效果都不是很理想，主

16、要是算 法速度受限于模式的數(shù)目或者實現(xiàn)算法需耍的空間消耗的內(nèi)存太大。字符串的模糊匹配是近年來倍受關(guān)注的領(lǐng)域，模糊匹配允許在搜索時搜索出 與模式有一些差別的文本中的字符串。在這個領(lǐng)域，有四條主要的技術(shù)路線： 動態(tài)規(guī)劃算法；自動機算法；過濾算法；位并行算法。由于這不是本文研 究的主耍內(nèi)容，故不做詳細(xì)介紹。第2章模式匹配算法模式匹配分為單模式兀配和多模式兀配，一次在文木串中查找一個模式串出 現(xiàn)的過程，稱為單模式匹配。同吋查找一個模式串集合中的所有模式串的出現(xiàn)的 過程稱為多模式匹配。木章主要討論幾種典型的單模式兀配算法和多模式兀配算法。2.1模式匹配定義字符串的模式匹配問題的形式化定義如下：在字符集工

17、上，給定一個長度為n的文木字符串t1n,以及一個長度為m的 模式字符串p1e1-m。模式集數(shù)量用k來表示，模式集用p=pl, p2，pk來表 示。如果對于1<=s<=n,存在ts+1s+m二pilm,則模式pi在文本t的位置s處 出現(xiàn)，即模式與文木匹配。字符串的模式匹配問題就是要尋找p在t中是否出現(xiàn)， 以及岀現(xiàn)的位置。例如：文本字符串t： here is a beauterful picture模式字符串p： beauterful該例子顯示需要在文本字符串t中搜索模式字符串p： "beauterful",通過搜 索我們發(fā)現(xiàn)模式字符串p： “beauterful”

18、岀現(xiàn)在文本字符串t中第11位，那么我們 稱模式字符串p與文木字符串t兀配成功。2. 2單模式匹配2.2. 1bf 算法bf算法即brute force算法的縮寫。是蠻力算法的意思，實際上是原理和邏輯 最簡單的算法.這個算法在字符中規(guī)模較小的吋候，還是能夠取得較好的效益。bf算法就是把模式串和文本串的所有窗口逐一進行比較。如果當(dāng)前字符相同 而h模式串結(jié)束則匹配成功如果字符相同而模式串未結(jié)束就比較下一個字符： 如果字符不相同，則窗口向后移動一個字符位置，模式串和新窗口從開始字符重 新比較。對于文本字符串tltktjtm-k-lt n模式字符串plpipm算法描述：(1) p和t從左端對齊，使得p1

19、與t1對齊；(2) 從左到右匹配p與t的字符，直到出現(xiàn)不匹配的情況或是p已被完全匹配：(3) 如果出現(xiàn)不匹配的情況，則將p右移一個字符，重新開始匹配；(4) 重復(fù)上述過程，盲到p被完全兀配，或p移到t的右端。每次模式串和某個窗口比較次數(shù)應(yīng)該是0(m),而窗口的個數(shù)是0 (n-m)個。 因此算法最壞情況的時問復(fù)雜度是0(mn)。最壞情況的例子之一是文本串是某一相 同字符的字符串而模式串也是這一字符的字符串。這種算法的缺陷是匹配過程 中帶有回溯，準(zhǔn)確地說是當(dāng)匹配不成功的時候，之前進行的匹配完全變?yōu)闊o效的, 所有的比較需要從模式串首字符重新開始。bf算法的優(yōu)點是不需要預(yù)處理。輔助的空間是常量，即只需

20、要幾個變量的臨 時存儲區(qū)域。模式串和某個窗口內(nèi)匹配的順序是任意的，向左或者向右都是可以 的。2. 2. 2kmp算法kmp算法是knuth等人在bf算法的基礎(chǔ)上提岀來的。從本質(zhì)上講，kmp算法就是 岀現(xiàn)不匹配情況下帶有智能指針初始化的bf算法。為了在不匹配時重新定位指針, kmp算法需耍進行預(yù)處理算出一個shift表來?；舅枷耄簁1p算法利用已匹配成功部分的信息，即前綴(模式字符串中存在 的相同子串)，可以使模式字符串向前推進若干個字符位置，而不只是一個字符， 避免了重復(fù)比較，同時也實現(xiàn)了文本字符串指針的無回溯。要點是：我們能夠通 過預(yù)先對模式的分析獲得知識，即如果在模式的位置1或2匹配失敗

21、則移動1個位 置，如果在模式的位置3匹配失敗則移動2個位置，如果在模式的位置4匹配失敗則 移動3個位置，以此類推。算法描述叫當(dāng)模式匹配執(zhí)行到比較字符ti和pi,其中l(wèi)=i=n, l=j=nio(1) 若ti二pj則繼續(xù)往右作匹配檢測，即對ti+1和pj+1；進行匹配檢測。(2) 若tihpj時則分兩種情況進行討論：第一種情況：若j=l,則對ti+1和pi進行匹配檢測，即把模式和正文向右移動 一位再從模式的第一個字符進行匹配。第二種情況：若l<j=m,我們將試圖在模式中找到一個合適位置再進行比較， 我們把這個下標(biāo)記做nextj o執(zhí)行ti和nextj的匹配，其中next j的構(gòu)造是算 法的

22、核心，約定如下：nextj=-1,當(dāng)j二0時nextj=max k|0<k<j且 “p0 plpk-l” = “pj-k pj-k+lpj-1 ”此集合 不為空集nextj=0,其他情況由于本文主講的是kmp算法，估計我們舉例詳細(xì)說明，如主串為 ababcabcacbab,模式串為abcac,匹配過程如下圖2-1:1 i=2第1次匹配：a blalb cabcacbab a blcla c仃2第2次匹配,"4第3次匹配:i j=6圖2-1一般情況下，假設(shè)主串為sosisn_i，模式串為內(nèi)0燦t，從上例的分析可知, 為了實現(xiàn)改進算法，需要解決下述問題：當(dāng)匹配過程中產(chǎn)生“失配

23、”(即 時，模式串“向右滑動”可行的距離有多遠(yuǎn)，換句話說，當(dāng)主串中字符s與模式 中字符 “失配”(即比較不等)時，主串中字符s (/指針不回溯)應(yīng)與模式 中哪個字符再比較？假設(shè)此時主串中字符si應(yīng)與模式中字符幾(k<j)繼續(xù)比較，則模式中字符 前面斤個字符的子串必須滿足下列關(guān)系式(f-1),且不存在kf>k滿足下列關(guān)系 式(f-1)pp *a-i = si-ksj-kt s,-i(f1)apl加a reprmpriiprl a-iia$ ji-h r* r»rt圖2-2模式串與主串的對應(yīng)關(guān)系一(f-2)當(dāng)主串中字符si與模式中字符匕“失配”吋，已經(jīng)得到的“部分”匹配結(jié)果

24、是：pzp* pj- 二 sis* s/-1 reph r 1 rep譏pie r opt/zz5)51 r«5十£-s'j-hl r i r«a f ra5rl圖2-3模式串與主串的對應(yīng)關(guān)系二由(f-1)和(f-2)推得下列等式aa *a-i = pj-p* 卩戸(f-3)我們稱"wpm為"氏p6pj2pj(的前綴子串,"pj4*pj(為 "aaa php的后綴子串。若模式串中存在真子串p嚴(yán)p屮pf,且滿足q<k<jf則當(dāng)匹配過 程中，主串中字符s與模式中字符匕比較不等時，僅需將模式向右滑動至模式中 第

25、斤個字符和主串中字符s對齊，此時，模式中頭斤個字符的子串f 兄必定 與主串中字符s之前長度為斤的子串”sggs匯相等。由此，匹配僅需從模式 中尤與主串中字符s比較起繼續(xù)進行。若令nextu=k則nextlj表明當(dāng)模式中第丿個字符與主串中相應(yīng)字符“失 配”時，在模式中需重新和主串中該字符進行比較的字符的位置。由此就可以得 出前面next函數(shù)的求值方法。kmp算法搜索階段在最壞的情況下時聞復(fù)雜度為o(n*m)，但在一般情況下，其 實際的執(zhí)行時間近似于0(n+m), shift表的存在需要額外的空間為0(m)o在大多數(shù) 情況下，kmp算法并不比bf算法好很多，但kmp算法確保了線性，并且其擴展性適

26、合求解更難的問題，尤其是因為kmp算法不需要回溯，在處理從外設(shè)讀入的龐大文 件時，這種特性很有價值。2. 2. 3bm 算法bm算法是由boyer和loore于1977年提出，該算法是目前應(yīng)用最為廣泛的單模 式匹配算法。bm算法的一個最主要的特點是，在對字符串的匹配過程中，可以跳 過很多無用的字符，即不對無用的字符進行匹配。通過這種跳躍式的匹配，獲得 了較高的執(zhí)行效率。有實驗數(shù)據(jù)表明，bm算法的匹配速度大約是kmp算法的35倍。 bm算法描述何：第一步：預(yù)處理，算法根據(jù)預(yù)先計算好的兩個數(shù)組將模式字符串向右移動盡 可能遠(yuǎn)的距離。計算skip：數(shù)組和shift：數(shù)組，分別代表bc規(guī)則和gs規(guī)則。第

27、二步：從右向左逐個字符比較文本字符串和模式字符串，單個字符匹配則 繼續(xù)比較。如果到達(dá)模式字符串的最左邊，則成功發(fā)生了匹配，輸出；如果發(fā)生 字符失配，則轉(zhuǎn)第三步。第三步：取失配字符相應(yīng)的skip數(shù)組和shift數(shù)組中的數(shù)值最大的一個， 作為移動距離，將模式字符串右移。如果己到達(dá)文本字符串的末尾，則退出算法; 否則轉(zhuǎn)回到第二步執(zhí)行。算法被設(shè)計成為在文本中搜索單一模式字符串的算法，在單一模式的字符 串匹配算法中，bm算法一般被認(rèn)為是性能最佳的。而在內(nèi)容過濾和檢測中有很多 種關(guān)鍵詞模式需要匹配，因此bm算法需要對每一種模式分別進行匹配。旳1算法的 預(yù)處理階段的時間空間復(fù)雜性是0(m+n),查找階段的時

28、間復(fù)雜性是0(mn),查找非 周期性模式時的最壞情況下比較次數(shù)是3n。bm算法最壞時間復(fù)雜度是0(mn),最好 時間復(fù)雜度是0(n)。對多模式字符串進行匹配，直接采用bm算法的復(fù)雜度是0(kn)obm算法需要預(yù)處理.也需要輔助空問.邏輯上也相對比較復(fù)雜。但是整個算 法執(zhí)行的效率相對較高。如果字符越多，效率越高。因此旳1算法在漢字文本串匹 配效率要高于英文文本串的匹配。2. 2. 4bmh算法它是對bm算法的改進，思想是通過目標(biāo)串和模式串中字符的最后一個位置對 應(yīng)字符的下一個字符來決定右移的字符個數(shù)。算法描述如下：(1) 模式串從左向右移動，匹配自右向左進行；(2) 若匹配失敗發(fā)生在pjti：,

29、先根據(jù)算法計算出字符ti的位移量，再比 較下一個字符：如果下一個字符出現(xiàn)在模式串中，則移動的距離通過模式串決定。 否則，跳過該字符從下一個字符開始重新比較。依次循環(huán)，直到匹配為止?？梢钥闯?，該算法的最壞情況即為31算法的情況，即右移的字符個數(shù) n二distt,故相對bm算法具有一定的優(yōu)越性。bmh算法預(yù)處理時間復(fù)雜度為0(m+o),空間復(fù)雜度先0(o), o是與pattern. text 相關(guān)的有限字符集長度。查找階段時間復(fù)雜度為0(mn),在一般情況下，bmh算法 比bm有更好的性能，它只使用了一個數(shù)組，簡化了初始化過程。2. 3多模式匹配2.3. 1ac 算法1975年，貝爾實驗室的alf

30、red v. aho和margaret j. corasick提出了著名的 多模式匹配算法一一ac自動機匹配算法(簡稱ac算法)。該算法最早被使用在圖書 館的書目查詢程序中，取得了很好的效果。ac算法描述(例如模式集sp=he, she, his, hers)：預(yù)處理階段，模式樹的各個節(jié)點作為狀態(tài)，根節(jié)點作為初態(tài)，標(biāo)簽為模式的 節(jié)點作為終態(tài)，利用轉(zhuǎn)向函數(shù)g和失效函數(shù)f作為轉(zhuǎn)移函數(shù)，將模式樹擴展成一個 樹型有限自動機。見圖2-4由模式樹擴展所得的ac自動機m是1個6元組：m二(q,工，g, f, qo, f)其中:(1) q是有限狀態(tài)集(模式樹上的節(jié)點)；(2) 工是有窮的輸入字符表(數(shù)據(jù)包中可

31、能出現(xiàn)的所有字符)；(3) g是轉(zhuǎn)移函數(shù)，該函數(shù)定義如下：g(s, a)：從當(dāng)前狀態(tài)s開始，沿著邊上 標(biāo)簽為a的路徑所到的狀態(tài)。假如(u, v)邊上的標(biāo)簽為a,那么g(u, a)=v；如果根 節(jié)點上出來的邊上的標(biāo)簽沒有a,貝ljg(o, a)=0,即如果沒有匹配的字符出現(xiàn)，自 動機停留在初態(tài)；(4) f(不匹配時自動機的狀態(tài)轉(zhuǎn)移)也是轉(zhuǎn)移函數(shù)，該函數(shù)定義如下：f(s)： 當(dāng)w是l(s)最長真后綴并且w是某個模式的前綴，那么f(s)就是以w為標(biāo)簽的那個節(jié) 占八、,(5) qo wq是初態(tài)(根節(jié)點，標(biāo)識符為0)；(6) f量q是終態(tài)集(以模式為標(biāo)簽的節(jié)點集)。這樣，在文本字符串中查找模式字符串的過

32、程轉(zhuǎn)化成在模式樹中的查找過程。 查找一個文本字符串t時從模式樹的根節(jié)點開始，沿著以t中字符為標(biāo)簽的路徑往 下走：若自動機能夠抵達(dá)終態(tài)v,則說明t中存在模式l(v)：否則不存在模式。圖2-4模式樹ac算法模式匹配的時間復(fù)雜度是0(n),并且與模式集中模式字符串的個數(shù)和 每個模式字符串的長度無關(guān)。無論模式字符串p是否出現(xiàn)在文本字符串t中，t中的 每個字符都必須輸入狀態(tài)機中，所以無論是最好情況述是最壞情況，ac算法模式 匹配的時間復(fù)雜度都是0(n),包括預(yù)處理時間在內(nèi)，ac算法總時間復(fù)雜度是 0(m+n),其中m為所有模式字符串的長度總和。ac算法的查找效率明顯高于算法。 但是，ac算法在對文本字符

33、串匹配的過程中沒有跳躍，無法跳過不必要的比較， 并且有限狀態(tài)自動機算法是以空間換時間的經(jīng)典算法，當(dāng)模式集較大時可能產(chǎn)生 內(nèi)存膨脹問題。因此在實際的匹配過程中，ac算法不可能是性能最佳的搜索算法。 2. 3. 2ac-bm算法ac-bm算法是在aho. corasick算法的基礎(chǔ)上，結(jié)合boyer. moore算法的跳躍 思想，產(chǎn)生的一種多模式匹配算法。在一般情況下，由于應(yīng)用了鬪算法的跳躍式 思維，所以不需要對文本的每個字符進行匹配。在算法的基礎(chǔ)上引入了ac算法, 來提高匹配速度，跳過盡可能多的字符，在模式字符串較長和較短的情況下，該 算法都具有很好的性能。ac-bm算法描述：設(shè)模式樹中最短模式

34、串的長度為l,第一次比較是從待匹配的文本字符串的末 端向前取l個字符與模式樹的根字符對齊，然后從樹的根字符開始比較，當(dāng)出現(xiàn)不 匹配的字符時：(1) 若目標(biāo)字符不在任何模式串中，則模式樹偏移量為l位；(2) 移動到另一模式串前綴的下一位置；(3) 將模式樹移動到作為樹中另一個模式后綴能夠正確匹配目標(biāo)串的某個前 綴的下一個位置。要注意的是：ac-bm算法在移動過程中，模式樹移動的偏移量不 能超過最短模式串的長度l。我們設(shè)模式字符串集合中，字符串最小長度minlen, 最大長度為maxlen,待匹配文本長度為n,則在最優(yōu)情況下，時間復(fù)雜度為0(n/ minlen),在最壞情況下，時間復(fù)雜度為o(n*

35、maxlen)。ac-bm算法結(jié)合多模式匹配ac和單模式匹配bm兩種算法的優(yōu)點，既可以同時匹 配多個模式又可以跳過不必耍的字符，因此相比其它模式匹配算法具有較高的性 能和效率。2. 4影響模式匹配算法的因素對于一個模式匹配算法來說，在實際應(yīng)用中，最為關(guān)注的問題有以下幾個方 面1819：(1) 正確性：即誤判率和漏判率，這與模式的選擇是密切相關(guān)的，如果模式的 選擇比較嚴(yán)格，那么誤判率和漏判率一定會下降，但是過于嚴(yán)格的模式會影響識 別的速度；同時過于簡短的模式又會影響誤判率和漏判率，所以耍選擇一個最優(yōu) 的折衷點。(2) 速度：即時間復(fù)雜性，這是評價一個模式匹配算法的重要的標(biāo)準(zhǔn)之一。隨 著網(wǎng)絡(luò)速度的

36、提高，通常要求模式匹配能以線速率執(zhí)行，特別是在一些實時性的 系統(tǒng)中，對模式匹配的速度有很高的耍求。一般情況下算法的時間復(fù)雜性，首先 是預(yù)處理時間復(fù)雜性，其次是匹配過程中的時間復(fù)雜性，最后是最壞情況和最好 情況下的時間復(fù)雜性，特別是最壞情況下的復(fù)雜性，是算法研究中的一個重要方 面。而在上述三種情況的時間復(fù)雜性中，模式的因素都是一個不可缺少的原因。 簡潔有效的模式不僅可以降低預(yù)處理的時間復(fù)雜度，而且述能縮短匹配過程的時 間，至于最壞和最好的時間復(fù)雜度，在很大程度上受控于模式的規(guī)模。所以若要 提高算法的速度，提高模式的有效性是一個重耍途徑。(3) 資源消耗：在模式的預(yù)處理階段和模式匹配階段，對內(nèi)存的

37、需求也是應(yīng)用 中關(guān)注的重要問題之一，盡管目前內(nèi)存的容量提高了很多，但是龐大的內(nèi)存占有 量會減慢算法的速度，所以現(xiàn)在人們常常借助于硬件實現(xiàn)算法。第3章fpga的基本知識木章主要介紹fpga的基木概念，fpga與cpld的關(guān)系，硬件描述語言的選擇。3. 1fpga簡介fpga （fieldprogrammable gate array）,即現(xiàn)場可編程門陣列，它是在 pal、 gal、cpld等可編程器件的基礎(chǔ)上進一步發(fā)展的產(chǎn)物。它是作為專用集成電路 （astc）領(lǐng)域中的一種半定制電路而出現(xiàn)的，既解決了定制電路的不足，又克服 了原有可編程器件門電路數(shù)有限的缺點。目前以硬件描述語言（verilog或v

38、hdl）所完成的電路設(shè)計，可以經(jīng)過簡單 的綜合與布局，快速的燒錄至fpga上進行測試，是現(xiàn)代ic設(shè)計驗證的技術(shù)主 流。這些可編輯元件可以被用來實現(xiàn)一些基本的邏輯門電路（比如and、or、xor、 not）或者更復(fù)雜一些的組合功能比如解碼器或數(shù)學(xué)方程式。在大多數(shù)的fpga里 面，這些可編輯的元件里也包含記憶元件例如觸發(fā)器（flip flop）或者其他更 加完整的記憶塊。系統(tǒng)設(shè)計師可以根據(jù)需要通過可編輯的連接把fpga內(nèi)部的邏輯塊連接起來， 就好像一個電路試驗板被放在了一個芯片里。一個出廠后的成品fpga的邏輯塊和 連接可以按照設(shè)計者而改變，所以fpga可以完成所需要的邏輯功能。fpga-般來說比

39、asic （專用集成芯片）的速度要慢，無法完成復(fù)雜的設(shè)計, 而且消耗更多的電能。但是他們也有很多的優(yōu)點比如可以快速成品，可以被修改 來改正程序中的錯誤和更便宜的造價。廠商也可能會提供便宜的但是編輯能力差 的fpgao因為這些芯片有比較差的可編輯能力，所以這些設(shè)計的開發(fā)是在普通的 fpga上完成的，然后將設(shè)計轉(zhuǎn)移到一個類似 于asic的芯片上。另外一-種方法是 用cpld （復(fù)雜可編程邏輯器件備）。3. 2fpga與cpld的關(guān)系以及工作原理cpld與fpga的關(guān)系：早在1980年代中期，fpga已經(jīng)在pld設(shè)備中扎根。cpld和fpga包括了一些 相對大數(shù)量的可編輯邏輯單元。cpld邏輯門的密

40、度在幾千到幾萬個邏輯單元之間, 而fpga通常是在幾萬到幾百萬。cpld和fpga的主要區(qū)別是他們的系統(tǒng)結(jié)構(gòu)。cpld是一個有點限制性的結(jié)構(gòu)。 這個結(jié)構(gòu)由一個或者多個可編輯的結(jié)果之和的邏輯組列和一些相對少量的鎖定 的寄存器。這樣的結(jié)果是缺乏編輯靈活性，但是卻有可以預(yù)計的延遲吋間和邏輯 單元對連接單元高比率的優(yōu)點。而fpga卻是有很多的連接單元，這樣雖然讓它 可以更加靈活的編輯，但是結(jié)構(gòu)卻復(fù)雜的多。cpld和fpga另外一個區(qū)別是大多數(shù)的fpga含有高層次的內(nèi)置模塊(比如加 法器和乘法器)和內(nèi)置的記憶體。一個因此有關(guān)的重要區(qū)別是很多新的fpga支持 完全的或者部分的系統(tǒng)內(nèi)重新配置。允許他們的設(shè)計

41、隨著系統(tǒng)升級或者動態(tài)重新 配置而改變。一些fpga可以讓設(shè)備的一部分重新編輯而其他部分繼續(xù)正常運行。fpga的工作原理：(1) 采用fpga設(shè)計as1c電路(專用集成電路)，用戶不需要投片生產(chǎn)，就能 得到合用的芯片。(2) fpga可做其它全定制或半定制as1c電路的中試樣片。(3) fpga內(nèi)部有豐富的觸發(fā)器和i / 0引腳。(4) fpga是asic電路中設(shè)計周期最短、開發(fā)費用最低、風(fēng)險最小的器件之o(5) fpga采用高速chmos工藝，功耗低，可以與cmos、ttl電平兼容?？梢哉f，fpga芯片是小批量系統(tǒng)提高系統(tǒng)集成度、可靠性的最佳選擇之一。fpga是由存放在片內(nèi)ram中的程序來設(shè)置

42、其工作狀態(tài)的，因此，工作時需要 對片內(nèi)的ram進行編程。用戶可以根據(jù)不同的配置模式，采用不同的編程方式。加電時，fpga芯片將eprom中數(shù)據(jù)讀入片內(nèi)編程ram中,配置完成后,fpga 進入工作狀態(tài)。掉電后，fpga恢復(fù)成白片，內(nèi)部邏輯關(guān)系消失，因此，fpga能夠 反復(fù)使用。fpga的編程無須專用的fpga編程器，只須用通用的eprom、prom編程 器即可。當(dāng)需耍修改fpga功能時，只需換一片eprom即可。這樣，同一片fpga, 不同的編程數(shù)據(jù)，可以產(chǎn)生不同的電路功能。因此，fpga的使用非常靈活。fpga有多種配置模式：并行主模式為一片fpga加一片eprom的方式；主從模 式可以支持一

43、片prom編程多片fpga；串行模式可以采用串行prom編程fpga；外 設(shè)模式可以將fpga作為微處理器的外設(shè)，由微處理器對其編程。如何實現(xiàn)快速的時序收斂、降低功耗和成本、優(yōu)化時鐘管理并降低fpga與 pcb并行設(shè)計的復(fù)雜性等問題，一直是采用fpga的系統(tǒng)設(shè)計工程師需要考慮的關(guān) 鍵問題。如今，隨著fpga向更高密度、更大容量、更低功耗和集成更多1p的方 向發(fā)展，系統(tǒng)設(shè)計工程師在從這些優(yōu)異性能獲益的同時，不得不面對由于fpga前 所未有的性能和能力水平而帶來的新的設(shè)計挑戰(zhàn)。3. 3硬件語言選擇verilog hdl與vhdl是兩種最常見的硬件描述語言,verilog hdl與vhdl相 比有以

44、下一些優(yōu)點：(1) 可以用來進行各種層次的邏輯設(shè)計，也可以進行數(shù)字系統(tǒng)的邏輯綜合、仿 真驗證和時序分析等。verilog hdl適合算法級(algorithm) 寄存器傳輸級(rtl) > 邏輯級(logic)、門級(gate)和版圖級(layout)等各個層次的設(shè)計和描述。(2) vhdl偏重于標(biāo)準(zhǔn)化考慮，而verilog hdl與eda工具的結(jié)合更為緊密。vhdl 是國際上第一個標(biāo)準(zhǔn)化的hdl語言(ieee-1076),是為了實現(xiàn)美國國防部vhs1c計 劃所推出的各個電子部件供應(yīng)商具有統(tǒng)一的數(shù)據(jù)交換格式的要求。相比之下， verilog hdl則是在全球最大的eda/esda供應(yīng)商c

45、adence公司的扶持下針對eda 工具開發(fā)的hdl語言。(3) 與vhdl相比，verilog hdl的編程風(fēng)格更加簡潔明了，更接近高級計算 機語言的語法形式。有鑒于此，本設(shè)計采用verilog hdl語言作為硬件描述語言。第4章kmp算法ver i i oghdl實現(xiàn)木章主要介紹kmp算法的veriloghdl實現(xiàn)設(shè)計過程，一些調(diào)試碰到的問題及 解決方法。4. 1模式串輸入kmp算法是一種改進的字符串匹配算法，由d. e. knuth與v. r. pratt和 j. h. morris同時發(fā)現(xiàn)，因此人們稱它為克努特一莫里斯一普拉特操作(簡稱kmp 算法)。kmp算法的關(guān)鍵是根據(jù)給定的模式串

46、pattern定義-一個next函數(shù)。next 函數(shù)包含了模式串木身局部兀配的信息。為了用verilog hdl實現(xiàn)kmp算法，我們需要在熟悉算法原理的基礎(chǔ)上進行 程序設(shè)計。kmp算法的原理已經(jīng)在論文的第二章詳細(xì)介紹過，這里就不再累述。40 /模式串輸入/41 always©(posedge elk or negedge rst)42 s begin43 s if (1rst)begin44 k<=0;45 wr_ed<=0 ; /wr_ed:模式串 寫入結(jié)束標(biāo)志46 end47 else48 hbegin49 if (k<=7)/若說明8個字符還沒有完全輸入50

47、sbegin51 pattern k <=p; /將端口的值p存放在數(shù)組中52 k<=k+4tb0001; /地址的值+153 end54 else55 wr_ed<=l;/當(dāng)wjed為1時表示模武串己經(jīng)全部寫入56 end57 end585958 endmodule61圖4-1模式串輸入代碼由于verilog hdl語言不像c語言一樣可以很方便的申請內(nèi)存用于存放變量 或者數(shù)據(jù)，而既然我們的工作是要進行字符串的查找，那么首先我們需要有兩個 字符串。如何存放這兩個字符串？有兩種方法：一種是將字符串存放在fpga內(nèi)部 的存儲器中，比如使用quartus it自帶的megawiza

48、rd plug-in manger工具在fpga 內(nèi)部定制一個ram或者rom存放字符串，或者直接定義一個數(shù)組，即使用fpga的 邏輯單元構(gòu)造ram用于存放字符串。當(dāng)然后一種方式的代價會比較高，尤其是當(dāng) fpga的邏輯單元相對較少吋，隨意地?fù)]霍這種寶貴的資源就不可取。對于本設(shè)計, 由于我們只是需要驗證算法，因此用作主串的字符串不需要很長(實際使用了一 個長度為16的字符串)，因此可以直接定義數(shù)組來存放這個字符串，這樣做可以 避免另外設(shè)計電路用于控制ram的讀取。另外一種方法是令字符串從外部通過引腳輸入到卜tga中，然后再存放在fpga的內(nèi)部ram中，采用這樣的設(shè)計方式，字 符串的內(nèi)容可以很方便

49、地改動，本設(shè)計中的模式串就采用這種方式從外部輸入。 首先我們需耍設(shè)計一個模式串的輸入接口，模式串輸入的verilog hdl代碼如圖 41所不：我們的 verilog hdl 開發(fā)環(huán)境為 quart us 11 8. 0 wed edition, quart us 11 是一個功能強大的集成開發(fā)環(huán)境，支持從源代碼編輯到仿真、布局布線和芯片燒 錄的全部功能。上述代碼中，k是一個計數(shù)值，寬度為4位，表示當(dāng)前輸入的字符的個數(shù)，在 復(fù)位時初始化為oo在每個時鐘的上升沿，k遞增1。p是一個位寬為8的端口， 外部數(shù)據(jù)就從這個端口輸入。在每個時鐘的上升沿，p端口的值賦給patternk 寄存器。因為模式串的

50、長度是8,因此當(dāng)計數(shù)值k>7時就不再需要存儲端口 p的數(shù) 據(jù)，但是為了顯示模式串輸入已經(jīng)完成，必須給出一個提示信息，這個提示信息 不需耍輸岀到fpga的外部，只需耍提醒內(nèi)部的相關(guān)檢測機制就可以，wr.ed就是 這個提示信息，并且將它定義為一個reg型的變量，位寬為1位。當(dāng)k>7時就令vr_ed為1,表示模式串已經(jīng)全部輸入。該部分的功能仿真結(jié)果見圖4-2：simulation laveforassimulation node functonalnamevalue at20.08 ns"0elks 0mlrsts 0聲2 p ka 0u 0a 16wr_eds 0ej ptt

51、ternoa 0&26ej p&tternla 0± pattext»2a 00 p<tt«rn3a 0h pattern4a 04j>62± pattenisa 0±a 0h pattern7a 0a英電）master time bar:20075 ns川 pointer1 73 nsinterval:18 35 nsstarl:圖4-2模式串輸入仿真結(jié)果其中 pattern0pattern7 是 wire 型的輸岀口連接到 pattern 0 "pattern 7,這只是一組用于觀測fpag內(nèi)部寄存器值

52、的端口變量，而這一組端口變量對一設(shè)計 本身并不是必需的，因此當(dāng)模式吊輸入接口的設(shè)計完成以后，可以撤銷這一組端 口。從仿真結(jié)果中可以看出，當(dāng)wr_ed變?yōu)?時，說明模式串應(yīng)當(dāng)已經(jīng)輸入到fpga 內(nèi)部的數(shù)組中了，我們查看此時的pattern0pattern7可以發(fā)現(xiàn)，模式串確實 已經(jīng)輸入到內(nèi)部的數(shù)組中了，這與我們的設(shè)想吻合。4. 2next函數(shù)的計算為了便于verilog hdl程序設(shè)計，我們首先用c語言描述kmp算法。之所以 先用c語言描述kmp算法，是因為verilog hdl最為一種高級的碩件描述語言， 與c語言的風(fēng)格有許多類似之處，其中有許多語句，如辻語句、case語句和(：語 言中的對應(yīng)

53、語句十分相似。如下所示是next函數(shù)的c語言代碼，在visual studio 2008下編輯和調(diào)試代碼。int* computenext(const char* pattern)(int len , i, nexttemp;int *next ;assert (pattern !=null);len = strlen(pattern);if (len = 0) len =1;next = (int*)malloc(sizeof(int) * len );for (i =1; i < len; i+)(nexttemp = nex tit;while (patternit upatter

54、nnexttemp && nexttemp !=-l ) (nexttemp = nextnexttemp;)next i = nexttemp +1;)return next;)代碼的功能即實現(xiàn)對next值的計算。下面我們將詳細(xì)說明如何根據(jù)c語言代碼編寫verilog hdl代碼，實現(xiàn)kmp 算法。仔細(xì)觀測上述代碼，我們會發(fā)現(xiàn)這個函數(shù)其實可以分解為四個步驟：(1) i的值遞增1;(2) 令 nexttemp=nextit；(3) 判斷 patternil!patternnexttemp&&nexttemp! =-1 是否成立，若 成立則執(zhí)行nexttemp二n

55、ext nexttemp,并且接下來繼續(xù)進入過程3；否則跳過這 一步進入過程4；(4) 令 next i=nexttemp+l,冋到過程 1；圖4-3 next函數(shù)狀態(tài)圖事實上我們可以用一個狀態(tài)圖表述上述過程如圖4-3這張狀態(tài)轉(zhuǎn)移圖的內(nèi)容與上述的c語言代碼的流程是完全一致的，有了這個狀態(tài)圖，我們就可以編寫一個狀態(tài)機，來實現(xiàn)next函數(shù)。具體代碼如圖4-455always!? (posedge elk or negedge rst)56 s begin57if (1rst)58 hbegin59counte r_i<=0;60next0<=4t七61end62else if (wr_

56、ed)/如果wjed為1*說明模式串已經(jīng)全部輸入'可以開始計算next t63 sbegin64 hcase(state nextv)65 h4tb0001:begin66if (coun-ter_i<7)67 hbegin68counte r_i<=coun69sta*te_nextv<=4 tb0010;70end71else72s七ate_nextvtb0001;73end74 s4tb0010:begin75nexcoun七&1?_:1-1;76sate_nextv<= 4 tboloo;77end78 h4boloo:begin79if ( (pa tyteirri uoun 七&芝 i-1 !=pat 七&疋“113：> 七*?&111卩)&& nex"ttemp!=4 'bllll)80 hbegin81nextt emp<=nextnextt emp;82s七ate_next