1. 概述
这一章节的内容没有数据结构的介绍,是单纯的算法,针对子字符的查找,介绍了四种常用的算法,包括暴力子字符串查找,KMP算法,Boyer-Moore算法,Rabin-Karp算法。并且在KMP算法中将初步介绍自动机的构造。
2. 算法部分
2.1. 暴力子字符串查找
2.1.1. 算法介绍
暴力查找的方法就是从文本字符串的第一个字符,一个一个的作为匹配串的开始,进行匹配,直到找到匹配的位置或者找不到目标子字符串返回文本长度。
1 | int normal_subsearch(string pat, string txt) |
2.1.2. 算法性质
暴力子字符串查找算法在长度为$N$的文本中查找长度为$M$的子字符串要~$NM$次比较。
2.2. KMP算法
2.2.1. KMP算法的思路
KMP算法是利用一次失败的匹配中前面已经被匹配的部分的信息来减少文本指针退回的算法。
这里我们的匹配过程仍然是$i$指向文本的字符,$j$指向模式的字符。$i$不断前进,永不退回;$j$会在模式中的某个字符上(初始时$i,j$同为0),每次都会使用$i$和$ j$指向的字符做对比。如果匹配,则$j$加一,同时$i$仍然保持前进一,如果不匹配,则$j$会退到前面的一个状态(字符)(这里的要退回的状态使用一个数组dfa[][]
来储存,第一个引索是文本中$i$指向的字符,第二个引索是当前状态,储存的值是退回(如果匹配则不退回,而是得到值$j+1$)的状态即新的j),$i$仍然加一,使得当前状态是匹配状态,然后继续对比新的$j$指向的模式字符和新的$i$指向的字符。
如下图所示,例如当前已经成功匹配了状态1,转移到了状态2,现在$j$为2准备和当前的$i$指向的字符匹配,假设文本中字符txt[i]
和模式的字符pat[j]
(此时是$A$)并不匹配,那么从图中知道此时要退回指针$j$,得到新的$j$,有j = dfa[txt[i]][j]
,那么根据图中所示不管txt[i]
是$B$还是$C$,都会使得$j$变成0。如此让$i$直接进行遍历,遇到不匹配就改变$j$然后继续匹配,可以最终实现子字符串的快速查找。
2.2.2. 确定有限状态自动机(DFA)
上面的算法思路理解后,其具体实现的核心就是这个能得到下一个状态的数组dfa[][]
了,首先我们先确定数组的初始可确定的元素,dfa[pat[0]][0] = 1
,dfa[][0] = 0
(即除了pat[0]
所在的都是0),dfa[pat[j]][j] = j+1
(匹配则到下一个状态)。这些是可以经过模拟和模型假设确定的。
那么剩下的元素其实都是不匹配的状况,我们使用一个重启状态$X$,同样是表示状态,它所代表的是在状态$j$范围内的模式子字符串的最长公共前后子字符串比如对于模式"ABCABDE"
,当j = 5
时,$X$为2,因为开始的AB和D之前的AB是$j$之前(不包含$j$)最长的公共前后子字符串。这个$X$,就是我们将要初步退回的状态(为什么是初步?因为还可能会二次退回,三次退回)。
为什么会选择这个作为退回状态,我们可以观察模式,很容易发现,在退回状态时只有$j$之前的前后的公共子字符串会使得退回状态数减少。在这里的具体例子里面模式的开头有AB,而在此时txt[i] = 'C'
( 假设是这个字符)在和pat[j] = 'D'
对比,不匹配,但是在D之前的前后公共子字符串是AB,那么实际上已经有了这个片段是已知和开头的前后子字符串匹配。那么我们完全可以让$i$不变,使得$j$指向$X$即2(对应模式第二个字符B),所以对应代码实际上有j = dfa[txt[i]][j]
, 而且其中dfa[txt[i]][j] == dfa[txt[i]][X]
,相当于将这个时候的不匹配下放到效果相同的$X$状态来处理,如此层层深入。这个时候我们的实际代码含义变成了j = dfa['c'][2]
,比对txt[i] = 'C'
和pat[j] = 'C'
,匹配,那么$j$会被加一。然后$i$指向下一个字符'E'
。如此继续这个过程,就可以完成算法。
2.2.3. 算法实现
代码如下
1 | class KMP |
2.2.4 算法性质
对于长度为$M$的模式字符串和长度为$N$的文本字符串,KMP算法访问的字符数不超过$M+N$。
2.3. Boyer-Moore算法
2.3.1. 算法原理
Boyer-Moore算法,这简称BM算法。其原理和KMP有一定相似之处,它的字符比较是从模式的末尾往前对比。对于算法过程,我们仍然用例子来说明。对于模式"BBAA"
,文本"ADAABABBAA"
,首先是有文本的位置指针$i$,和模式的指针$j$,此处指针是位置的意思,有初始时i = 0, j = 3
,即ADAA
和BBAA
先进行匹配,并且从后往前匹配,可以知道到$j$为1时发生不匹配,在BM算法里我们的处理是将$j$复位为3,将$i$向前移动到使得从$i$开始的长度与模式相同的子字符串中刚才发生不匹配的位置的字符状态变为匹配或者重置。在这里,我们观察到不匹配字符D,不在模式中出现,所以新的比对子字符串不应该包含之,故$i$移到2。
现在AABA
来进行匹配,在B处发生不匹配,$j$重新变为3,而由于B在模式中出现过,B在模式中出现的最靠近末尾的是位置1,而我们的移动应该使得移动距离最小,否则可能会有遗漏,我们移动$i$将文本中不匹配的B和模式中距离末尾最近的B对应上,这就是最优移动方式。(移动到不匹配处,显然不匹配;移动到非最近末尾的匹配会发生遗漏)那么$i$移动到3。
现在ABAB
进行匹配,第一个不匹配,同理,会移动$i$使得新的子字符串末尾的B与模式的最靠右的B匹配,那么$i$变化为5。这时匹配的是ABBA
,同理发生不匹配,会将$i$移动到6(这时可以看出,如果不是最靠右的匹配字符,则会遗漏)。匹配成功,返回位置i = 6
。
可以看出来,关键的实现步骤是这个移动的距离,显然匹配的字符不会引发移动,不匹配的字符不出现在模式中会使得$i$移动到$j+1$位置,出现在模式的字符,则会移动$i$将文本中出现不匹配的字符和模式中距离末尾最近的同样的字符对应上。假设其在模式中是位置$X$,那么应该移动$j - X$的距离。这样,我们的实现就可以完成了。
2.3.2. 算法实现
代码如下
1 |
|
2.3.3. 算法性质
一般情况下,对于长度为$N$的文本和长度为$M$的模式字符串,使用BM算法,需要$~N/M$次比较。
2.4. Rabin-Karp算法
2.4.1. 算法原理
这个算法是通过把模式当成R进制数,计算一个散列值,把文本所有同样长度子字符串的散列值计算出来,我们选取足够大的散列表,根据概率论可以将其视为不冲突的情况,所以和模式散列值相同的子字符串我们将它认为是找到了。这里我们不深入学习这个算法,仅学习其思想。
2.4.2. 算法实现
1 | class RK |
2.4.3. 算法性质
RK算法利用概率论的思想,使得算法以极高成功率完成,性能近线性。