Mengzelev's Blog

算法导论学习笔记-字符串匹配

Word count: 1,626 / Reading time: 7 min
2019/03/23 Share

基本知识

问题的形式化定义

  • 文本是一个长度为$n$的数组$T[1,…n]$
  • 模式是一个长度为$m$的数组$P1,…m$
  • $P$和$T$的元素都是来自一个有限字母集$\Sigma$的字符
  • 若$0\le s\le n-m$,且$T[s+1,…s+m]=P[1,…m]$,则称模式$P$在文本$T$中出现,且偏移为$s$(模式$P$在文本$T$中出现的位置是$s+1$开始的)
  • 如果$P$在$T$中以偏移$s$出现,那么称$s$是有效偏移,否则是无效偏移
  • 字符串匹配问题:找到所有的有效偏移
  • 算法总运行时间=预处理时间+匹配时间

符号和术语

  • $\Sigma^*$: 包含所有有限长度的字符串的集合
  • $\varepsilon$: 长度为0的空字符串,$\varepsilon\in\Sigma^*$
  • $|x|$: 字符串$x$的长度
  • $xy$: 两个字符串$x$和$y$的连结(concatenation)
  • 若对某个字符串$y\in \Sigma^*$有$x=wy$,则称字符串$w$是字符串$x$的前缀,记作$w\sqsubset x$
  • 若对某个字符串$y$有$x=yw$,则称字符串$w$是字符串$x$的后缀,记作$w\sqsupset x$
  • 空字符串$\varepsilon$同时是任何一个字符串的前缀和后缀
  • $x\sqsupset y$当且仅当$xa\sqsupset ya$
  • $\sqsubset$和$sqsupset$都是传递关系

引理32.1(后缀重叠引理): 假设$x,y$满足$x\sqsupset z$和$y\sqsupset z$的字符串。如果$|x|\le |y|$, 那么$x\sqsupset y$; 如果$|x|\ge |y|$, 那么$y\sqsupset x$; 如果$|x|=|y|$, 那么$x=y$

  • 把模式$P[1..m]$的由$k$个字符组成的前缀$P[1..k]$记作$P_k$,因此$P_0=\varepsilon$,$P_m=P=P[1..m]$
  • 把文本$T$中由$k$个字符组成的前缀记为$T_k$
  • 采用这种记号,字符串匹配问题能被表述为:找到所有偏移$s(0\le s\le n-m)$, 使得$P\sqsupset T_{s+m}$
  • 假设:检测$x==y$需要时间$\Theta(t+1)$,其中$t$是满足$z\sqsubset x$和$z\sqsubset y$的最长字符串$z$的长度

朴素字符串匹配算法

通过循环找到所有有效偏移
对$n-m+1$个可能的$s$进行检测

运行时间

最坏情况下:$O((n-m+1)m)$
无预处理时间

Rabin-Karp算法

为了便于说明,假设$\Sigma={0,1,2,…,9}$
在通常情况下可以假定每个字符都是以$d$为基数表示的数字
$p$: 模式$P$表示的十进制值
$t_s$: 文本$T[s+1..s+m]$对应的十进制值
把字符串匹配转化为数值匹配

计算$t_1,…t_s$时,可以根据$t_s$计算$t_{s+1}$
$$t_{s+1}=10(t_s-10^{m-1}T[s+1])+T[s+m+1]$$
(去掉高位数字,左移,加上低位数字)

如果$p$和$t_s$的值太大,可以选取一个合适的模$q$来计算$p$和$t_s$的模
在一般情况下,选取一个$q$,使得$dq$在一个计算机字长内,调整递归式
$$t_{s+1}=(d(t_s-T[s+1]h)+T[s+m+1])\mod~q$$
其中$h\equiv d^{m-1}(mod q)$是一个具有$m$数位的文本窗口的高位数位上的数字”1”的值

运行过程

  • 计算所有长度为$m$的文本窗口对$q$取模的值
  • 找出$t_s\equiv q(\mod~q)$的$s$值(伪命中点)
  • 进行字符串匹配检验

伪代码

  • 去除$t$的下标不会影响程序运行
  • 循环不变量:$t_s=T[s+1…s+m]\mod~q$

