资源描述：
《串匹配算法中模式串与文本之间关系的研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.ac.cnJournalofSoftware,Vol.21,No.7,July2010,pp.1503−1514http://www.jos.org.cndoi:10.3724/SP.J.1001.2010.03613Tel/Fax:+86-10-62562563©byInstituteofSoftware,theChineseAcademyofSciences.Allrightsreserved.∗串匹配算法中模式串与文本之间关系的研究1,3+1
2、,2,31,31,3刘萍,刘燕兵,郭莉,方滨兴1(中国科学院计算技术研究所,北京100190)2(中国科学院研究生院,北京100049)3(信息内容安全技术国家工程实验室,北京100190)ResearchonRelationshipBetweenPatternsandTextinStringMatchingAlgorithms1,3+1,2,31,31,3LIUPing,LIUYan-Bing,GUOLi,FANGBin-Xing1(InstituteofComputingTechnology,TheChineseAcademy
3、ofSciences,Beijing100190,China)2(GraduateUniversity,TheChineseAcademyofSciences,Beijing100049,China)3(NationalEngineeringLaboratoryforInformationSecurityTechnologies,Beijing100190,China)+Correspondingauthor:E-mail:liuping@ict.ac.cnLiuP,LiuYB,GuoL,FangBX.Researchonrela
4、tionshipbetweenpatternsandtextinstringmatchingalgorithms.JournalofSoftware,2010,21(7):1503−1514.http://www.jos.org.cn/1000-9825/3613.htmAbstract:Itwasassumedthatthepatternandtextcharactersareindependentanduniformlydistributedoverafinitealphabetinclassicalstringmatchin
5、galgorithms,andthisassumptiondiffersfromrealapplicationsandcausesmanyproblems.Consideringtheprobabilitydistributions,thecontextsofthecharacters,andtheconvenienceofapplications,thispapergivesaconcepthitrateandfourextendedconceptsaboutit.Thenitgivesthetheoryanalysisandd
6、etailedexperimentswithhitrateonthefourclassicalalgorithms.Themapoftherelationshipsisobtainedbetweenthehitrateandthealgorithms’performance,andatthesametimesomevaluableconclusionsaremadethroughabovework.Asacharactervariable,hitratedescribestherelativityofpatternsandtext
7、andcanserveasguidelinesinthealgorithmsdesign,analysisandsomeotherextendedresearchfieldsofthestringmatching.Keywords:stringmatching;probabilitydistributionsofcharacter;relativityofstrings摘要:经典的串匹配算法设计和分析中假设“字符互相独立并且等概率出现”,这与实际应用环境差异很大,导致出现很多问题.考虑了字符的概率分布和上下文的关联,同时兼顾应用的
8、方便,提出了命中密度的概念.在给出基本定义和扩展定义后,通过对4种类型的代表性算法的理论和实验分析,给出了命中密度与算法性能之间的关系.同时,在对命中密度的分析中得出一些极具价值的结论.对命中密度概念的多角度理解以及对它与算法性能关系的深入剖析都说
