文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 信息与通信 > 基于过滤的中文多模式近似字符串匹配算法
侵权投诉

基于过滤的中文多模式近似字符串匹配算法

当前近似字符串匹配算法主要针对英文等中小字符集,该文针对汉字等大字符集的有效算法很少,尤其缺少适合汉字等大字符集的多模式近似匹配算法的情况,提出了一种适合汉字等大字符集的多模式近似匹配算法——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

基于过滤的中文多模式近似字符串匹配算法

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email