文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > 数学 > 一种快速的多模式字符串匹配算法
侵权投诉

一种快速的多模式字符串匹配算法

 第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]

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email