【4.3】字符串的模式匹配

字符串的模式匹配:

  • 模式匹配 (pattern matching)
    • 一个目标对象 T(字符串)
    • (pattern)P(字符串)
    • 在目标 T 中寻找一个给定的模式P的过程
  • 应用
    • 文本编辑时的特定词、句的查找 UNIX/Linux: sed, awk, grep – DNA 信息的提取
    • 确认是否具有某种结构
  • 模式集合

用给定的模式 P,在目标字符串 T 中搜索与模式 P 全 同的一个子串,并求出 T 中第一个和 P 全同匹配的子 串(简称为”配串”),返回其首字符位置

为使模式 P 与目标 T 匹配,必须满足

p0 p1 p2 ...pm-1 = ti ti+1 ti+2 ... ti+m-1

模式匹配的目标和算法:

  • 目标:在大文本(诸如,句子、段落,或书本)中 定位(查找)特定的模式
  • 解决模式匹配问题的算法
    • 朴素(称为“Brute Force”,也称 “Naive” )
    • Knuth-Morrit-Pratt ( KMP) 算法 )
    • ……

一、朴素算法(穷举法)

设 T = t0t1, t2, …,tn-1,P = p0, p1, …, pm-1

  • i 为 T 中字符的下标,j 为 P 中字符的下标
  • 匹配成功 (p0 = ti , p1 = ti+1 , …, pm-1 = ti+m-1 ) ,即,T.substr(i, m) == P.substr(0, m)
  • 匹配失败 (pj≠ti ) 时, •将 P 右移再行比较
  • 尝试所有的可能情况

朴素模式匹配算法:其一

朴素模式匹配算法:其二

朴素模式匹配代码(简洁)

模式匹配原始算法:效率分析

假定目标 T 的长度为 n,模式 P 长度为 m,m≤n

  • 在最坏的情况下,每一次循环都不成功,则一共要进行比较(n-m+1)次
  • 每一次“相同匹配”比较所耗费的时间,是 P 和 T 逐个字符比较的时间,最坏情况下,共 m 次
  • 因此,整个算法的最坏时间开销估计为O( m * n )

朴素模式匹配算法:最差情况

模式与目标的每一个长度为 m 的子串进行比较

  • 目标形如 an-1 X
  • 模式形如 am-1b

总比较次数: m(n – m + 1)

时间复杂度: O(mn)

最佳情况-找到模式

在目标的前 m 个位置上找到模式,设 m = 5

总比较次数:m

时间复杂度:O(m)

最佳情况-没找到模式

  • 总是在第一个字符上不匹配
  • 总比较次数: n–m+1
  • 时间复杂度: O(n)

朴素算法的冗余运算

朴素算法之所以较慢的原因是有冗余运算

e.g.

  • 由1)可知: p5 ≠ t5, p0 ≠t0, p1 = t1,同时由 p0 ≠ p1可得知p0 ≠t2 故将 P 右移一位后第2) 趟比较一定不等; 比较冗余
  • 那么把 P 右移几位可以消除冗余的比较而不丢 失配串呢?

二、KMP算法

无回溯匹配

匹配过程中,一旦 pj 和 ti 比较不等时,即

P.substr(1,j-1) == T.substr(i-j+1,j-1)

但 pj ≠ ti

  • 该用 P 中的哪个字符 pk 和 ti 进行比较?
  • 确定右移的位数
  • 显然有k<j,且不同的j,其k值不同

Knuth-Morrit-Pratt (KMP)算法 : k 值仅仅依赖于模式 P 本身,而与目标对象T无关

KMP算法思想

字符串的特征向量N

设模式 P 由 m 个字符组成,记为 P = p0 p1p2p3……pm-1

令 特征向量 N 用来表示模式 P 的字符分布特征,简称 N 向量由m个特征数 n0 …nm-1 整数组成,记为 N = n0n1n2n3……nm-1

N 在很多文献中也称为 next 数组,每个 nj 对应 next 数组中的元素 next[j]

字符串的特征向量N:构造方法:

P 第 j 个位置的特征数 nj,首尾串最长的 k

  • 首串: p0 p1 … pk-2 pk-1
  • 尾串: pj-k pj-k+1 … pj-2 pj-1

KMP模式匹配示例

KMP模式匹配算法

对应的求特征向量算法框架:

特征数 nj ( j>0, 0≤ nj+1≤ j )是递归定义的, 定义如下:

  1. n0 = -1,对于j > 0的 nj+1 ,假定已知前一位置的 特征数nj,令k=nj ;
  2. 当k≥0且pj≠pk 时,则令k=nk;让步骤2循 环直到条件不满足
  3. nj+1 =k+1;//此时,k==-1或pj ==pk

字符串的特征向量N ——非优化版:

求特征向量N

字符串的特征向量N ——优化版

next数组对比

KMP算法的效率分析

循环体中”j = N[j];” 语句的执行次数不能超过 n 次。否则,

  • 由于“j = N[]; ”每执行一次必然使得j减少(至少减1)
  • 而使得 j 增加的操作只有“j++ ”
  • 那么,如果“j = N[j]; ”的执行次数超过n次,最终的结果必然 使得 j 为比-1小很多的负数。这是不可能的(j有时为-1,但是 很快+1回到0)。
  • 同理可以分析出求N数组的时间为O(m) 故,KMP算法的时间为O(n+m)

总结:单模式的匹配算法:

思考:不同版本特征值定义

更多阅读

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾

个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn

Sam avatar
About Sam
专注生物信息 专注转化医学