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

【摘要】：在基于有限狀態(tài)自動(dòng)機(jī)的多模式匹配算法(DFSA算法)基礎(chǔ)上,結(jié)合Tuned BM算法的優(yōu)點(diǎn),提出一種快速的多模式字符串匹配算法,實(shí)現(xiàn)了多模式匹配過程中不匹配字符的連續(xù)跳躍.在一般情況下,算法不需要匹配目標(biāo)串中的每個(gè)字符,而是在實(shí)際比較之前跳過盡可能多的字符,以減少字符比較的操作,實(shí)現(xiàn)快速匹配.在模式串較長(zhǎng)和較短的情況下,算法都有很好的性能.分析指出算法實(shí)際比較的字符數(shù)隨著模式串長(zhǎng)度的增加而下降,并隨模式集的增大有所增多.實(shí)驗(yàn)表明,在模式串較短時(shí),算法需要的匹配時(shí)間僅為AC算法的50%到33.3%,AQR算法的90%左右;在模式串較長(zhǎng)時(shí),所需時(shí)間為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è)大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心 哈爾濱工業(yè)大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心
【基金】：國(guó)家自然科學(xué)基金資助項(xiàng)目(60203021)
【分類號(hào)】：TP391.1

【共引文獻(xiàn)】

相關(guān)期刊論文 前10條

1 萬國(guó)根;秦志光;;改進(jìn)的AC-BM字符串匹配算法[J];電子科技大學(xué)學(xué)報(bào);2006年04期

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

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

4 袁世忠;曹e，

本文編號(hào)：1847381