Efficient algorithmsfor (δ,γ,α)-matching.ppt

文档介绍：Efficientalgorithmsfor(δ,γ,α)-puterEngineeringDept.,ódź,Poland******@,Prague,August2006KimmoFredriksson,Finland******@,it’snotrelevantformusicinformationretrieval(MIR)thusbeendeveloped...Stringmatchinginitsclassicform:giventextT=t0t1...tn–1,andpatternP=p0p1...pm–1overafinitealphabetΣofsizeσ,(exactmatching)&,Efficientagorithmsfor(δ,γ,α)-matching2Models&applications–musicinformationretrievalWeallowclassesofcharacters:theclassesarecontinuousintervals(ofequalwidth,2δ+1,forallpatternpositions).Thiscorrespondstohandlinglittledistortionsofthemelody(singer/whistlerunskilledorunderinfluence...).Limitationonthesumofindividualerrorsγ(<mδ).Gapsalsoallowed–thisistoskipornamentation(esp.inclassicalmusic).Weassumeallgapsarein[0,α]–thekeyofthemelodycanbearbitrary,&,Efficientagorithmsfor(δ,γ,α)-matchingFuturework,hopefully...3Problemweconsiderhere(δ,γ,α)-matchingTwosymbolsa,bΣdelta-match(wewritea=δb)iff|a–b|(δ,γ,α)-matchesthetextsubstringti0ti1...ti(m–1),ifpj=δtijforj{0...m–1},where0<ij+1–ijα+1,&,Efficientagorithmsfor(δ,γ,α)-matching4Previousworkonsimilarmodels(δ,α)-matching:Crochemoreetal.,2002:O(mn)time(worst,avg,andbestcase).Cantoneetal.,2005a:alsoO(mn)ineverycasetofindnotonlythe.,2005b:achievingO(n)onavg(forconstantα)andretainingO(mn)&Raffinot,2003;Cantoneetal.,2005b:nondeterministicfiniteautomatonwithO(nmα/w)worstcasetime.Alongtheselines:Fredriksson&Grabowski,2006:pactautomatonwithO(nmlog(α)/w)&Grabowski,2006:bit-paralgwithO(nδ+n/wm)