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

基于过滤的中文多模式近似字符串匹配算法_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页 免费...
热门文档