rambo

字符串匹配(二)有限自动机

有限自动机,通过对文本字符串T进行扫描,找出模式P的所有出现位置。它们只对每个文本字符检查一次,并且检查每个文本字符时所用的时间为常数。因此,在模式预处理完成并建立好自动机后进行匹配所需要的时间为\Theta(n)。预处理的时间为O(m|\Sigma|)

QQ截图20150826002148

有限自动机开始于状态q_{0},每次读入输入字符串的一个字符。如果有限自动机在状态q时读入了字符a,则它从状态q变为状态\delta(q,a)。每当当前状态q属于A时,就说自动机M接受了迄今为止所读入的字符串。

QQ截图20150826003004

状态1(被涂黑)是唯一的接受状态。

\delta(0,a)=1,\delta(1,b)=0,\delta(0,a)=1,\delta(1,a)=0,\delta(0,a)=1。因而接受abaaa这个输入。

有限自动机M引入一个状态函数\phi,称为终态函数,它是从\Sigma^{*}到Q的函数,满足\phi(w)是M在扫描字符串w后终止时的状态。当且仅当\phi(w)\in A时,M接受字符串w。(A\in Q是一个特殊的接受状态集合。利用状态转移函数递归定义\phi

\phi(\epsilon)=q_{0}

\phi(wa)=\delta(\phi(w),a),w\in\Sigma^{*},a \in\Sigma

假设文本长度为n,模式长度为m,则自动机将会有0,1,...,m这么多种状态,并且初始状态为0。在从文本从左到右扫描时,对于每一个字符a,根据自动机当前的状态还有a的值可以找出自动机的下一个状态,这样一直扫描下去,并且一定自动机状态值变为m的时候我们就可以认为成功进行了一次匹配。

后缀函数

定义一个辅助函数sigma,函数\sigma是一个从\Sigma^{*}\{0,1,...,m\}的映射。

举例解释:对于模式P=ab,有\sigma(\epsilon)=0,\sigma(ccaca)=1,\sigma(ccab)=2。对于一个长度为m的模式P,\sigma(x)=m当且仅当x\in P

有限自动机定理:

  • 状态集合Q为\{0,1,...,m\}。开始状态q_{0}是0状态,并且只有状态m是唯一被接受的状态。
  • 对于任意的状态q和字符a,转移状态函数delta定义为

\delta(q,a)=\sigma(P_{q}a),

也就是记录已得到的与模式P匹配的文本字符串T的最大前串。

假设现在文本和模式只有三种字符a,b,c,已经文本T为"abababaca",模式P为"ababaca",根据模式P建立自动机如下图(b)(先不管实现细节):

QQ截图20150826004624

如图(c),对照自动机转换图(b),一个个的扫描文本字符,扫描前状态值初始化为0,这样在i = 9的时候状态值刚好变成7 = m,所以完成一个匹配。

建立模式P = "ababaca"的有限自动机。首先需要明白一点,如果当前的状态值为k,其实说明当前文本的后缀与模式的前缀的最大匹配长度为k,这时读进下一个文本字符,即使该字符匹配,状态值最多变成k + 1.假设当前状态值为5,说明文本当前位置的最后5位为"ababa",等于模式的前5位。

如果下一位文本字符是"c",则状态值就可以更新为6.如果下一位是"a",这时我们需要重新找到文本后缀与模式前缀的最大匹配长度。简单的寻找方法可以是令k = 6(状态值最大的情况),判断文本后k位与模式前k位是否相等,不等的话就k = k - 1继续找。由于刚才文本后5位"ababa"其实就是模式的前5位,所以实际上构建自动机时不需要用到文本。这样可以找到这种情况状态值将变为1(只有a一位相等)。同理可以算出下一位是"b"时状态值该变为4(模式前4位"abab"等于"ababab"的后缀)。请对照图(c)进行理解。