面向中英文混合环境的多模式匹配算法·

《面向中英文混合环境的多模式匹配算法·》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据ISSN1000-9825．CODENRUXUEWJournalofSoftware，V01．19，No．3，March2008，IV．674--686DOf：10．3724／Spd．100J．2008．00674o2008byJournalofSoftware．Allrightsreserved．面向中英文混合环境的多模式匹配算法·孙钦东1芦，黄新波3，王倩1’(西安理工大学计算机科学与工程学院，陕西西安710048)2(西安交通大学电子与信息工程学院，陕西西安710049)3(西安工程大学电子信息学院，陕西西安710048)MultiplePatternMatchi

2、ngonChinese／EnglishMixedTextsSUNQin．Don91芦，HUANGXin．B03，WANGQianl1(SchoolofComputerScienceandEngineering，Xi’anUniversityofTechnology，Xi’all710048，China)2(SchoolofElectronicsandInformationEngineering。Xi’allJiaotongUniversity，Xi’all710049，China)3(CollegeofElectronicsandInformation，Xi’anPolytec

3、hnicUniversity，Xi’an710048，China)+Correspondingauthor：Plan：+86—29-82312231．E—mail：sqd@xanet．edu．∞E-mail：jos@iscas．∽．cnhnp：／／www．jos．org．gnTel／Fax：+86·10-62562563SunQD，HuangXB，WangQ．MultiplepatternmatchingonChinese／Englishmixedtexts．JournalofSoftware，2008，19(3)：674-686．http：I／www．jos．org．cn／1

4、000-9825／19／674．htmAbstract：ThecharacteristicsofmultiplepatternmatchinginmixedChineseandEnglishtextandtheproblemoftheexistingmultiplepaaemmatchingalgorithmsusedforprocessingmixedChineseandEnglishtextareanalyzed．AtheoremofmultiplepaRernmatchinginmixedChineseandEnglishtextisdiscoveredandproved

5、．Anovelmultiplepattemmatchingalgorithmbasedonthethreadedtrietreeisproposed,whichexpandsthestandardtriestructure，constructsthehashtriematchingmachinewiththecodesofChineseandEnglishcharacters，andthreadsthetrietreeaccordingtothecharacteristicofpatternsset．Theproposedalgorithmdoesnotneedcomplexh

6、ashoperation，andthematchingpointerdoesnotneedbackdateduringmatching．Theoreticanalysisandexperimenmlresultsdemonstratethattheproposedalgorithmefficientlysolvesthespaceexpansionproblem，andprocessmixedChineseandEnglishtextcorrectlyandefficientlywithlowertimeandspacecomplexity．Keywords：multiplep

7、atternmatching；Chinese／Englishmixed；Hash；Trie摘要：分析了中英文混合环境下多模式匹配的特点，以及已有多模式匹配算法应用于中英文混合环境时的不足，给出并证明了中英文混合环境下多模式匹配算法的性能定理，提出了一种适合于中英文混合环境的基于线索完全哈希The结构的多模式匹配算法．该算法扩展了标准Trie结构，以中英文字符内码为键值构造完全哈希Trie匹配机，并利用模式串之间的关系对Trie匹配机进行线索化．理论分析与实验结果表明，所提出的算法在匹配中无需