数学建模社区-数学中国
标题:
透彻理解Shift-And/Shift-Or 算法 字符串匹配/子串查找
[打印本页]
作者:
美人如花
时间:
2015-4-13 10:06
标题:
透彻理解Shift-And/Shift-Or 算法 字符串匹配/子串查找
Shift-And/Shift-Or 算法和KMP 算法一样，也是线性时间复杂度的字符串匹配算法，运行时间上甚至要比KMP 算法快得多。而理解上比KMP 算法更容易一些。Shift-And/Shift-Or 算法设计的非常巧妙，初次接触时同样“吓了一跳”。
# _4 y4 _! ^# C0 Y
Shift-And 与 Shift-Or 算法的原理完全一样，区别仅在于Shift-Or 对Shift-And 做了一点儿改进。我们先说Shift-And 算法。
' J) r1 X1 ?8 g4 e7 L" {6 i0 ~5 E
+ l6 [( [! S4 g$ T9 k% n3 |
S 表示原字符串，T 表示目标串（模式串），我们要在S 中搜索T。
1 o w$ L9 `3 c, f- z
令 S[0..m-1] = abcabcabdabba, T[0..n-1] = abcabd
2 P, A7 ~% B4 ]9 N. T9 @
1 i: `$ q0 Q- F0 w( ^6 A
1，Shift-And 算法思想
' r2 l. w4 n2 R' Q7 n: G
Shift-And 算法的核心思想是利用掩码D 来记录模式串的前缀匹配情况。（瞧，shift 算法的核心也是前缀匹配）。Shift 算法大量应用了位运算。
$ g a7 \0 @% q$ J0 e( w! N, E
D 是一个m 位的无符号整数：D[n-1, n-2, ..,1,0] （注意D 并不是一个数组，仅仅是一个整数，D[n-1] 表示其最高位bit）。
) r5 [- R9 }2 {$ O2 B
数组索引i 控制S 串的扫描，当扫描的字符S
时，D 的第j 位D[j] = 1 当且仅当T[0..j] 是S[0..i] 的一个后缀。
( T& O R4 E5 a" d' a' N
. S' D y# n$ P, b% a7 D1 O5 p
要使用Shift 算法，需要一个辅助表B。B 是一个字典，key 是问题域字符集中的每个字符，value 是一个n 位无符号整数，记录该字符在模式串T 的哪些位置出现。
5 L+ x6 U5 ]2 [6 Q8 b
例如，字符c 在T[2] 处出现，那么B['c'] = 000100 （对于字符串，低位在左；对于B['c']，低位在右）；同理，a 在T[0],T[3] 处出现，B['a'] = 001001.
# Z- h' M9 M6 h8 T! u4 ^
+ S% o+ C( |+ C$ x1 v- x0 X
假设当前处理到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]。
0 o- w: O8 l9 t( I8 L9 K* h& d8 M
所以，D = (D << 1 | 1) & B[S[i］ ;
) F) W1 O9 }% \0 {
显然，当D[n-1]=1 时，表示T[0..n-1] 是S[0..i] 的后缀，此时找到一个T的完全匹配。
! C! w( f0 L# W s u
; Y$ P% B+ K( d# R: i
2，Shift-And 算法实现
. W( `6 v. l6 ?) D9 w& D: Y
Shift-And 匹配过程代码：
: X% q/ p% T1 M
, o/ x( J! T# l
( x9 G% B* {* X8 ?! T0 y( x6 b4 {
由于位运算在计算机中可以并行进行，每次循环的执行是常数时间的，所以上面代码段的复杂度是 O(m)。
5 I/ E. y/ _6 ~3 [! j$ [ C
6 q& @: A* o4 S& P+ F- N1 w
3，辅助表 B
% k$ ` f% \; A, k5 n+ p: p2 x" h
上面没有提到如何得到辅助表B。很简单，只要获得模式串T 中每个字符出现的位置。
, l, t& E9 _1 Z8 B8 r3 Z }
. D' f- }* u4 f+ W% Q5 G/ s
8 |! }0 G; i: Z+ W* a; |
显然，上述代码段的复杂度是 O(n)。Shift-And 算法的时间复杂度是O(m+n)。
' i$ p2 x3 g! i1 A f+ [4 {' w; }
实际上，shift 算法通常比KMP 算法的匹配速度要快，因为计算机位并行运算是非常高效的。
$ O) s0 `- g& Z8 F" S
* W- W% G3 K, \* D$ A @# {& V
注意：数组B 的大小是由字符集决定的，如果字符来自ASCII 码，字符的数值范围是0~127，数组大小是128 即可；否则，可能需要更大的数组B，或者自己构建字符到整数索引之间的散列关系。
; C! x! w7 |/ T! c+ j
- j; O2 M& F) E7 ~, J4 H
4，Shift-Or 算法
2 Z* t$ y( X& ~
在Shift-And 中，对掩码D 的更新：D = (D << 1 | 1) & B[S[i］ ;
3 @5 L3 f& O1 t2 O
每次更新D 都需要额外进行D 移位后与"1" 的"或"运算。这是由于我们要保证当字符S
在T[0] 处出现时，D[0] 一定要等于1，而D 向左移位后最低位是0。
$ t& P4 N; O5 U1 L
. _' X, w/ E4 P/ ]
如果将Shift-And 中核心的“与” 运算改为“或” 运算，可以节省这一个附加的“或1” 运算。这正是Shift-Or 所改进的地方。
+ |# C" s3 P, }7 @( g- n
Shift-Or 与Shift-And 的唯一区别在于，在Shift-Or 中，“有效位” 是通过0（而不是1）来标识。
& I+ e' N% J0 t/ _2 |
于是求解辅助表B 和更新掩码D 都会与Shift-And 有一些区别，详见代码。
+ [6 I" a/ p: W& a6 X9 [+ ]! F4 [: d$ X
/ z+ H2 S: E# P( s( D$ H% B
Shift-And 完整代码：
C++ 实现
Python 实现
* a; X5 ^% y& r4 J
Shift-Or 完整代码：
C++ 实现
Python 实现
# t/ Y6 o2 G; B* J2 X
, B9 I" H+ p$ T
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
