删除或更新信息,请邮件至freekaoyan#163.com(#换成@)

一般间隙与One-Off条件的序列模式匹配

本站小编 Free考研考试/2022-01-02

闂備浇顕х€涒晠顢欓弽顓炵獥闁圭儤顨呯壕濠氭煙閸撗呭笡闁抽攱鍨堕妵鍕箛閸撲焦鍋ч梺纭呮閻☆櫀闂傚倸鍊烽悞锔锯偓绗涘懐鐭欓柟鐑橆殕閸庢銇勯弬鍨挃闁告宀搁弻娑㈠箻濡も偓閹虫劙鎮$€n喗鍊垫鐐茬仢閸旀岸鏌eΔ鈧崯鏉戠暦閹达箑绠婚悹鍥皺椤︺劌顪冮妶鍛婵☆偅顨婇幃鈥斥槈閵忊檧鎷洪梺绋跨箰閸氬娆㈤弻銉︾厱闁绘梻枪閳绘洟鏌熼娆戝妽鐎垫澘瀚禒锕傚箚瑜庨悗顓㈡⒒娴h櫣銆婇柛鎾寸箖缁楃喎螖閸涱厽杈堥梺闈涱槴閺呮粓鍩涢幒妤佺厱婵炴垵宕獮妯肩磼閻欏懐鎮肩紒杈ㄥ笧娴狅箓鎮剧仦鐣屽幗闂備浇顕栭崹鏉棵洪妸鈺佺劦妞ゆ帒锕﹂崚鏉款熆瑜嶅ù椋庡垝閸喎绶為悗锝庡亜瀵潡姊洪幐搴g畵闁硅櫕鍔楃划濠氬矗婢跺瞼鐦堥梺閫炲苯澧撮柟顔ㄥ洤閱囬柍鍨涙櫆閻忓啴鏌f惔锛勭暛闁稿酣浜堕獮濠冩償閵婏箑浜楅梺绋挎湰閸╁啫危閸儲鐓欑紓浣靛灩閻忕姴霉濠婂牏鐣烘慨濠冩そ瀹曘劍绻濋崒婊呮噯婵犵妲呴崑鍛崲閸儳宓侀柟鎵閺呮悂鏌ㄩ悤鍌涘
547闂傚倸鍊风粈浣革耿闁秲鈧倹绂掔€n亞锛涢梺鐟板⒔缁垶鍩涢幒妤佺厱闁哄洦顨嗗▍鍛存煟韫囷絼閭柡宀嬬到铻栭柍褜鍓熼弻濠囨晲婢跺﹦鐤囬梺瑙勫礃椤曆呯矆閸愨斂浜滈煫鍥ㄦ尰椤ユ粓鏌i幘瀵告创婵﹥妞藉畷妤呭礂閼测晛鍤掗梻浣告憸閸c儵宕戦崟顖涘仼闁绘垼濮ら弲鎼佹煥閻曞倹瀚�1130缂傚倸鍊搁崐椋庣矆娓氣偓钘濇い鏍ㄧ矌閻捇鏌i姀銏╂毌闁稿鎹囧畷褰掝敃閿濆洦顓婚梻渚€鈧偛鑻晶鍙夈亜椤愩埄妲洪柛鐘诧工椤撳吋寰勬繝鍐发闂備線鈧偛鑻晶鎾煛鐏炵ǹ澧茬€垫澘瀚埀顒婄秵娴滄粓锝炴惔鈾€鏀介柣鎰皺婢ф盯鏌涢妸銉т虎闁伙絿鍏橀弫鎾绘偐閼碱剦妲伴柣鐔哥矊缁绘帞鍒掑▎鎾崇倞闁冲搫鍟伴敍婊勭節閵忥絾纭鹃柨鏇檮閺呫儵姊绘担鍛婂暈閼垦囨煕婵犲啰澧辩紓鍌涙崌閹稿﹥绔熼埡鍌涱棃鐎规洦浜濋幏鍛喆閸曨厽袙闂傚倷绀佸﹢閬嶅储瑜旈幃娲Ω閳轰胶顔囬梺鍓插亝濞叉牠鎮為崹顐犱簻闁瑰鍋涢婊呯磼娴e搫顣奸柕鍥у椤㈡洟濮€閳轰礁澹夐梻浣瑰缁嬫帡宕濆▎鎾跺祦閻庯綆鍣弫宥嗙節婵犲倹濯兼俊鏌ユ敱缁绘繈鎮介棃娑楁勃闂佹悶鍔岀紞濠傤嚕椤愩倗鐭欐俊顐ゆ暩閸庛倗鎹㈠┑瀣倞闁靛ǹ鍎查娲⒑閸濆嫷妲搁柣妤佺矒瀹曟垿骞掑Δ鈧崥褰掓煛閸愩劎澧涢柣鎾崇箻閺屾盯鍩勯崘鈺冾槷闂佺ǹ绻愰惉鑲╂閹烘鏁婇柛蹇擃槸娴滈箖鎮洪幒宥嗙グ妞ゎ偄顦甸獮鍡涘棘鎼存挻顫嶉梺鍦劋閸ㄨ櫕绔熼弴鐔虹閺夊牆澧介幃濂告煛閸滀礁浜滈崡閬嶆煕椤愮姴鍔滈柣鎾存礋閺岀喖鎮滃Ο璇查瀺闂佺ǹ顑囨繛鈧柡灞界Х椤т線鏌涜箛鏃傘€掓繛鍡愬灩椤繄鎹勫ú顏咃紬濠德板€х徊浠嬪疮椤栫偛绠犳慨妯诲閸嬫捇鐛崹顔煎闂佸摜鍠撴繛鈧€规洘鍨块獮妯尖偓娑櫭鎾绘⒑缂佹ê鐏﹂柨姘舵煃瑜滈崜娑㈠磻閻旂厧鐒垫い鎺戝枤濞兼劙鏌熼鑲╁煟鐎规洘娲熼、娑㈡倷閼碱剙濮︽俊鐐€栭崹濂稿磿婵犳艾绀傞悘鐐板嫎娴滄粓鏌熼幆褏鎽犻柛濠冨姍閺岀喖顢欓懖鈺佺厽閻庤娲熸禍鍫曠嵁閸ヮ剙惟闁靛鍊曢ˉ姘攽閻愯埖褰х紒鑼亾缁傚秹鎳為妷褜娴勯梺鎸庢磵閸嬫捇妫佹径鎰厱闊洦娲栫敮鍫曟煙閸忓吋鍊愰柡灞界Х椤т線鏌涜箛鏃傗槈闂囧鏌涢妷顔煎缁炬儳銈搁弻鏇熺節韫囨洜鏆犲銈嗘礉妞存悂骞堥妸銉庣喓绮欓崹顔碱潕闂備胶枪椤戝棝骞愭繝姘闁告侗鍨遍崰鍡涙煕閺囥劌澧伴柡鍡樺哺濮婄粯鎷呴崫鍕粯閻庢鍠楅崕濂稿Φ閹版澘绀冩い蹇撴婢跺嫭淇婇妶蹇曞埌闁哥噥鍨跺畷鎴︽偐缂佹ḿ鍘遍梺鏂ユ櫅閸燁偅鎱ㄩ埀顒勬⒑缁嬫鍎愰柟绋款煼楠炲繘宕ㄧ€涙ê浠惧銈嗙墬閼瑰墽绮婚幋锔解拻濞达絽鎲¢幆鍫ユ煕婵犲媱鍦弲闂侀潧绻堥崐鏇㈡倿閸偁浜滈柟瀵稿仜椤曟粎绱掓担瑙勭凡妞ゎ叀娉曢幉鎾礋椤掆偓绾炬娊鎮楀▓鍨灓闁轰礁顭烽妴浣糕槈濡粎鍠庨悾鈩冿紣娴e壊妫滄繝鐢靛仩閹活亞绱為埀顒併亜椤愩埄妯€闁诡噯绻濋崺鈧い鎺戝閳锋帡鏌涚仦鎹愬闁逞屽厸缁瑩銆佸▎鎰瘈闁告洦鍓﹀ḿ鐔兼⒑閸撴彃浜濇繛鍙夌墱缁崵绱掑Ο闀愮盎闂佸湱鍋撳ḿ娆撍夊鑸电厱閻庯綆鍋呯亸浼存煙瀹勭増鍤囩€规洜鍏橀、妯衡攦閹傚婵犵數濮村ú锕傚磹閸偆绠鹃柟瀛樼箘閺嬪啰绱掗埀顒傗偓锝庡枟閻撳啰鎲稿⿰鍫濈婵炴垶姘ㄩ惌鍡椕归敐鍫熴€冮柣鎺戯躬閺岀喎鈻撻崹顔界亐闂佺ǹ顑嗛幐鎼佸煡婢跺备鍋撻崷顓炐ユい锔垮嵆濮婃椽鏌呴悙鑼跺闁告ê鎲$换娑㈠级閹寸偛鏋犲銈冨灪閿曘垹鐣烽锕€唯鐟滃瞼绮径濞炬斀閹烘娊宕愰幘缁樺€块柨鏃€宕樻慨铏叏濡灝鐓愰柣鎾崇箻閺屾盯鍩勯崘鈺冾槶濡炪倧璁f俊鍥焵椤掆偓濠€杈ㄧ仚濡炪値鍘奸崲鏌ユ偩閻戣姤鏅查柛銉檮閸曞啴姊虹粙鎸庢拱妞ゃ劌鎳忕粋宥夊箚椤€崇秺閺佹劙宕ㄩ鍏兼畼闂備礁鎲″ú鐔虹不閺嶎厼钃熼柨婵嗩槹閸婄兘鏌涘▎蹇f▓婵☆偅鍨垮娲焻閻愯尪瀚伴柛妯绘倐閺岋綁骞掗悙鐢垫殼閻庢鍣崜鐔风暦閹烘埈娼╅柨婵嗘閸欏啯绻濆▓鍨灓闁硅櫕鎸哥叅闁绘ǹ顕х壕濠氭煙閹呮憼濠殿垱鎸抽弻娑樷槈濮楀牊鏁鹃梺闈╃稻閹倿寮婚敐鍡樺劅闁靛繒濮撮弸娆撴煟閻樺啿濮夐柛鐘崇墵瀹曟椽鍩€椤掍降浜滈柟瀵稿仜椤曟粍銇勯敃鍌ゆ缂佽鲸鎸搁濂稿椽娴gǹ澹庨梻浣侯攰濞呮洟鎮ч悩璇茬疇闁绘ɑ妞块弫鍡涙煕閹邦喖浜鹃柦鎴濐槺缁辨捇宕掑▎鎴濆闂佸憡鍔曢…鐑界嵁韫囨稒鏅搁柨鐕傛嫹28缂傚倸鍊搁崐椋庢閿熺姴纾诲鑸靛姦閺佸鎲搁弮鍫涒偓浣肝旈崨顔间簻闂佹儳绻愬﹢閬嶆偂鐎n喗鈷戦悷娆忓閸庢鏌涢妸銉э紞缂侇喖鐗婄换鍛枎缁碍绻濋悽闈涗沪婵炲吋鐟╁畷銉р偓锝庡枟閸ゅ苯螖閿濆懎鏆欑紒鐘靛枛閺屟嗙疀閿濆懍绨兼繝娈垮灡閹告娊鐛弽顬ュ酣顢楅埀顒勫焵椤掍焦绀€闁崇粯鎹囬弫鎾绘晸閿燂拷128.00闂傚倸鍊烽懗鑸电仚缂備胶绮崝娆忕暦閺夊簱妲堟慨姗嗗弾濞肩喖姊虹捄銊ユ珢闁瑰嚖鎷�
摘要:带有间隙约束的模式匹配问题是序列模式挖掘的关键问题之一.目前,大多数的研究都为非负间隙,对字符串中每个字符的出现顺序有着严格的要求.为了增加匹配的灵活性,并且考虑到在序列模式挖掘中采用one-off条件更加合理,研究一般间隙与one-off条件下的模式匹配问题.该问题为NP-Hard问题.为了有效地求解该问题,提出了MSAING(maximum sequential pattern matching with one-off and general gaps condition)算法:首先,利用Reverse策略使模式与序列达到最佳的匹配状态;然后,使用线性表的结构使匹配过程中消耗的时间和空间大幅度地降低,同时,利用回溯机制提高匹配的成功率;最后,根据inside_Checking机制判断模式串是否会产生内部重复现象,以进一步提高算法的执行效率.理论证明了MSAING算法的完备性,实验结果验证了MSAING算法匹配结果的准确性以及在时间和空间方面的高效性.



