单模式匹配-KMP

在很多应用中,例如计算tf-idf,我们都希望有一个算法能够快速返回字符串B(模式串,长度M)是否包含在字符串A(主串,长度N>>M),以及包含的位置。最暴力的解决方式就是两层循环,外层遍历A,内层遍历B,一旦出现匹配失误,外层的index就加1,复杂度是O(M·N)。我们令两个指针pA和pB分别指向当前正在比较的A和B的位置,你会发现这个算法做了很多无用功,因为一旦匹配失败,pA就会“回头”。KMP算法的基本思想就是避免“回头”,使得复杂度降到O(N)。

具体来说,KMP需要提前为模式串B生成一个辅助数组next,next[i]的包含的信息是:如果i位置字符匹配失败,则模式串至少需要前移k个字符(k>0),保证B[0:i-k-1]==B[k:i-1]。有了这个数组,就不用“回头”了,一旦B[i]和A[t]匹配失败,只需要继续比较A[t+1]和B[next[i]](next[i]存储i-k)。

下面的问题就是如何生成next数组。当然了,最暴力的方式同样是一个一个试,复杂度为O(N^2)。为了避免重复计算,我们自然而然的就会想到能否借助动态规划来解决这个问题。假设我们已经算好了next[0],…,next[i-1],next[i]能否借助这些前面的“状态”生成呢?首先我们看next数组相邻的两位。next[i]是否包含next[i-1]?可以肯定的是next[i]一定<=next[i-1]+1,因为用反证法,如果next[i]>next[i-1]+1,则将next[i-1]赋值为next[i]-1能得到更优的解。也就是说,如果B[i-1]==B[next[i-1]],则next[i]一定等于next[i-1]+1;如果B[i-1]!=B[next[i-1]],则next[i]一定小于等于next[i-1],这样一来,next[i]就一定<=next[next[i-1]]+1(证明同样用反证法)。这样,我们可以不挺尝试“上界”,这样保证最优解不会被漏掉。

多模式匹配-字典树与后缀树

利用KMP算法,可以在O(N)的时间复杂度内,算出主串A是否包含B,而且稍加修改(next数组延长一位,next[B.length]),就可以找到所有出现B的位置。但是在实际计算tf-idf时,我们往往有k主串(文档doc)和p
个模式串(单词term),如果简单的多次运行KMP,最后的时间复杂度则为O(N·k·p),往往term的个数非常多,这样的时间复杂度会吃不消。

降低复杂度,就要少做重复的事,我们稍微想一下这k·p次KMP算法,就会发现其中有很多重复的比较。例如,假设模式串B1是abcd,B2是abce,其实对’abc’的比较就进行了两次。程序=算法+数据结构,这个是我们刚上计算机课就学的“醒世恒言”,高效的程序不仅要算得好,还要存得好。说到这,估计大家就会想到用树来组织数据了,下面将会介绍字符串处理中常用的两种树(本质上是一种):字典树Trie,以及字典树的进化版-后缀树

字典树-模式串

我们可以将所有的模式串组织成一颗字典树,然后把next数组附加到这棵树上(实际就是在后代和祖先节点间连了很多指针)。这样,如果两个模式分别是abcd和abce,在进行abc的比较时,就只用比较一次。我们可以这样理解这个问题,对于某个主串A,有p个模式要检测。不用字典树,就会有p个指针,在A上一个字符一个字符的递进,每次递进一个字符,p个指针就要比较p次;使用字典树的情况下,多个指针可能指向的是同样的“前缀”,例如前面abc的例子,实际上这些指针指向了同一个树中的节点,因此减少了比较的次数。但是最坏的情况下,树上仍可能同时有p个指针。那可不可能把这p个指针合为一个呢?也就是说,能否把复杂度从O(N·k·p)降到O(N·k),看起来好像多模式匹配就像单模式一样,与模式串个数无关呢?这就引出来AC自动机。

我们换这个角度来想这个问题:一个主串,长度为N,p个模式串,平均长度为M。我们把这颗Trie当成一个自动机,随着主串的输入,不停的进行状态转移(像编译原理那样)。Tire上的节点就是自动机的状态,每个节点保存两个变量(1)无法进行下一步转移时(孩子节点匹配失败),至多会退到哪个节点(和KMP的next一模一样,就是上一段说的后代与祖先间的指针)(2)以当节点结尾的模式串。(1)可以很方便的获得(KMP),(2)其实也一样,令当前节点为v,以v结尾的模式串集合为P(v),P(v)=L(v)+P(next[v]),其中L(v)是当前节点在Trie中代表的模式,L(v)可能为空,不为空也就只能有一个元素。通过观察,我们发现,(1)和(2)都可以由Trie上的bfs得到(因为next[v]的深度一定小于v的深度)。

