资源描述：
《面向中英文混合环境的多模式匹配算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.ac.cnJournalofSoftware,Vol.19,No.3,March2008,pp.674−686http://www.jos.org.cnDOI:10.3724/SP.J.1001.2008.00674Tel/Fax:+86-10-62562563©2008byJournalofSoftware.Allrightsreserved.∗面向中英文混合环境的多模式匹配算法1,2+31孙钦东,黄新波,王倩1(西安理工大学计算机科学与工程学院,陕西西安710048)2(西安交通大学电子与信
2、息工程学院,陕西西安710049)3(西安工程大学电子信息学院,陕西西安710048)MultiplePatternMatchingonChinese/EnglishMixedTexts1,2+31SUNQin-Dong,HUANGXin-Bo,WANGQian1(SchoolofComputerScienceandEngineering,Xi’anUniversityofTechnology,Xi’an710048,China)2(SchoolofElectronicsandInformationEngineering,Xi’anJiaotongUniversity,Xi’a
3、n710049,China)3(CollegeofElectronicsandInformation,Xi’anPolytechnicUniversity,Xi’an710048,China)+Correspondingauthor:Phn:+86-29-82312231,E-mail:sqd@xanet.edu.cnSunXD,HuangXB,WangQ.MultiplepatternmatchingonChinese/Englishmixedtexts.JournalofSoftware,2008,19(3):674−686.http://www.jos.org.cn/10
4、00-9825/19/674.htmAbstract:ThecharacteristicsofmultiplepatternmatchinginmixedChineseandEnglishtextandtheproblemoftheexistingmultiplepatternmatchingalgorithmsusedforprocessingmixedChineseandEnglishtextareanalyzed.ThetheoremofmultiplepatternmatchinginmixedChineseandEnglishtextisputforthandprov
5、ed.Anovelmultiplepatternmatchingalgorithmbasedonthethreadedtrietreeisproposed,whichexpandsthestandardtriestructure,constructsthehashtriematchingmachinewiththecodesofChineseandEnglishcharacters,andthreadsthetrietreeaccordingtothecharacteristicofpatternsset.Theproposedalgorithmdoesnotneedcompl
6、exhashoperation,andthematchingpointerdoesnotneedbackdateduringmatching.Theoreticanalysisandexperimentalresultsdemonstratethattheproposedalgorithmefficientlysolvesthespaceexpansionproblem,andprocessmixedChineseandEnglishtextcorrectlyandefficientlywithlowertimeandspacecomplexity.Keywords:multi
7、plepatternmatching;Chinese/Englishmixed;Hash;trie摘要:分析了中英文混合环境下多模式匹配的特点,及已有多模式匹配算法应用于中英文混合环境时的不足,给出并证明了中英文混合环境下多模式匹配算法的性能定理,提出了一种适合于中英文混合环境的基于线索完全哈希Trie结构的多模式匹配算法,该算法扩展了标准Trie结构,以中英文字符内码为键值构造完全哈希Trie匹配机,并利用模式串之间的关系对Trie匹配机进行线索化.理论分析与实验结果表明,所提算法在匹配中
