资源描述：
《Strict pattern matching under non-overlapping condition.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、SCIENCECHINAInformationSciences.RESEARCHPAPER.January2017,Vol.60012101:1–012101:16doi:10.1007/s11432-015-0935-3Strictpatternmatchingundernon-overlappingconditionYouxiWU1,2*,CongSHEN1,3,HeJIANG4&XindongWU5,61SchoolofComputerScienceandEngineering,HebeiUniversityofTechnology,Tianjin300401,
2、China;2HebeiProvinceKeyLaboratoryofBigDataCalculation,Tianjin300401,China;3SchoolofComputerScienceandTechnology,TianjinUniversity,Tianjin300072,China;4SchoolofSoftware,DalianUniversityofTechnology,Dalian116621,China;5SchoolofComputerScienceandInformationEngineering,HefeiUniversityofTech
3、nology,Hefei230009,China;6SchoolofComputingandInformatics,UniversityofLouisianaatLafayette,Lafayette,LA70503,USAReceivedFebruary14,2016;acceptedMay11,2016;publishedonlineNovember15,2016AbstractPatternmatching(orstringmatching)isanessentialtaskincomputerscience,especiallyinse-quentialpat
4、ternmining,sincepatternmatchingmethodscanbeusedtocalculatethesupport(orthenumberofoccurrences)ofapatternandthentodeterminewhetherthepatternisfrequentornot.Astate-of-the-artsequentialpatternminingwithgapconstraints(orflexiblewildcards)usesthenumberofnon-overlappingoc-currencestodenotethef
5、requencyofapattern.Non-overlappingmeansthatanytwooccurrencescannotusethesamecharacterofthesequenceatthesamepositionofthepattern.Inthispaper,weinvestigatestrictpatternmatchingunderthenon-overlappingcondition.WeshowthattheproblemisinPatfirst.Thenweproposeanalgorithm,calledNETLAP-Best,which
6、usesNettreestructure.NETLAP-BesttransformsthepatternmatchingproblemintoaNettreeanditeratestofindtherightmostroot-leafpath,toprunetheuselessnodesintheNettreeafterremovingtherightmostroot-leafpath.WeshowthatNETLAP-Bestisacompletealgorithmandanalysethetimeandspacecomplexitiesofthealgorithm.
7、ExtensiveexperimentalresultsdemonstratethecorrectnessandefficiencyofNETLAP-Best.Keywordspatternmatching,sequentialpatternmining,gapconstraint,flexiblewildcard,non-overlapping,occurrence,NettreeCitationWuYX,ShenC,JiangH,etal.Strictpatternmatchingundernon-overlappingcondition.SciChi
