基于跳躍式匹配的多模式匹配算法研究.pdf

1、模式匹配技術(shù)廣泛應(yīng)用于生物信息學(xué)、網(wǎng)絡(luò)搜索引擎、內(nèi)容過濾防火墻、入侵檢測系統(tǒng)等領(lǐng)域，是信息科學(xué)領(lǐng)域中重要的研究方向之一。隨著計算機網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)中的信息量呈現(xiàn)爆炸式增長。如何提高模式匹配效率成為人們研究的熱點。
　　本文介紹了模式匹配技術(shù)的國內(nèi)外研究現(xiàn)狀，探討了模式匹配及其應(yīng)用技術(shù)，研究了幾種典型的模式匹配算法，包括單模式匹配BM算法、BMH算法、Sunday算法等及多模式匹配AC算法、AC_BM算法等，分析了他們的時間

2、性能，并比較了各自的優(yōu)缺點。針對AC_BM等算法的不足之處，提出一種改進的多模式匹配算法——AC_TE，該算法具有以下特點:
　　(1)基于跳躍式匹配思想，根據(jù)當前匹配窗口前兩個字符確定模式樹跳躍距離，保證在不發(fā)生漏檢的情況下，使得模式樹最大移動距離達到最短模式串長度minlen加2，從而減少匹配次數(shù)。
　　(2)構(gòu)建首字符表、minlen層字符表和字符串跳躍哈希表，分別存儲模式樹首層字符、minlen層字符和模式樹中兩兩相