Snort入侵檢測(cè)中模式匹配算法的研究和改進(jìn)

1、    snort入侵檢測(cè)中模式匹配算法的研究和改進(jìn)    劉凱摘要：入侵檢測(cè)系統(tǒng)snort是一種常用的入侵檢測(cè)軟件，該文其分析系統(tǒng)的檢測(cè)引擎及其采用的模式匹配算法尤其是bm算法進(jìn)行了深入的分析和討論，在分析的基礎(chǔ)中對(duì)bm算法進(jìn)行改進(jìn)，使用一種新的模式匹配算法，以減少匹配時(shí)間，提高匹配效率，達(dá)到提高算法的平均性能和較少資源消耗的目的。關(guān)鍵詞：入侵檢測(cè)；模式匹配；算法：tp393 ：a ：1009-3044（2014）34-8117-02入侵檢測(cè)系統(tǒng)（intrusion detection system，簡(jiǎn)稱(chēng)“ids”）1是一種對(duì)網(wǎng)絡(luò)傳輸進(jìn)行即時(shí)監(jiān)控，在發(fā)

2、現(xiàn)可以傳輸數(shù)據(jù)時(shí)發(fā)出警報(bào)或者采取主動(dòng)反應(yīng)措施的網(wǎng)絡(luò)安全設(shè)備。1 入侵檢測(cè)系統(tǒng)snortsnort2入侵檢測(cè)是一個(gè)基于libpcap的輕量級(jí)入侵檢測(cè)系統(tǒng)軟件，是從著名的tcpdump軟件發(fā)展而來(lái)的。它是個(gè)基于libpcap包的網(wǎng)絡(luò)監(jiān)視軟件，是一個(gè)十分有效的網(wǎng)絡(luò)入侵監(jiān)測(cè)系統(tǒng)。snort入侵檢測(cè)系統(tǒng)基本由四部分組成：嗅探器，預(yù)處理器，檢測(cè)引擎，日志報(bào)警3。如圖1所示。其中檢測(cè)引擎， 是 snort 的核心部件， 主要功能是規(guī)則分析和特征檢測(cè)。當(dāng)數(shù)據(jù)包從預(yù)處理器送過(guò)來(lái)后， 檢測(cè)引擎依據(jù)預(yù)先設(shè)置的規(guī)則檢查數(shù)據(jù)包，使用某種模式匹配算法 一旦發(fā)現(xiàn)數(shù)據(jù)包中的內(nèi)容和某條規(guī)則相匹配， 就通知報(bào)警模塊。2 單模式匹

3、配算法研究與改進(jìn)為了提高入侵檢測(cè)系統(tǒng)的準(zhǔn)確率，減少誤報(bào)率，在實(shí)際的入侵檢測(cè)系統(tǒng)中一般大都采用精確的模式串匹配算法。模式匹配問(wèn)題分為單模式匹配算法和多模式匹配算法4。該文主要對(duì)單模式匹配算法（bm）進(jìn)行研究和改進(jìn)。2.1 單模式匹配算法（bm）僅一次在文本串中查找一個(gè)模式串出現(xiàn)的過(guò)程，稱(chēng)為單模式匹配，相應(yīng)的算法稱(chēng)為單模式匹配算法。目前比較常見(jiàn)的單模式匹配算法有kmp（knuth-morris-pratt）算法，bm 算法，bmh 算法等。其中， bm 算法由于使用了啟發(fā)式搜索，采用從右向左的比較方式， 使用好后綴和壞字符來(lái)決定模式串移動(dòng)的距離，通常同時(shí)使用兩個(gè)來(lái)加快查找速度。能夠在搜索過(guò)程中跳過(guò)

