本文選題：字符串匹配 + 有限狀態(tài)自動機�。� 參考：《華中科技大學學報(自然科學版)》2005年S1期

【摘要】：在基于有限狀態(tài)自動機的多模式匹配算法(DFSA算法)基礎上,結合Tuned BM算法的優(yōu)點,提出一種快速的多模式字符串匹配算法,實現(xiàn)了多模式匹配過程中不匹配字符的連續(xù)跳躍.在一般情況下,算法不需要匹配目標串中的每個字符,而是在實際比較之前跳過盡可能多的字符,以減少字符比較的操作,實現(xiàn)快速匹配.在模式串較長和較短的情況下,算法都有很好的性能.分析指出算法實際比較的字符數(shù)隨著模式串長度的增加而下降,并隨模式集的增大有所增多.實驗表明,在模式串較短時,算法需要的匹配時間僅為AC算法的50%到33.3%,AQR算法的90%左右;在模式串較長時,所需時間為AC算法的25%至12.5%,AQR算法的75%左右.
[Abstract]:On the basis of multi-pattern matching algorithm based on finite state automata and combining the advantages of Tuned BM algorithm, a fast multi-pattern string matching algorithm is proposed, which realizes the continuous jump of mismatched characters in the process of multi-pattern matching. In general, the algorithm does not need to match each character in the target string, but skips as many characters as possible before the actual comparison, so as to reduce the operation of character comparison and achieve fast matching. When the pattern string is longer and shorter, the algorithm has good performance. It is pointed out that the number of characters compared with the algorithm decreases with the increase of the length of the pattern string and increases with the increase of the pattern set. The experimental results show that the matching time of the algorithm is only about 50% to 33. 3% of the AC algorithm when the pattern string is short, and 25% to 75% of the AC algorithm when the pattern string is longer.
【作者單位】： 哈爾濱工業(yè)大學計算機網(wǎng)絡與信息安全技術研究中心 哈爾濱工業(yè)大學計算機網(wǎng)絡與信息安全技術研究中心
【基金】：國家自然科學基金資助項目(60203021)
【分類號】：TP391.1

【共引文獻】

相關期刊論文 前10條

1 萬國根;秦志光;;改進的AC-BM字符串匹配算法[J];電子科技大學學報;2006年04期

2 宋華,戴一奇;一種用于內(nèi)容過濾和檢測的快速多關鍵詞識別算法[J];計算機研究與發(fā)展;2004年06期

3 郭道榮,劉衛(wèi)寧;多維頻繁情節(jié)挖掘在電信告警信息分析中的應用[J];計算機工程與應用;2004年02期

4 袁世忠;曹e，

本文編號：1847381