当前近似字符串匹配算法主要针对英文等中小字符集,该文针对汉字等大字符集的有效算法很少,尤其缺少适合汉字等大字符集的多模式近似匹配算法的情况,提出了一种适合汉字等大字符集的多模式近似匹配算法——MBPM—BM,通过实验证明了该算法的有效性。
维普资讯 doc.guandang.net
第 3卷第 2期 2 O V L3 o 2
计
算
机
工
程
20 0 6年 l O月 Oc o e 0 6 tb r 2 0
№
2 o
Comput rEng ne rng e i ei
软件技术与数据库
文章编号: oo 32( 0) _ s 3文献标识码。 1o- 48 o6 0枷4一】 2 2_ A
中圈分类号。T 31 P9
基于过滤的中文多模式近似字符串匹配算法 范立新,谢晓能,吴飞 (. 1浙江大学计算机学院,杭州 3 0 2;2绍兴文理学院计算机系,绍兴 3 2 0;3杭州广播电视大学信息工程学院,杭州 3 0 1) 10 7 10 0 . 10 2
攮
要:当前近似字符串匹配算法主要针对英文等中小字符集,文针对汉字等大字符集的有效算法很少,尤其缺少适合汉字等大字符集该 MB M— M, P B通过实验证明了该算法的有效性。
的多模式近似匹配算法的情况,出了一种适合汉字等大字符集的多模式近似匹配算法一提
关量词:近似字符串匹配;中文字符串匹配;多模式匹配;位并行运算;过滤
Al o ih f u t l p o i a eS r n g rt m 0 li eAp r x m t t i g M p f rCh n s o i e e Cha a t r s d 0 le i g r c e sBa e n Fi rn t FAN x n . I Xi one . U i Li i X E a ng W Fe
(. l g f o ue, hjagUnv r t, n zo 0 7 2 D p r n f o ue, h o igA s n ce c ies y 1Col eo mptrZ ein iesyHa gh u3 2; . e at t mp t S a xn r dS in e vri, e C i 1 0 me o C r t a Un t S o ig 310 0; . le eo n om ainEn n e n, n z o do& TV i est, n z o 0 2 ha x n 2 0 3 Colg fIf r to gie r g Ha g h uRa i i Unv riy Ha g h u31 01 )
[ sr c]Mot fh loi ms f p rxmaes n thaed s ndfr mal r d l s eo aat tUnin w po lC’f d Ab tat s o eag rh po i t r gma r ei e lo de i f h ce s . t o,
e pe a t n t t oa t i c g o s mi z cr re l n i a y e ce t l o t m sf rs a c n fmu tp ep te ns fl g i eof h a t rs t Th sp p rp e e t n a g rt n f in g r h e hi g o l l a t r e sz a c e e . i a e r s n sa l o i i a i o r i o a r cr hm—— M BP— M BM, i h C wh c a n b s d f rs a c n fmu t l a t r . p rme t l e u t h w h tMBP— e u e e hi g o l p e p t ns Ex e o r i e i n a s lss o t a r M BM r swe l n p a t ee p ca l n c i e e c a a tr t h wo k l i r c i s i ly i h n s h c e sma c . c e r
[ ywod]Ap rxmaes n th C iee tn th Mut l pt rs th Bt aal aclt n Fl r g Ke r s po i t r gmac; hn s r gma; lpe a en c; ip l l l ao; ie n t i si c i t ma—r e c u i ti
近似字符串匹配在病毒检测、语音识别、文件检索、计
处理。
算生物学、模式识别、O R纠错等许多领域有广泛应用,是 C 算法设计中的一个热点。可描述为:给定一个文本 T T.、= - - 一
() P B算法 I 2B M—M 若 M【j 0 T】,称 T无用字符;若 M【j≠0= . T】,称 T有用字 .
个模式 P P_以及允许的最大误差 k (<,找出满足=l _ k m)
符。其中 1≤m,M【≤j】的含义与 B M中模式匹配向量数组 P M【同。B ds表示 S中无用字符数, o ds表示 S】相 a( ) G o ()中有用字符数。S对应 B M中扫描至 T后的 S oe . P . cr值。一个有用字符最多使 S oe 1一个无用字符不会使 S oe 1若 S= cr减, c r减。 . m且 T是无用字符,则 S+ S= … _= jm。】
e(,) ds≤k的所有子串 S P。其中 e(,) S P2个字符串之 ds是和 P
间编辑距离的函数。当查找 r个模式 P, P时,…,就扩展成多 模式近似字符串匹配。即用户提
交 r个模式 P, P, T中 …,在
查找满足 e(,≤k的所有子串 S ds ) P,其中 1≤r≤q。每个模式 可有不同长度 m .m。 .,
引理 1若 S= im且 B dT+ . )+,有 S a(j1i≥k 1 .+…≥k 1+,其 中 1 i m。≤≤
l背景与相关研究 11符号表示 .用S代表任意字符串,、、 a b c代表字符,∑表示字符集, S s∈E,I表示其长度。S代表 S中第 i个字符,其中 i l i∈{, l】 1… S,用 S. I i表示 S s . j .。为简化描述,文中部分内容采 j用指数形式来表示位的二进制,如 01= 0 1。 0 0 1 设E是全体字符的集合,其大t Elo匹配文本 T∈ bl=, E,长度是 n,模式 P∈E的长度是 m,k∈ N表示允许的最大误差,o km代表误差率。距离函数 e: 。近 N似=/ dE×E一N
引理 2若 S=且 B dT+.≥k l l是从 T+开 jm a (j11 )+,T+ .+ i l 始从右往左数的第 k 1+个无用字符,则将 T+ T。 j1一全改为 .. 无用字符,不影响 P与 T从 T开始的后续匹配。 . 在引理 2前提下,可直接令 S+ m。 j=实际上若能记住 T+ i _ i 右边第 1个有用字符 T。 ,必有 S lt= s+ m,故可令 ja.…= j=+s1 i S lt= ja Im,然后继续扫描。+s -
本文把区域 T…T+ . m看作当前的过滤窗 I。算法思想: 1是:先确定过滤窗 I,然后从窗I右端开始向左扫描,变量: 1: 1 lt a记录最新遇到的有用字符位置, a s b d累计遇到的无用字符总数,一旦 b d大干 k则当前窗 I不满足匹配条件, jls a,: 1将+at 作为新窗 I起点,然后重新开始。若向左扫描到达窗 I起始: 1: 1
字符串匹配可定义为给定 T、P、e(,求解满足条件、k d. ) e (,i) dP ≤k的所有字符串 T. T . .始位置 i和终止位置 j。 或求解所有满足条件的开
1 .关算法介绍 2相 () P算法和 MB M算法 1B M P
端,则用 B M进一步对该区域进行匹配。 P
2多模式近似字符串匹配 设 r个模式 P, P…,的长度分别为 m…m,则 作者倚介:范立新( 6一) 1 8,男,士、讲师, 9硕
主研方向:计算机算 法,信息检索,数据库应用;晓能,硕士、讲师;吴谢 副教授
B M针对动态规划矩阵进行位并行运算,目前理论上 P是 最快的算法(非过滤方法)若计算机物理字长为 W位, B M。但 P只用到了其中 m位,文献【】 BP进行了扩充,若 r 3对 M个模式的总长不超过 W,即 r m<W,则同时搜索 r个模式。若 r
飞,士、博
个模式总长超过 W,将模式分组,按每组I/7个模式 1J 7
收穑日期:20——7 060 1 4
Ema:cc@zcs d. — i sl s . u n I x ae c

基于过滤的中文多模式近似字符串匹配算法_IT/计算机_专业资料 暂无评价0人阅读0次下载举报文档 基于过滤的中文多模式近似字符串匹配算法_IT/计算机_专业资料。...
· 基于过滤的中文多模式近似字符串匹配算法范立新1,2,谢晓能1,3,吴飞1 (1. 浙江大学计算机学院,杭州 310027;2. 绍兴文理学院计算机系,绍兴 312000;3. 杭州...
改进的中文近似字符串匹配算法_专业资料。BPM-BM算法在针对汉字等大字符集的... 基于过滤的中文多模式近... 7人阅读 4页 2.00 基于中文字符串匹配算法...
基于过滤的中文多模式近似... 4页 免费 一种单字符串精确模式匹配... 6页 免费 一种改进的字符串模式匹配... 5页 5财富值 字符串模式匹配算法的改进 5...
基于过滤的中文多模式近似... 4页 免费喜欢此文档的还喜欢 多模式匹配快速... 改进的多模式字符串匹配算法改进的多模式字符串匹配算法隐藏>> 第2 7卷第 6...
基于字符串近似匹配的模式生成算法_专业资料。本文提出一种字符串之间的模式... 一种改进的字符串多模式... 1人阅读 5页 3.00 基于过滤的中文多模式...
基于中文字符串匹配算法考试系统_计算机软件及应用_IT/计算机_专业资料。基于... 改进的中文近似字符串匹... 28人阅读 4页 2.00 基于过滤的中文多模式...
基于字符频率的字符串模式匹配算法的研究_化学_自然科学_专业资料。l 勺 化 麟 j 巫 喜红 ,凌 WU Xi—hong。.LING Jie 基于字符频率 的字符 串模式匹配...
信息过滤系统中字符串匹配算法的研究 陈小冬 1 程克非 400065 ) 摘要: 模式匹配是基于攻击特征的信息过滤系统中的网络数据包分析技术, 匹配算法的性 能直接影响到...
特殊情况,近似字符串匹配 的研究也同样重要.这里将对字符串匹配算法进行简要分析... 基于过滤的中文多模式近... 4页 免费 KMP字符串模式匹配详解 17页 免费...
热门文档