运行时间

预处理:$\Theta(m)$
最坏情况运行时间: $\Theta((n-m+1)m)$(e.g.$P=a^m$且$T=a^n$时需要对所有可能进行字符串匹配验证,相当于退化为朴素算法)

若有效便宜只有常数$c$个,算法的期望匹配时间为$O((n-m+1)+cm)=O(n+m)$

若假设$q$是从适当大的整数中随机得出的,则伪命中的次数为$O(n/q)$(因为任意$t_s$模A$q$与$p$同余的概率为$1/q$)。 第10行中的测试会在$O(n)$个位置上失败,每次命中的时间代价是$O(m)$。因此Rabin-Karp算法的期望运行时间是$$O(n)+O(m(v+n/q))$$其中$v$为有效偏移量

若选取的素数$q$大于模式的长度,则可以估计Rabin-Karp算法的匹配时间为$O(n+m)=O(n)$

利用有限自动机进行字符串匹配

有限自动机

一个有限自动机$M$是一个五元组$(Q,q_0,A,\Sigma,\delta)$,其中:

  • $Q$是状态的有限集合
  • $q_0\in Q$是初始状态
  • $A\subseteq Q$是一个特殊的接受状态集合
  • $\Sigma$是有限输入字母表
  • $\delta$是一个从$Q\times\Sigma$到$Q$的函数,称为$M$的转移函数

状态转移

  • 开始状态为$q_0$,每次读入输入字符串的一个字符
  • 如果在状态$q$时读入字符$a$,就从状态$q$变为状态$\delta(q,a)$(进行了一次转移)
  • 当前状态$q\in A$时,就说$M$接受了迄今为止所读入的字符串,没有被接受的输入称为被拒绝的输入

终态函数

终态函数$\phi:\Sigma^*\to Q$
$\phi(w)$: $M$在扫描字符串$w$后终止时的状态
当且仅当$\phi(w)\in A$时,$M$接受字符串$w$

用转移函数递归定义$\phi$:
$$\phi(\varepsilon)=q_0,$$
$$\phi(wa)=\delta(\phi(w),a), ~~w\in\Sigma^*,a\in\Sigma$$

字符匹配自动机

后缀函数$\sigma:\Sigma^*\to{0,1,…,m}$,满足$\sigma(x)$是同时是$x$的后缀和$P$的前缀的字符串的长度
$$\sigma(x)=\max{k:P_k\sqsupset x}$$

对于任意的状态$q$和字符串$a$,转移函数$\delta$定义如下:
$$\delta(q,a)=\sigma(P_qa)$$
记录已得到的与模式$P$匹配的文本字符串$T$的最长前缀

匹配时间为$\Theta(n)$

正确性证明

引理32.2(后缀函数不等式): 对任意字符串$x$和字符$a$,$\sigma(xa)\le\sigma(x)+1$

引理32.3(后缀函数递归引理): 对任意$x$和字符$a$,若$q=\sigma(x)$,则$\sigma(xa)=\sigma(P_qa)$

定理32.4: 如果$\phi$是字符串匹配自动机关于给定模式$P$的终态函数,$T[1..n]$是自动机的输入文本,则对$i=0,1,..,n,\phi(T_i)=\sigma(T_i)$(终态函数的值=后缀函数的值)

计算转移函数

计算转移函数的运行时间为$O(m^3|\Sigma|)$,可以改进为$O(m\Sigma)$

CATALOG
  1. 1. 基本知识
    1. 1.1. 问题的形式化定义
    2. 1.2. 符号和术语
  2. 2. 朴素字符串匹配算法
    1. 2.0.1. 运行时间
  • 3. Rabin-Karp算法
    1. 3.1. 运行过程
    2. 3.2. 伪代码
    3. 3.3. 运行时间
  • 4. 利用有限自动机进行字符串匹配
    1. 4.1. 有限自动机
      1. 4.1.1. 状态转移
      2. 4.1.2. 终态函数
    2. 4.2. 字符匹配自动机
    3. 4.3. 正确性证明
    4. 4.4. 计算转移函数