4、大部分文本，從而使執(zhí)行效率得到很大的提高，因而在 ids 中運(yùn)用最為廣泛。boyer-moore算法（簡(jiǎn)稱(chēng)為bm算法）5是一個(gè)著名的字符串匹配算法，它把被匹配的字符串模板與匹配字符串自左向右對(duì)齊，并從字符串的最后一個(gè)字符開(kāi)始自右向左進(jìn)行比較。bm算法并不是對(duì)每個(gè)字符依次進(jìn)行比較，當(dāng)出現(xiàn)不匹配的字符時(shí)，它使用兩步啟發(fā)式搜索過(guò)程來(lái)決定字符串向右移動(dòng)多少個(gè)字符繼續(xù)與文本串進(jìn)行比較，從而減少比較次數(shù)。其中：n>m，需要從t中查找出與p完全匹配的子串，并返回該子串在正文串的首字母的位置。bm算法采用從右向左比較 的方法，同時(shí)應(yīng)用到了兩種啟發(fā)式規(guī)則，即壞字符規(guī)則 和好后綴規(guī)則 ，來(lái)決定向右跳躍的距離

5、。 bm算法的基本流程： 設(shè)文本串t，模式串為p。首先將t與p進(jìn)行左對(duì)齊，然后進(jìn)行從右向左比較 。若是某趟比較不匹配時(shí)，bm算法就采用兩條啟發(fā)式規(guī)則，即壞字符規(guī)則 和好后綴規(guī)則 ，來(lái)計(jì)算模式串向右移動(dòng)的距離，直到整個(gè)匹配過(guò)程的結(jié)束。2.2 bm算法改進(jìn)盡管bm算法是擁有高效，考慮全面，簡(jiǎn)便易懂等優(yōu)點(diǎn)，但是由于其使用了兩個(gè)數(shù)組，預(yù)處理時(shí)間較大，匹配次數(shù)較多，造成許多重復(fù)、不必要的比較，還是存在很多需要改進(jìn)的地方。通過(guò)對(duì)bm算法的分析，我們可以發(fā)現(xiàn)，原算法雖然是用到了兩種啟發(fā)式規(guī)則，即壞字符規(guī)則和好后綴規(guī)則。但是，在算法的分析中我們看到，當(dāng)進(jìn)行字符或者字符串匹配時(shí)，大多數(shù)匹配都用到的規(guī)則是壞字符規(guī)

6、則。因此我們可以只用壞字符規(guī)則，通過(guò)移動(dòng)量和規(guī)定字符這兩個(gè)方面對(duì)bm算法進(jìn)行一些改進(jìn)。根據(jù)改進(jìn)算法的思想，可以對(duì)bm算法進(jìn)行如下改進(jìn)。由文本串和模式串最后一個(gè)位置對(duì)應(yīng)的字符的下一個(gè)字符做啟發(fā)向右滑動(dòng)。其作用在于在每次匹配失敗后，把模式向右滑動(dòng)的距離變大，減少了模式匹配中一些不必要的和重復(fù)的比較，縮短了模式匹配的時(shí)間。首先，對(duì)模式串和文本串進(jìn)行分析，將文本串中文本串與模式串最后一個(gè)位置對(duì)應(yīng)的字符的下一個(gè)字符（假設(shè)為x）與模式串進(jìn)行匹配。當(dāng)字符x在模式串中不存在時(shí)，那么顯然從x開(kāi)始的m個(gè)文本不可能與模式串 匹配成功，所以直接跳過(guò)，移動(dòng)距離為模式串長(zhǎng)度+1。當(dāng)x在模式串中出現(xiàn)，并且x的前一位字符也存

7、在于模式串中。移動(dòng)模式串使字符對(duì)齊，計(jì)算偏移量。利用原bm算法進(jìn)行匹配。當(dāng)x在模式串中出現(xiàn)，但是x的前一位字符不存在于模式串中，計(jì)算移動(dòng)模式串使字符x對(duì)齊時(shí)的偏移量和原bm算法中字符不存在模式串中時(shí)的偏移量，進(jìn)行比較，取兩者中的偏移量大的進(jìn)行匹配。2.3 算法性能比較分別對(duì)bm算法和改進(jìn)后的bm算法進(jìn)行性能測(cè)試，用同一主程序分別調(diào)用bm算法和改進(jìn)后的bm算法進(jìn)行匹配測(cè)試，匹配算法實(shí)驗(yàn)中均插入cpu內(nèi)部時(shí)間戳進(jìn)行高精度計(jì)時(shí)，同時(shí)統(tǒng)計(jì)兩種算法在匹配時(shí)模式串向右移動(dòng)的次數(shù)。初始條件：文本串：whiccmnxmxammm 模式串： emam下圖是分別用bm算法和改進(jìn)后的bm算法對(duì)文本串和模式串進(jìn)行匹配

