数学建模社区-数学中国
标题:
透彻理解Shift-And/Shift-Or 算法 字符串匹配/子串查找
[打印本页]
作者:
美人如花
时间:
2015-4-13 10:06
标题:
透彻理解Shift-And/Shift-Or 算法 字符串匹配/子串查找
Shift-And/Shift-Or 算法和KMP 算法一样，也是线性时间复杂度的字符串匹配算法，运行时间上甚至要比KMP 算法快得多。而理解上比KMP 算法更容易一些。Shift-And/Shift-Or 算法设计的非常巧妙，初次接触时同样“吓了一跳”。
0 t4 Z' \4 `6 s! H) k& ~
Shift-And 与 Shift-Or 算法的原理完全一样，区别仅在于Shift-Or 对Shift-And 做了一点儿改进。我们先说Shift-And 算法。
: q, L& O$ o; [' }2 `7 w4 F
) x: `) P$ n2 [+ X
S 表示原字符串，T 表示目标串（模式串），我们要在S 中搜索T。
, a. Q/ a; r- m% ~! E" m9 ?, x
令 S[0..m-1] = abcabcabdabba, T[0..n-1] = abcabd
( s( c J7 g3 t: Q. Q& h
- L' f5 P, p# w2 |, F
1，Shift-And 算法思想
$ w- w) Y; U8 u6 w8 |% U
Shift-And 算法的核心思想是利用掩码D 来记录模式串的前缀匹配情况。（瞧，shift 算法的核心也是前缀匹配）。Shift 算法大量应用了位运算。
# q) D1 ]1 A2 W
D 是一个m 位的无符号整数：D[n-1, n-2, ..,1,0] （注意D 并不是一个数组，仅仅是一个整数，D[n-1] 表示其最高位bit）。
7 f& O' Y' X! d4 g
数组索引i 控制S 串的扫描，当扫描的字符S
时，D 的第j 位D[j] = 1 当且仅当T[0..j] 是S[0..i] 的一个后缀。
: H- F- Q: g F) M4 g9 P7 x$ X
$ Z, y0 o+ M9 G7 o3 w {
要使用Shift 算法，需要一个辅助表B。B 是一个字典，key 是问题域字符集中的每个字符，value 是一个n 位无符号整数，记录该字符在模式串T 的哪些位置出现。
9 s. C; G$ \5 W
例如，字符c 在T[2] 处出现，那么B['c'] = 000100 （对于字符串，低位在左；对于B['c']，低位在右）；同理，a 在T[0],T[3] 处出现，B['a'] = 001001.
/ U p- V7 H% t# Q; D$ m/ L% y
; Q* f; ^3 u, ~& ^
假设当前处理到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]。
7 B* d% y p O( P; p
所以，D = (D << 1 | 1) & B[S[i］ ;
3 ^( ]; V. E6 |- @: ]8 N
显然，当D[n-1]=1 时，表示T[0..n-1] 是S[0..i] 的后缀，此时找到一个T的完全匹配。
2 G# z) |. q9 P( N
4 [) Z. U0 i/ C8 ~- S0 k
2，Shift-And 算法实现
) P# i$ L; i, v5 B8 v
Shift-And 匹配过程代码：
4 r5 r6 _. ~) T" r+ Z. c
3 |2 C7 b8 X3 s* W' A2 T* _
" T4 @' r* A* c8 p
由于位运算在计算机中可以并行进行，每次循环的执行是常数时间的，所以上面代码段的复杂度是 O(m)。
5 M% |8 `; P3 P2 f- L' `
# i4 Q5 I: }3 l7 ^; v. X0 U/ P
3，辅助表 B
& c6 W- M" C! [# a6 y N
上面没有提到如何得到辅助表B。很简单，只要获得模式串T 中每个字符出现的位置。
1 e! \' J" D* D
7 `1 e3 f9 }* O3 A6 j& y
0 u% d5 F4 {8 C( d
显然，上述代码段的复杂度是 O(n)。Shift-And 算法的时间复杂度是O(m+n)。
7 r5 H1 F& `3 t. [
实际上，shift 算法通常比KMP 算法的匹配速度要快，因为计算机位并行运算是非常高效的。
7 h p, i+ J+ @: S* }" \/ @! R5 L1 i. N
1 M1 V1 S7 x5 F. n! y0 X
注意：数组B 的大小是由字符集决定的，如果字符来自ASCII 码，字符的数值范围是0~127，数组大小是128 即可；否则，可能需要更大的数组B，或者自己构建字符到整数索引之间的散列关系。
1 w3 {6 a* u5 W
- B1 [! d9 g/ L9 Z
4，Shift-Or 算法
, a; Z( k: H! p7 P: }5 J
在Shift-And 中，对掩码D 的更新：D = (D << 1 | 1) & B[S[i］ ;
; X- m8 q! Y8 n3 _: d6 P, G8 x
每次更新D 都需要额外进行D 移位后与"1" 的"或"运算。这是由于我们要保证当字符S
在T[0] 处出现时，D[0] 一定要等于1，而D 向左移位后最低位是0。
+ q( x" [, g h( Q: @/ \+ g' g
0 i5 z& o5 q8 m
如果将Shift-And 中核心的“与” 运算改为“或” 运算，可以节省这一个附加的“或1” 运算。这正是Shift-Or 所改进的地方。
0 N0 A$ f5 P8 i2 y6 _( ^' d3 M
Shift-Or 与Shift-And 的唯一区别在于，在Shift-Or 中，“有效位” 是通过0（而不是1）来标识。
6 p+ n) w+ }" H! S! R" K! ~6 {' x |
于是求解辅助表B 和更新掩码D 都会与Shift-And 有一些区别，详见代码。
/ Y0 \/ X* A! {5 F" j1 d
6 c8 P& m! Z' L
Shift-And 完整代码：
C++ 实现
Python 实现
% [3 A7 q6 K% R6 U1 ?9 }7 J, W
Shift-Or 完整代码：
C++ 实现
Python 实现
* y- s# W* |" g( J4 b* E' C. \! r2 }$ H' K
& w8 _; K; P1 n# u# x; z$ [' t* l
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
