第36卷第4期 2002年4月
上海交通大学学报
JOURNALOFSHANGHAIJIAOTONGUNIVERSITY
Vol.36No.4 Apr.2002
文章编号:1006-2467(2002)04-0516-05
一种快速的多模式字符串匹配算法
许一震, 王永成, 沈 洲
(上海交通大学计算机科学与工程系,上海200030)
摘 要:以基于有限自动机的多模式匹配算法(DFSA)为基础,结合Boyer-Moore(BM)和QuickSearch(QS)快速单模式匹配算法的优点,提出了一种快速的多模式字符串匹配算法.在一般情况下,该算法不需要匹配目标文本串中的每个字符,能充分利用匹配过程中本次匹配不成功的信息和已经匹配成功的信息,跳过尽可能多的字符.实验表明,模式串较短时,本算法所需时间为DFSA算法的1/2~1/3;模式串较长时,其所需时间为DFSA算法的1/3~1/5.关键词:匹配;有限自动机;多模式匹配中图分类号:TP311 文献标识码:A
AFastAlgorithmforMatchingMultiplePatterns
XUYi-zhen, WANGYong-cheng, SHENZhou
(Dept.ofComputerScience&Eng.,ShanghaiJiaotongUniv.,Shanghai200030,China)
Abstract:Afastalgorithmtoperformmultiplepatternsmatchinastringwasdescribed.Theproposedmatchalgorithmisbasedontheconceptofdeterministicfinitestateautomata(DFSA),combiningthead-vantagesofBoyer-Moore'salgorithmandQuickSearchalgorithm,thetwofastalgorithmsforsinglepat-ternmatching.Ingeneral,itdoesnotneedinspecteachcharacterofthestring.Itskipsasmanycharactersaspossiblebymakingfulluseofthesucceededmatchinformationandfailureinformationduringthematching.Theproposedalgorithmachievesexcellentperformanceinthecasesofbothshortpatternsandlongpatterns.Theactualexperimentsshowthatinthecaseofshortpatternsthetimeittakestosearchastringis1/2~1/3ofthetimeDFSAmethodtakes,andinthecaseoflongpatternsthetimeisonly1/3~1/5ofthetimebyDFSAmethod.
Keywords:patternmatch;finitestateautomata;multiplepatternmatch
在文本串中查找用户指定的模式串,即所谓字符串匹配是计算机进行信息处理的一个基本问题,一直受到人们的关注.多模式匹配是从文本串S[1:n]中一次查找多个模式串P1,P2,…,Pq;所有模式串形成模式串集合{P},其中q为模式串的数目,模式串Pk的长度是mk,即Pk[1:mk](1≤k≤q),
收稿日期:2000-09-12
基金项目:国家“863”计划资助项目(863-306-ZD03-04-1)作者简介:许一震(1975-),男,江苏无锡人,硕士生,主要从事
中文信息处理、自动摘要技术、模式匹配算法等研minlen是最短模式串的长度,即
minlen=min{mk 1≤k≤q}
3种经典的单模式匹配算法是:Knuth-Morris-Pratt(KMP)Search(QS)
[1]
、Boyer-Moore(BM)
[2]
和Quick
[3]
.多模式匹配的经典算法是基于有限
自动机(DeterministicFiniteStateAutomata,DF-SA)的算法,它把模式串集合转换成树型有限自动机,然后只需对文本串进行一次扫描就可找出所有模式串.FS(Fan-Su)算法把DFSA和BM算法相结合,在匹配中实现了跳跃式查找,在平均情况,.
[5]
[4]
Sea rch (Q S ) 快速单模式匹配算法的优点, 提出了一种快速的多模式字符串匹配算法 在一般情况 中图分类号: T P 311 文献标识码: A 下, 该算法不需要...
一种高效的多模式字符串匹配算法_数学_自然科学_专业资料 暂无评价
多模式匹配快速算法的设... 6页 免费 一种快速的多模式字符串... 5页 1下载...Fo r the aver2 m 据一次查找字串模式的数目, 字串匹配可以分为单 模式...
2. 深圳金山信息安全技术有限公司,深圳 518057) 摘要:将有序二叉树和 QS 算法相结合,提出一种快速多模式字符串匹配算法,实现在多模式匹配过程中不匹配字符的连续...
改进的多模式字符串匹配算法_专业资料。在经典的AC多模式字符串匹配算法的基础上,结合BMH算法的优点,提出了一种快速的多模式字符串匹配算法。一般情况下,该算法不需...
基于有序二叉树的快速多模式字符串匹配算法_专业资料。将有序二叉树和QS算法相结合,提出一种快速多模式字符串匹配算法,实现在多模式匹配过程中不匹配字符的连续跳跃...
BMH算 法的优 点,出 了一 种 快速 提 的 多模 式字符 串匹配 算法 。一般...。所谓 多模式匹 配, 就是在文本 串T1 〕中一次匹 配多个 模式 串 〔…...
一种改进的字符串多模式匹配算法_董世博_林学_农林牧渔_专业资料。Computer Engineering...个问题: (1) 如 何充分可靠地描述入侵行为; (2) 使用何种模式匹配算法 ...
本文在有限状态自动机的AC算法的基础上,综合BM算法的跳跃思想和QS算法的优点, 提出了一个快速的多模式字符串匹配算法。该算法能充分利用每次匹配过程中匹配不成功...
一种快速的多模式字符串匹... 5页 2财富值喜欢此文档的还喜欢 多模匹配算法-AC算法 28页 1财富值 多模式匹配算法的性能分析 2页 免费 多模式匹配快速算法的...
热门文档