8、后所得到的數(shù)據(jù)。3 結(jié)論本文以目前最著名、最活躍的、基于誤用檢測(cè)的snort為基礎(chǔ)，針對(duì)目前應(yīng)用最廣泛的模式匹配算法bm算法的缺陷進(jìn)行改進(jìn)。但由于各個(gè)方面的局限性，該文研究還有不足和待改進(jìn)的地方?？傊?，網(wǎng)絡(luò)安全是技術(shù)問(wèn)題，也是管理的問(wèn)題。只有提高使用者的安全意識(shí)，合理使用網(wǎng)絡(luò)及安全工具，才能達(dá)到網(wǎng)絡(luò)的真正安全。參考文獻(xiàn)：1 蔣建春，馮登國(guó).網(wǎng)絡(luò)入侵檢測(cè)原理與技術(shù)m.北京：國(guó)防工業(yè)出版社，2001.2 brian caswell，jay beale c foster，jeffrey posluns.snort2.0入侵檢測(cè)m.宋勁松，譯.北京：國(guó)防出版社，2004.3 jack koziol.s

9、nort入侵檢測(cè)實(shí)用解決方案m.吳薄峰，許誠(chéng)，譯.北京：機(jī)械工業(yè)出版社，2005.4 李曉芳，姚遠(yuǎn).入侵檢測(cè)工具snort的研究與使用j.計(jì)算機(jī)應(yīng)用與軟件，2006，23（3）：123-124.5 胡大輝，劉乃齊.高效的snort規(guī)則匹配機(jī)制j.微計(jì)算機(jī)信息，2006（2）.6 2009年中國(guó)互聯(lián)網(wǎng)網(wǎng)絡(luò)安全報(bào)告r.北京：電子工業(yè)出版社，2010.7 楊薇薇，廖翔.一種改進(jìn)的bm模式匹配算法j.計(jì)算機(jī)應(yīng)用，2006（2）：64-65.endprint摘要：入侵檢測(cè)系統(tǒng)snort是一種常用的入侵檢測(cè)軟件，該文其分析系統(tǒng)的檢測(cè)引擎及其采用的模式匹配算法尤其是bm算法進(jìn)行了深入的分析和討論，在分析的基

10、礎(chǔ)中對(duì)bm算法進(jìn)行改進(jìn)，使用一種新的模式匹配算法，以減少匹配時(shí)間，提高匹配效率，達(dá)到提高算法的平均性能和較少資源消耗的目的。關(guān)鍵詞：入侵檢測(cè)；模式匹配；算法：tp393 ：a ：1009-3044（2014）34-8117-02入侵檢測(cè)系統(tǒng)（intrusion detection system，簡(jiǎn)稱(chēng)“ids”）1是一種對(duì)網(wǎng)絡(luò)傳輸進(jìn)行即時(shí)監(jiān)控，在發(fā)現(xiàn)可以傳輸數(shù)據(jù)時(shí)發(fā)出警報(bào)或者采取主動(dòng)反應(yīng)措施的網(wǎng)絡(luò)安全設(shè)備。1 入侵檢測(cè)系統(tǒng)snortsnort2入侵檢測(cè)是一個(gè)基于libpcap的輕量級(jí)入侵檢測(cè)系統(tǒng)軟件，是從著名的tcpdump軟件發(fā)展而來(lái)的。它是個(gè)基于libpcap包的網(wǎng)絡(luò)監(jiān)視軟件，是一個(gè)十分有效