Abstract:Pattern matching with gap constraints is one of the key issues of sequential pattern mining. Recently, most research work focuses on pattern matching with non-negative gaps, but the rule strictly limits the order that each character appears in the sequence. In order to increase the flexibility of matching while taking into account that it is more reasonable to use one-off condition in sequential pattern mining, this paper studies the pattern matching problem under general gap and one-off condition, which is NP-hard. To tackle this issue, an algorithm, named MSAING, is proposed. Firstly, the algorithm processes the pattern and sequence using the Reverse strategy to get the maximum number of matching results. Secondly, it significantly reduces the time and space overhead with linear table structure in the matching process, and improves the matching rate using the backtracking method. Finally, to further improve the efficiency of the algorithm, it determines whether internal repetition exists in the pattern or not, according to the inside_Checking mechanism. Completeness of the MSAING algorithm is proved in theory. Experimental results verify the accuracy of the matching results of the MSAING algorithm and its validity in terms of the time and space complexity.



PDF全文下载地址:

http://jos.org.cn/jos/article/pdf/5255
相关话题/序列 空间 实验 结构 模式

  • 领限时大额优惠券,享本站正版考研考试资料!
    大额优惠券
    优惠券领取后72小时内有效,10万种最新考研考试考证类电子打印资料任你选。涵盖全国500余所院校考研专业课、200多种职业资格考试、1100多种经典教材,产品类型包含电子书、题库、全套资料以及视频,无论您是考研复习、考证刷题,还是考前冲刺等,不同类型的产品可满足您学习上的不同需求。 ...
    本站小编 Free壹佰分学习网 2022-09-19
  • CFSv2模式对春季逐月南极涛动预测效能及成因分析
    摘要摘要:系统评估了美国第二代气候预测系统(CFSv2)对1983~2019年北半球春季逐月南极涛动(AAO)的预测效能及可能成因。结果表明,CFSv2模式对3月、4月和5月AAO空间模态预测效能较好,但是耦合模式仅对3月的AAO年际变化具有较好的预测能力,对4月和5月AAO年际变化的预测能力较差。 ...
    本站小编 Free考研考试 2022-01-02
  • CFSv2模式对春季逐月南极涛动预测效能及成因分析
    摘要摘要:系统评估了美国第二代气候预测系统(CFSv2)对1983~2019年北半球春季逐月南极涛动(AAO)的预测效能及可能成因。结果表明,CFSv2模式对3月、4月和5月AAO空间模态预测效能较好,但是耦合模式仅对3月的AAO年际变化具有较好的预测能力,对4月和5月AAO年际变化的预测能力较差。 ...
    本站小编 Free考研考试 2022-01-02
  • 基于降水遥相关型的夏季降水模式预测改进研究
    摘要摘要:我国月—季降水分布在空间上存在类似于大气环流遥相关的空间遥相关型。本文基于中国近57年夏季降水资料研究了我国夏季降水空间遥相关型的主要空间模态特征及其年代际变化,评估并改进了BCC_CSM模式、ECMWF_SYSTEM4模式以及NCEP_CFSV2模式对中国夏季降水的预测能力。研究结果显示 ...
    本站小编 Free考研考试 2022-01-02
  • 基于降水遥相关型的夏季降水模式预测改进研究
    摘要摘要:我国月—季降水分布在空间上存在类似于大气环流遥相关的空间遥相关型。本文基于中国近57年夏季降水资料研究了我国夏季降水空间遥相关型的主要空间模态特征及其年代际变化,评估并改进了BCC_CSM模式、ECMWF_SYSTEM4模式以及NCEP_CFSV2模式对中国夏季降水的预测能力。研究结果显示 ...
    本站小编 Free考研考试 2022-01-02
  • 中国动植物自然物候长序列数据集研制
    摘要摘要:中国气象档案馆馆藏1981年以来的木本、草本、虫鸟两栖动物自然物候观测资料,是现有中国境内覆盖范围最广、持续时间最长的自然物候观测数据。通过对数字化档案与电子报文进行数据清洗与质量控制,研制出1981~2018年中国动植物自然物候长序列数据集,分为木本、草本、虫鸟两栖动物3个子集。其中草本 ...
    本站小编 Free考研考试 2022-01-02
  • 中国动植物自然物候长序列数据集研制
    摘要摘要:中国气象档案馆馆藏1981年以来的木本、草本、虫鸟两栖动物自然物候观测资料,是现有中国境内覆盖范围最广、持续时间最长的自然物候观测数据。通过对数字化档案与电子报文进行数据清洗与质量控制,研制出1981~2018年中国动植物自然物候长序列数据集,分为木本、草本、虫鸟两栖动物3个子集。其中草本 ...
    本站小编 Free考研考试 2022-01-02
  • CMIP5耦合模式对欧亚大陆冬季雪水当量的模拟及预估
    摘要摘要:基于美国冰雪资料中心(NSIDC)提供的卫星遥感雪水当量资料,评估了26个CMIP5(CoupledModelInter-comparisonProject)耦合模式对1981~2005年欧亚大陆冬季雪水当量的模拟能力,在此基础上应用多模式集合平均结果,预估了21世纪欧亚大陆雪水当量的变化 ...
    本站小编 Free考研考试 2022-01-02
  • 气象—化学双向耦合模式(WRF-NAQPMS)研制及其在京津冀秋季重霾模拟中的应用
    摘要摘要:为解析大气污染物与气象的双向反馈机制及其对气象和环境的影响,建立基于Mie散射理论的气溶胶—光学性质模块,研制气象-化学双向耦合器,以嵌套网格空气质量预报模式NAQPMS(NestedAirQualityPredictionModelingSystem)为基础,建立了NAQPMS和中尺度气 ...
    本站小编 Free考研考试 2022-01-02
  • GRAPES_GEPS模式对2018年冬季欧亚地区500 hPa高压脊形势的预报效果评估
    摘要摘要:基于1979~2017年(共39年)NCEP/NCAR第一套再分析数据首先对欧亚大陆500hPa持续性高值[Persistentopenridgesandblockinghigh(maxima)of500hPageopotentialheight,PMZ]事件的气候分布特征进行了统计分析, ...
    本站小编 Free考研考试 2022-01-02
  • GRAPES_GEPS模式对2018年冬季欧亚地区500 hPa高压脊形势的预报效果评估
    摘要摘要:基于1979~2017年(共39年)NCEP/NCAR第一套再分析数据首先对欧亚大陆500hPa持续性高值[Persistentopenridgesandblockinghigh(maxima)of500hPageopotentialheight,PMZ]事件的气候分布特征进行了统计分析, ...
    本站小编 Free考研考试 2022-01-02