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

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

当前近似字符串匹配算法主要针对英文等中小字符集,该文针对汉字等大字符集的有效算法很少,尤其缺少适合汉字等大字符集的多模式近似匹配算法的情况,提出了一种适合汉字等大字符集的多模式近似匹配算法——MBPM—BM,通过实验证明了该算法的有效性。

维普资讯 doc.guandang.net

miL mi{ l≤q n= n m q 1≤r。假设计算机物理字长为 W位, r J且 个模式总长不超过 W,条件为

【 r n I 1 l№I+=。 最后的加 1既可保证单元的足够长度,又可作为相应模式的 bd值是否已经超过 k的判断标志。于是,利用一个物 as理字进行存储的所需条件为 r×L≤ W () 2

∑ q= l

2 . 1多模式赡跃引理 先作如下准备,B d() a。:针对模式 P,S中无用字符个 s 数。I o ()若存在 q s dc: Go、i(≤q,1≤m ) 1≤r≤i q,使 c,= 则为真,否则为假。类似地,引理 3,在中分别将满足 IG o () s o dc 为真或假的字符 C为有用或无用字符。s:针对模式 P,称? 在 BP中扫描至 T后的 S oe值。 M . cr 引理 3设 r个模式 P、 P, q 1’, …、对∈{….均有 S= r J q ,m,且i是使得 B d (j,+。)+ aq T+. ≥k 1的最小 i . L 1,则将 T+. i全 j1+1 .. j改为无用字符不影响 P、…、P与 T从 T开始的后续匹配。 .

显然当 miL 1、3 n=、2,且所有模式长度 m q均相等, 才有

∑m q= l

当模式长度 m。不全相等或 miL n≥4时,有

∑m r( g+】 x1 ̄ l l… l o q=l

因此任何时候均有

∑m r( g+ x l ̄ 1 1 l) o q =l r r 1一

实际上如能记住 T+ .右边的第一个有用字符 T,

则对 q∈

{-} 1.,均有 sja-…= qimq r qlt= Sj=,不必检测 T .l l跳+sI+ . 。可 1+

其

rL w于面∑中,x<弱前 w只保 ,需证 q=l

q=l

w可。即

至 T l处,并令 S+ ja+ t q,

=q m,继续扫描。

当然,实际中若超出计算机字宽 W的话,可串接多个字,本文为方便说明才提出上面假设。 为并行计算,S中 r个单元的初值均为 k,分割符为 1, 也就是 s 1 k为并行更新 S值,=(0+ )。单独创建一个数组 B】【, 用来并行记录不同模式对应的好字符、坏字符,定义为 r m。

22MB M- M主要思想 . P B () 1为使多个模式对齐,仅在满足多模式跳跃引理情况下才移动至新位置 j ls,+at函数 I o 0 s d作为记录和改变 ls值 Go at的判断条件; () 2令过滤窗口大小为 miL,多个模式右对齐 (略较 n忽长模式的左端部分 ),从窗口右端开始向左扫描; () ls记录扫描过程中遇到的有用字符最新位置,状 3用 at

B】∑∑g≠ 【= ( p)一 x 2 =I i =1

其中,x∈∑,函数 6() l当条件 C为真,否则为 0 C=。例如, 当 P= aab P= a a, n=,=, B a=0 0, 0】 ab b, cac miL 5 L 4则[][0 00 0, 0

态变量 S并行计算扫描过程中每个模式所对应的累计无用字 符总数 bd、…、bd。若 bd 1≤r均大于 k将 j l t al a a。(≤q ),+a s作为新窗口起点;若向左扫描到达窗口起始端,则采用 MBP M进一步对该区域进行匹配。状态变量 S的具体格式后面详述。 图 1给出了对 2个模式进行并行过滤的过程。 其中,/×分别表示多模式情况下的有用和无用字符,、和/ 为方便起见,图中只有 2个模式 P、P,长度为别为 m1 l 2、 m2且 m 1 m2。 .> 符

B[][0 0 0 1,Bc=00, 0】 b=O 0,00】[][0 1 0 0,对字符 x{,C, 0 ab}, 则 B[][0 1 0 1。 x=0 0, 0】 0

若 k2=,则 S的初值= 1 1,00。【0 01 1] 当扫描至位置 i,状态变量 S的更新公式为时 S S B T+=—【j】 l

因为 S中每个单元初值均为 k,所以只需判断每个单元标志位。定义变量 hg= 1’,形式化定义为 ih (O ) hi gh: 2q f, _ q

= l

于是可利用条件 (&hg )O来判断 S中是否还有不是 0 S - 的标志位,若 S中标志位全为 0,则满足多模式跳跃引理, 将位置 jls作为新过滤窗口起始位置。若向左扫描到达窗+at口起始端,则采用 MB M进行匹配。 P

L l l l ::L 卜————一 过滤窗口

二 L

——————

24更新 ls值 . at当前字符为有用字符时就更新 ls。定义变量 at o e= 0 1 n s (’ r,形式化定义为

多式跃理==== l—一模跳引奄===一—=卜 i n m I l2 - l+1 F

新过窗—的滤—— .

oHe s=

2(一)。 q。

m

l

[[二二二二1[二 圈 1多楱式囊跃弓理 I

q l=

当条件 ([j] o e) n s,更新 ls i B T+& n s≠o e时 i at。=

2 . 5多模式应用 B M P 多模式应用 B M, P可支持不同模式长度的 MB M。 P算法还用到模式匹配向量数组 P】思路类似 MB M,文献【】 M[, P但 3只给出相等模式长度下的示例,把它扩充到不同模式长度, 定义为

2 . 3并行记录多个 bd值 a由于统一采用 MiL作为过滤窗口的标准长度,因此每 n 个模式所对应的 b d as满足 0 a ̄MiL,但为了判断处理≤bd< n

的方便,调整了 b d值的设置方式,初值设为 k as,然后每次 遇到一个 bd字符就减 1 a,实际单元的取值范围为【—MiL k n, k。保存每个模式所对应的 b d值的相应单元的长度为】 as

P:∑( q(- ̄ - M】圭m6 im i_ 【 q ) q+ p2 )[ j - q:1 i =l

其中,x∈∑,定义如前。例如:当 P= aab c ac ab b,P= aa, 则 P a=0 10100】 M[][0 0,00 1,P c= 1 M【】【1 1,1 10,P b=O 0 00 1 1】 M【】【

0 0, 0 0】对于字符 x{,,} M[][0 0,0 0 0。 0 1 000, 0 a C,P x=0 0 0 0 0】 b 0 一

49一 _

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

上一页第2页

你可能喜欢

热门文档

相关文档

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