11、的網(wǎng)絡(luò)入侵監(jiān)測(cè)系統(tǒng)。snort入侵檢測(cè)系統(tǒng)基本由四部分組成：嗅探器，預(yù)處理器，檢測(cè)引擎，日志報(bào)警3。如圖1所示。其中檢測(cè)引擎， 是 snort 的核心部件， 主要功能是規(guī)則分析和特征檢測(cè)。當(dāng)數(shù)據(jù)包從預(yù)處理器送過(guò)來(lái)后， 檢測(cè)引擎依據(jù)預(yù)先設(shè)置的規(guī)則檢查數(shù)據(jù)包，使用某種模式匹配算法 一旦發(fā)現(xiàn)數(shù)據(jù)包中的內(nèi)容和某條規(guī)則相匹配， 就通知報(bào)警模塊。2 單模式匹配算法研究與改進(jìn)為了提高入侵檢測(cè)系統(tǒng)的準(zhǔn)確率，減少誤報(bào)率，在實(shí)際的入侵檢測(cè)系統(tǒng)中一般大都采用精確的模式串匹配算法。模式匹配問(wèn)題分為單模式匹配算法和多模式匹配算法4。該文主要對(duì)單模式匹配算法（bm）進(jìn)行研究和改進(jìn)。2.1 單模式匹配算法（bm）僅一次在文

12、本串中查找一個(gè)模式串出現(xiàn)的過(guò)程，稱(chēng)為單模式匹配，相應(yīng)的算法稱(chēng)為單模式匹配算法。目前比較常見(jiàn)的單模式匹配算法有kmp（knuth-morris-pratt）算法，bm 算法，bmh 算法等。其中， bm 算法由于使用了啟發(fā)式搜索，采用從右向左的比較方式， 使用好后綴和壞字符來(lái)決定模式串移動(dòng)的距離，通常同時(shí)使用兩個(gè)來(lái)加快查找速度。能夠在搜索過(guò)程中跳過(guò)大部分文本，從而使執(zhí)行效率得到很大的提高，因而在 ids 中運(yùn)用最為廣泛。boyer-moore算法（簡(jiǎn)稱(chēng)為bm算法）5是一個(gè)著名的字符串匹配算法，它把被匹配的字符串模板與匹配字符串自左向右對(duì)齊，并從字符串的最后一個(gè)字符開(kāi)始自右向左進(jìn)行比較。bm算法并

13、不是對(duì)每個(gè)字符依次進(jìn)行比較，當(dāng)出現(xiàn)不匹配的字符時(shí)，它使用兩步啟發(fā)式搜索過(guò)程來(lái)決定字符串向右移動(dòng)多少個(gè)字符繼續(xù)與文本串進(jìn)行比較，從而減少比較次數(shù)。其中：n>m，需要從t中查找出與p完全匹配的子串，并返回該子串在正文串的首字母的位置。bm算法采用從右向左比較 的方法，同時(shí)應(yīng)用到了兩種啟發(fā)式規(guī)則，即壞字符規(guī)則 和好后綴規(guī)則 ，來(lái)決定向右跳躍的距離。 bm算法的基本流程： 設(shè)文本串t，模式串為p。首先將t與p進(jìn)行左對(duì)齊，然后進(jìn)行從右向左比較 。若是某趟比較不匹配時(shí)，bm算法就采用兩條啟發(fā)式規(guī)則，即壞字符規(guī)則 和好后綴規(guī)則 ，來(lái)計(jì)算模式串向右移動(dòng)的距離，直到整個(gè)匹配過(guò)程的結(jié)束。2.2 bm算法改進(jìn)