具体的AC自动机算法解析可见这里

后缀树-主串

上面的方法是将所有模式串做了预处理,主串并没有做任何处理。这节所讲的后缀树,就是用来组织多个主串的(当然了,一个也可以),以求进一步降低复杂度。后缀树本质上也是一种字典树,只不过,后缀树中存的是主串的所有后缀。例如字符串abcde的后缀树可以理解成是以其5个后缀(abcde,bcde,cde,de,e)构建的字典树。当然了,实际的后缀树为了节省空间,还做了一些压缩。构建后缀树的算法比较复杂,这里不作介绍,可以参考博文的Ukkonen后缀树算法的解析

有了后缀树后,任何单词的查询只需要O(M)的时间复杂度(M是单词长度)。而构造后缀树的时空开销都是线性的。所以,使用后缀树,可以将复杂度从O(N·k·p)降到O(N·k+M·p)。

最长公共子串

最长公共子串(LCS)指的是两个字符串A、B之间最长的公共子串(子串可能并不连续),是比较两个字符串相似性的常用算法。除此之外,还有编辑距离(ED)等字符串相似性匹配算法。这类问题往往可以通过2维状态空间的状态规划算法求解。有一个有意思的问题是,LCS问题等价于MES(Minimal Edit Script)问题,ES不用于ED的地方在于,ES只允许使用insert和delete操作,且这两个操作的权重相同。令字符串A和B的长度都为N,则其MES=2(N-LCS),简单来说,就是最短编辑脚本对应于最长公共子串。证明可以利用反证法,因为一种编辑脚本就唯一对应一种公共子串,一个公共子串就唯一对应于一种编辑脚本(把非公共子串部分进行insert,delete),所以如果MES<2(n-lcs),则通过该mes推出的公共子串一定比lcs更长;反之,如果mes>2(N-LCS),则通过LCS推导出的编辑脚本一定比MES更小。

git diff背后的算法

我们都知道,LCS的动态规划算法的时空复杂度是O(N^2)(N为单个字符串长度),对于大文件来说,这个复杂度还是太大了,还能更低么。如果你用过git diff这个命令,你会发现这个命令的效率是很高的,而且结果很“人性化”。这个命令背后用的是简单的动态规划么?其实是的,但是状态空间不是简简单单的N·N,而是N·D,其中D是最短编辑脚本,也就是最少需要用多少次insert,delete操作将字符串A变换成字符串B。

这个算法的论文可以见An O(ND) Difference Algorithm and Its Variations,大概的想法是:在一般比较字符串的公共子串的场合,两个字符串大部分都是相似的(LCS高,MES低),例如版本管理系统的diff命令等。这就意味着,最简单的动态规划算法的N·N的状态空间中有很多状态是白算的。见下图

ND algrithm

字符串大部分都相似,换成LCS的匹配路径上,意味着大部分都是“斜线”,少部分是“横竖线”。(因为横竖线代表insert和delete操作),也就是说,左下角和右上角这些状态根本用不上,这就是这个算法的出发点。具体N·D状态空间是如何构造的看下图

ND algrithm

我们试着在头脑中把上图中方形空间以中心为原点,顺时针旋转45度(看起来是个菱形)。这个菱形的二维空间,竖着是循环的第一层:遍历最短的横竖移动次数D;横着是循环的第二层:遍历在D次数下,最“远”能走到哪里。这只是粗略和直白的描述,具体的解释,还要看论文。

git diff –patience背后的算法

git的文件比较命令还有另外一个参数git diff --patience,该命令背后用的是patience diff算法,这种算法的结果更人性化。算法的大体思想是,要把两个序列“对齐”,可能有很多种方式,有时候并不是ES最小的对齐方式是最佳的,比如代码中可能有大量的行是大括号、换行等,把这些意义不大的行对齐其实并不重要,重要的是把两个序列(比如两段代码)的关键部分对齐,所以这个算法先取出每个序列unique的元素,首先求把这些元素的LCS,然后删掉两个序列中的相同的块,原来不unique的可能现在unique了,再进行这个过程,直到迭代完成。具体可见Patience Diff, a brief summaryPatience Diff Advantages