QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 3634|回复: 0
打印 上一主题 下一主题

[其他资源] 透彻理解Shift-And/Shift-Or 算法 字符串匹配/子串查找

[复制链接]
字体大小: 正常 放大

14

主题

10

听众

43

积分

升级  40%

  • TA的每日心情
    慵懒
    2015-5-5 09:46
  • 签到天数: 10 天

    [LV.3]偶尔看看II

    自我介绍
    撒
    跳转到指定楼层
    1#
    发表于 2015-4-13 10:06 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    Shift-And/Shift-Or 算法和KMP 算法一样,也是线性时间复杂度的字符串匹配算法,运行时间上甚至要比KMP 算法快得多。而理解上比KMP 算法更容易一些。Shift-And/Shift-Or 算法设计的非常巧妙,初次接触时同样“吓了一跳”。5 S% E" m! z$ Y0 N7 b( l
    Shift-And 与 Shift-Or 算法的原理完全一样,区别仅在于Shift-Or 对Shift-And 做了一点儿改进。我们先说Shift-And 算法。
    1 K0 @. Z  H- L1 Q
    4 p9 }2 }* _& U) M2 DS 表示原字符串,T 表示目标串(模式串),我们要在S 中搜索T。
    ' D6 u& i  r3 O% Y: m令 S[0..m-1] = abcabcabdabba, T[0..n-1] = abcabd5 D) D6 F5 J6 ^+ k
    5 U" r7 v; i7 o7 s- ]* L
    1,Shift-And 算法思想$ X% f0 w; G" \2 M) \
    Shift-And 算法的核心思想是利用掩码D 来记录模式串的前缀匹配情况。(瞧,shift 算法的核心也是前缀匹配)。Shift 算法大量应用了位运算。
    ; {, d. q5 z/ n9 Z( X3 JD 是一个m 位的无符号整数:D[n-1, n-2, ..,1,0] (注意D 并不是一个数组,仅仅是一个整数,D[n-1] 表示其最高位bit)。
    6 G$ W7 ^+ [+ g4 N* Q* i( d数组索引i 控制S 串的扫描,当扫描的字符S 时,D 的第j 位D[j] = 1 当且仅当T[0..j] 是S[0..i] 的一个后缀。
    : {  ?. d" z) u; w3 O" b% y
    4 m' b' h4 _$ C/ j3 {要使用Shift 算法,需要一个辅助表B。B 是一个字典,key 是问题域字符集中的每个字符,value 是一个n 位无符号整数,记录该字符在模式串T 的哪些位置出现。( s& z# t, l0 a% [7 G+ m
    例如,字符c 在T[2] 处出现,那么B['c'] = 000100 (对于字符串,低位在左;对于B['c'],低位在右);同理,a 在T[0],T[3] 处出现,B['a'] = 001001.
    5 J7 Z, Q; ?  e. V" T( Z
    ) E- H$ S  ?) |: m$ X  o9 t假设当前处理到S,需要对D 进行更新。由于D[j] (0<j<n) 标识T[0..j] 是否是S[0..i] 的后缀,所以D[j]=1 当且仅当更新前的D[j-1]=1 并且S==T[j];D[0] 是边界情况,D[0]=1 当且仅当S==T[0]。
    5 l7 }, F0 G+ A! G" h* l2 N所以,D = (D << 1 | 1) & B[S[i] ;
    6 t* T4 Z& `  _& }7 D: _/ M! ^显然,当D[n-1]=1 时,表示T[0..n-1] 是S[0..i] 的后缀,此时找到一个T的完全匹配。; k/ D8 S& e% [: a- f( x
    + j+ [5 B# b- c) L. b! O# r
    2,Shift-And 算法实现2 y- }6 J$ J% E  e; K: q
    Shift-And 匹配过程代码:
    ! c% Z9 B( |5 _. `6 h# z

    1 l3 L- n, B2 w) [5 C2 C! E4 {7 ^: G9 J% u. Z! q) P5 @) _7 R! C
    由于位运算在计算机中可以并行进行,每次循环的执行是常数时间的,所以上面代码段的复杂度是 O(m)。
    ! i* t4 b! A& [  n( F! K. h: l5 K! r$ \' h4 w4 M
    3,辅助表 B
    6 v" v& c+ X* \& w1 ]# t  l/ v上面没有提到如何得到辅助表B。很简单,只要获得模式串T 中每个字符出现的位置。
    ' _6 s& M' x0 b0 p# e4 D

    / |5 I3 T0 x5 \  x2 d
    " W+ J* U' ~/ K% {% C! |显然,上述代码段的复杂度是 O(n)。Shift-And 算法的时间复杂度是O(m+n)。
    9 V1 t- g: n1 R& z* p实际上,shift 算法通常比KMP 算法的匹配速度要快,因为计算机位并行运算是非常高效的。
    9 i  ?+ f& }. k* S' I5 k- s
    ' }$ N; V. n7 ~+ f0 U5 \注意:数组B 的大小是由字符集决定的,如果字符来自ASCII 码,字符的数值范围是0~127,数组大小是128 即可;否则,可能需要更大的数组B,或者自己构建字符到整数索引之间的散列关系。
    9 b6 W& K, U/ Y: f* Q; K# t6 Y5 F- P: @  \& O: F  ?' O. k
    4,Shift-Or 算法( H9 H! `# d$ l- l
    在Shift-And 中,对掩码D 的更新:D = (D << 1 | 1) & B[S[i] ;, k/ U7 P" v( m6 h; D' F
    每次更新D 都需要额外进行D 移位后与"1" 的"或"运算。这是由于我们要保证当字符S 在T[0] 处出现时,D[0] 一定要等于1,而D 向左移位后最低位是0。  E, x0 H# P( ]; `6 i

    # ]( |+ A8 x+ x$ F如果将Shift-And 中核心的“与” 运算改为“或” 运算,可以节省这一个附加的“或1” 运算。这正是Shift-Or 所改进的地方。& S0 j. c6 @/ T+ C6 X
    Shift-Or 与Shift-And 的唯一区别在于,在Shift-Or 中,“有效位” 是通过0(而不是1)来标识。# L1 _* J* p0 w. O0 c$ x- T
    于是求解辅助表B 和更新掩码D 都会与Shift-And 有一些区别,详见代码。" U0 T# k2 f$ I! [2 w1 w
    ! H2 p$ I  o9 h$ J
    Shift-And 完整代码:C++ 实现  Python 实现
    + `& G" D  d+ z2 m: v1 {" |Shift-Or 完整代码:C++ 实现  Python 实现
    2 t* [8 s7 i1 w+ ?
    9 N% y# j% z. L! p
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    fastpost qq
    收缩
    • 电话咨询

    • 04714969085

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-11-23 05:13 , Processed in 0.466391 second(s), 54 queries .

    回顶部