14、盡管bm算法是擁有高效，考慮全面，簡(jiǎn)便易懂等優(yōu)點(diǎn)，但是由于其使用了兩個(gè)數(shù)組，預(yù)處理時(shí)間較大，匹配次數(shù)較多，造成許多重復(fù)、不必要的比較，還是存在很多需要改進(jìn)的地方。通過(guò)對(duì)bm算法的分析，我們可以發(fā)現(xiàn)，原算法雖然是用到了兩種啟發(fā)式規(guī)則，即壞字符規(guī)則和好后綴規(guī)則。但是，在算法的分析中我們看到，當(dāng)進(jìn)行字符或者字符串匹配時(shí)，大多數(shù)匹配都用到的規(guī)則是壞字符規(guī)則。因此我們可以只用壞字符規(guī)則，通過(guò)移動(dòng)量和規(guī)定字符這兩個(gè)方面對(duì)bm算法進(jìn)行一些改進(jìn)。根據(jù)改進(jìn)算法的思想，可以對(duì)bm算法進(jìn)行如下改進(jìn)。由文本串和模式串最后一個(gè)位置對(duì)應(yīng)的字符的下一個(gè)字符做啟發(fā)向右滑動(dòng)。其作用在于在每次匹配失敗后，把模式向右滑動(dòng)的距離變大

15、，減少了模式匹配中一些不必要的和重復(fù)的比較，縮短了模式匹配的時(shí)間。首先，對(duì)模式串和文本串進(jìn)行分析，將文本串中文本串與模式串最后一個(gè)位置對(duì)應(yīng)的字符的下一個(gè)字符（假設(shè)為x）與模式串進(jìn)行匹配。當(dāng)字符x在模式串中不存在時(shí)，那么顯然從x開(kāi)始的m個(gè)文本不可能與模式串 匹配成功，所以直接跳過(guò)，移動(dòng)距離為模式串長(zhǎng)度+1。當(dāng)x在模式串中出現(xiàn)，并且x的前一位字符也存在于模式串中。移動(dòng)模式串使字符對(duì)齊，計(jì)算偏移量。利用原bm算法進(jìn)行匹配。當(dāng)x在模式串中出現(xiàn)，但是x的前一位字符不存在于模式串中，計(jì)算移動(dòng)模式串使字符x對(duì)齊時(shí)的偏移量和原bm算法中字符不存在模式串中時(shí)的偏移量，進(jìn)行比較，取兩者中的偏移量大的進(jìn)行匹配。2.

16、3 算法性能比較分別對(duì)bm算法和改進(jìn)后的bm算法進(jìn)行性能測(cè)試，用同一主程序分別調(diào)用bm算法和改進(jìn)后的bm算法進(jìn)行匹配測(cè)試，匹配算法實(shí)驗(yàn)中均插入cpu內(nèi)部時(shí)間戳進(jìn)行高精度計(jì)時(shí)，同時(shí)統(tǒng)計(jì)兩種算法在匹配時(shí)模式串向右移動(dòng)的次數(shù)。初始條件：文本串：whiccmnxmxammm 模式串： emam下圖是分別用bm算法和改進(jìn)后的bm算法對(duì)文本串和模式串進(jìn)行匹配后所得到的數(shù)據(jù)。3 結(jié)論本文以目前最著名、最活躍的、基于誤用檢測(cè)的snort為基礎(chǔ)，針對(duì)目前應(yīng)用最廣泛的模式匹配算法bm算法的缺陷進(jìn)行改進(jìn)。但由于各個(gè)方面的局限性，該文研究還有不足和待改進(jìn)的地方?？傊?，網(wǎng)絡(luò)安全是技術(shù)問(wèn)題，也是管理的問(wèn)題。只有提高使用者

17、的安全意識(shí)，合理使用網(wǎng)絡(luò)及安全工具，才能達(dá)到網(wǎng)絡(luò)的真正安全。參考文獻(xiàn)：1 蔣建春，馮登國(guó).網(wǎng)絡(luò)入侵檢測(cè)原理與技術(shù)m.北京：國(guó)防工業(yè)出版社，2001.2 brian caswell，jay beale c foster，jeffrey posluns.snort2.0入侵檢測(cè)m.宋勁松，譯.北京：國(guó)防出版社，2004.3 jack koziol.snort入侵檢測(cè)實(shí)用解決方案m.吳薄峰，許誠(chéng)，譯.北京：機(jī)械工業(yè)出版社，2005.4 李曉芳，姚遠(yuǎn).入侵檢測(cè)工具snort的研究與使用j.計(jì)算機(jī)應(yīng)用與軟件，2006，23（3）：123-124.5 胡大輝，劉乃齊.高效的snort規(guī)則匹配機(jī)制j.微計(jì)算

