本文選題：海量多模式匹配 + 布爾表達式匹配�。� 參考：《哈爾濱工程大學》2013年碩士論文

【摘要】：經(jīng)過40余年的發(fā)展，字符串匹配已經(jīng)從單一的單模式串匹配發(fā)展成為包含多模式匹配、正則匹配、近似匹配等多個新方向的研究領域。而隨著計算機技術、網(wǎng)絡技術的發(fā)展，社會的進步，字符串匹配也有了越來越廣泛的應用場所。在信息檢索、入侵檢測、網(wǎng)絡數(shù)據(jù)分析等多個領域都能夠看到字符串匹配的身影。布爾表達式匹配也有很多的應用，如搜索引擎中的布爾查詢，病毒檢測系統(tǒng)的特征組合匹配等等。字符串匹配算法以往的研究和實驗分析都是在模式集規(guī)模在幾千到幾萬的情況下進行的，對于大規(guī)模模式集下的算法沒有進行過深入的分析。本文主要研究內(nèi)容分為如下兩個部分： 研究在大規(guī)模模式集下的多模式匹配問題的特點和難點，提出了基于Wu-manber算法的三種改進算法：基于最短關鍵字長度哈希的改進算法、多哈希值預檢改進算法、成組比較改進算法。 研究布爾表達式匹配問題，提出更泛化的復雜與或布爾表達式匹配問題，，并且針對該問題提出擴展位標記算法。此外本文還提出了布爾表達式化簡方法，來進一步減少表達式數(shù)目，提高匹配效率。 綜上所述，本文在研究和總結現(xiàn)有的模式匹配算法和布爾表達式匹配算法的基礎上，重點對大規(guī)模模式集下匹配算法、復雜與或布爾表達式匹配和表達式化簡進行研究，提出優(yōu)化方案，并且通過實驗來驗證算法的可行性以及空間和時間效率。最后本文還展望了該領域的未來發(fā)展趨勢。
[Abstract]:After more than 40 years' development, string matching has developed from single single pattern string matching to many new research fields, such as multi-pattern matching, regular matching, approximate matching and so on.With the development of computer technology, network technology and society, string matching has been used more and more widely.String matching can be seen in many fields, such as information retrieval, intrusion detection, network data analysis and so on.Boolean expression matching also has many applications, such as Boolean query in search engine, feature combination matching in virus detection system and so on.The previous research and experimental analysis of string matching algorithm are carried out in the case of pattern set size ranging from thousands to tens of thousands, but no in-depth analysis has been done for the algorithm under large-scale pattern set.The main contents of this paper are as follows:This paper studies the characteristics and difficulties of multi-pattern matching problem in large-scale pattern sets, and proposes three improved algorithms based on Wu-manber algorithm: an improved algorithm based on the shortest keyword length hash, an improved multi-hash pre-checking algorithm.The improved algorithm is compared in groups.In this paper, the problem of Boolean expression matching is studied, and a more generalized problem of complex or Boolean expression matching is proposed, and an extended bit marking algorithm is proposed to solve the problem.In addition, a Boolean expression simplification method is proposed to further reduce the number of expressions and improve the matching efficiency.To sum up, on the basis of studying and summarizing the existing pattern matching algorithms and Boolean expression matching algorithms, this paper focuses on the large-scale pattern set matching algorithm, complex or Boolean expression matching and expression simplification.The optimization scheme is proposed, and the feasibility of the algorithm and space and time efficiency are verified by experiments.Finally, the future development trend of this field is prospected.
【學位授予單位】：哈爾濱工程大學
【學位級別】：碩士
【學位授予年份】：2013
【分類號】：TP301.6

【參考文獻】

相關期刊論文 前7條

1 楊軍;鄧芳林;;基于Snort入侵檢測系統(tǒng)模式匹配改進算法研究[J];計算機安全;2011年06期

2 殷麗華,張冬艷,方濱興;面向入侵檢測的單模式匹配算法性能分析[J];計算機工程與應用;2004年24期

3 曹京;譚建龍;劉萍;郭莉;;布爾表達式匹配問題研究[J];計算機應用研究;2007年09期

4 宋云;龍際珍;;規(guī)則數(shù)量無關的多布爾表達式匹配算法[J];軟件導刊;2012年03期

5 李曉明,鳳旺森;兩種對URL的散列效果很好的函數(shù)[J];軟件學報;2004年02期

6 李安懷;荊繼武;;網(wǎng)絡安全系統(tǒng)中的快速規(guī)則匹配[J];計算機工程與設計;2007年06期

7 曹京;劉燕兵;劉萍;譚建龍;郭莉;;定序窗口布爾表達式匹配技術研究[J];通信學報;2007年12期

本文編號：1757934