18、機(jī)信息，2006（2）.6 2009年中國(guó)互聯(lián)網(wǎng)網(wǎng)絡(luò)安全報(bào)告r.北京：電子工業(yè)出版社，2010.7 楊薇薇，廖翔.一種改進(jìn)的bm模式匹配算法j.計(jì)算機(jī)應(yīng)用，2006（2）：64-65.endprint摘要：入侵檢測(cè)系統(tǒng)snort是一種常用的入侵檢測(cè)軟件，該文其分析系統(tǒng)的檢測(cè)引擎及其采用的模式匹配算法尤其是bm算法進(jìn)行了深入的分析和討論，在分析的基礎(chǔ)中對(duì)bm算法進(jìn)行改進(jìn)，使用一種新的模式匹配算法，以減少匹配時(shí)間，提高匹配效率，達(dá)到提高算法的平均性能和較少資源消耗的目的。關(guān)鍵詞：入侵檢測(cè)；模式匹配；算法：tp393 ：a ：1009-3044（2014）34-8117-02入侵檢測(cè)系統(tǒng)（intru

19、sion detection system，簡(jiǎn)稱(chēng)“ids”）1是一種對(duì)網(wǎng)絡(luò)傳輸進(jìn)行即時(shí)監(jiān)控，在發(fā)現(xiàn)可以傳輸數(shù)據(jù)時(shí)發(fā)出警報(bào)或者采取主動(dòng)反應(yīng)措施的網(wǎng)絡(luò)安全設(shè)備。1 入侵檢測(cè)系統(tǒng)snortsnort2入侵檢測(cè)是一個(gè)基于libpcap的輕量級(jí)入侵檢測(cè)系統(tǒng)軟件，是從著名的tcpdump軟件發(fā)展而來(lái)的。它是個(gè)基于libpcap包的網(wǎng)絡(luò)監(jiān)視軟件，是一個(gè)十分有效的網(wǎng)絡(luò)入侵監(jiān)測(cè)系統(tǒng)。snort入侵檢測(cè)系統(tǒng)基本由四部分組成：嗅探器，預(yù)處理器，檢測(cè)引擎，日志報(bào)警3。如圖1所示。其中檢測(cè)引擎， 是 snort 的核心部件， 主要功能是規(guī)則分析和特征檢測(cè)。當(dāng)數(shù)據(jù)包從預(yù)處理器送過(guò)來(lái)后， 檢測(cè)引擎依據(jù)預(yù)先設(shè)置的規(guī)則檢查數(shù)據(jù)

20、包，使用某種模式匹配算法 一旦發(fā)現(xiàn)數(shù)據(jù)包中的內(nèi)容和某條規(guī)則相匹配， 就通知報(bào)警模塊。2 單模式匹配算法研究與改進(jìn)為了提高入侵檢測(cè)系統(tǒng)的準(zhǔn)確率，減少誤報(bào)率，在實(shí)際的入侵檢測(cè)系統(tǒng)中一般大都采用精確的模式串匹配算法。模式匹配問(wèn)題分為單模式匹配算法和多模式匹配算法4。該文主要對(duì)單模式匹配算法（bm）進(jìn)行研究和改進(jìn)。2.1 單模式匹配算法（bm）僅一次在文本串中查找一個(gè)模式串出現(xiàn)的過(guò)程，稱(chēng)為單模式匹配，相應(yīng)的算法稱(chēng)為單模式匹配算法。目前比較常見(jiàn)的單模式匹配算法有kmp（knuth-morris-pratt）算法，bm 算法，bmh 算法等。其中， bm 算法由于使用了啟發(fā)式搜索，采用從右向左的比較方式，

21、 使用好后綴和壞字符來(lái)決定模式串移動(dòng)的距離，通常同時(shí)使用兩個(gè)來(lái)加快查找速度。能夠在搜索過(guò)程中跳過(guò)大部分文本，從而使執(zhí)行效率得到很大的提高，因而在 ids 中運(yùn)用最為廣泛。boyer-moore算法（簡(jiǎn)稱(chēng)為bm算法）5是一個(gè)著名的字符串匹配算法，它把被匹配的字符串模板與匹配字符串自左向右對(duì)齊，并從字符串的最后一個(gè)字符開(kāi)始自右向左進(jìn)行比較。bm算法并不是對(duì)每個(gè)字符依次進(jìn)行比較，當(dāng)出現(xiàn)不匹配的字符時(shí)，它使用兩步啟發(fā)式搜索過(guò)程來(lái)決定字符串向右移動(dòng)多少個(gè)字符繼續(xù)與文本串進(jìn)行比較，從而減少比較次數(shù)。其中：n>m，需要從t中查找出與p完全匹配的子串，并返回該子串在正文串的首字母的位置。bm算法采用從右

22、向左比較 的方法，同時(shí)應(yīng)用到了兩種啟發(fā)式規(guī)則，即壞字符規(guī)則 和好后綴規(guī)則 ，來(lái)決定向右跳躍的距離。 bm算法的基本流程： 設(shè)文本串t，模式串為p。首先將t與p進(jìn)行左對(duì)齊，然后進(jìn)行從右向左比較 。若是某趟比較不匹配時(shí)，bm算法就采用兩條啟發(fā)式規(guī)則，即壞字符規(guī)則 和好后綴規(guī)則 ，來(lái)計(jì)算模式串向右移動(dòng)的距離，直到整個(gè)匹配過(guò)程的結(jié)束。2.2 bm算法改進(jìn)盡管bm算法是擁有高效，考慮全面，簡(jiǎn)便易懂等優(yōu)點(diǎn)，但是由于其使用了兩個(gè)數(shù)組，預(yù)處理時(shí)間較大，匹配次數(shù)較多，造成許多重復(fù)、不必要的比較，還是存在很多需要改進(jìn)的地方。通過(guò)對(duì)bm算法的分析，我們可以發(fā)現(xiàn)，原算法雖然是用到了兩種啟發(fā)式規(guī)則，即壞字符規(guī)則和好后綴

23、規(guī)則。但是，在算法的分析中我們看到，當(dāng)進(jìn)行字符或者字符串匹配時(shí)，大多數(shù)匹配都用到的規(guī)則是壞字符規(guī)則。因此我們可以只用壞字符規(guī)則，通過(guò)移動(dòng)量和規(guī)定字符這兩個(gè)方面對(duì)bm算法進(jìn)行一些改進(jìn)。根據(jù)改進(jìn)算法的思想，可以對(duì)bm算法進(jìn)行如下改進(jìn)。由文本串和模式串最后一個(gè)位置對(duì)應(yīng)的字符的下一個(gè)字符做啟發(fā)向右滑動(dòng)。其作用在于在每次匹配失敗后，把模式向右滑動(dòng)的距離變大，減少了模式匹配中一些不必要的和重復(fù)的比較，縮短了模式匹配的時(shí)間。首先，對(duì)模式串和文本串進(jìn)行分析，將文本串中文本串與模式串最后一個(gè)位置對(duì)應(yīng)的字符的下一個(gè)字符（假設(shè)為x）與模式串進(jìn)行匹配。當(dāng)字符x在模式串中不存在時(shí)，那么顯然從x開(kāi)始的m個(gè)文本不可能與模式串 匹配成功，所以直接跳過(guò)，移動(dòng)距離為模式串長(zhǎng)度+1。當(dāng)x在模式串中出現(xiàn)，并且x的前一位字符也存在于模式串中。移動(dòng)模式串使字符對(duì)齊，計(jì)算偏移量。利用原bm算法進(jìn)行匹配。當(dāng)x在模式串中出現(xiàn)，但是x的前一位字符不存在于模