20 KiB
11｜字符串匹配：如何实现最快的grep工具
你好，我是微扰君。
grep命令，相信使用过Linux的同学都会非常熟悉，我们常常用它在Linux上进行文本搜索操作，具体来说就是从一段文本中查找某个字符串存在的行。下面一个典型的grep的使用例子，比如我可以用它来看看自己在LeetCode上用Java做了多少题：
GNU Grep 则是 grep 命令的一个工业级实现，在项目官方 Readme 中作者是这样介绍它的：
This is GNU grep, the “fastest grep in the west” (we hope).
其实就是在说这是世界上最快的grep程序。当然，这款从上世纪就诞生的软件，敢这么说自己也是因为它有着十足的底气。
GNU Grep 确实是将“文本搜索”这一简单的功能做到了极致。作者 Mike Haertel 自己写了一封邮件解释 GNU Grep 为什么这么快，主要有两点：
- 它避免了检查每一个byte
- 对于被检查的byte，只需要执行非常少的指令
第一点的主要优化就在于 GNU Grep 用到了非常知名的字符串匹配算法：Boyer Moore 算法，也就是我们常说的 BM 算法，它是目前已知的在大多数工业级应用场景中最快的字符串匹配算法，因而被广泛应用在各种需要搜索关键词的软件中，许多文档编辑器快捷键 ctrl+f 对应的搜索功能都是基于这个算法实现的。
那第二点呢，就是当你发现查询的速度已经优化到足够好时，也需要让IO的速度更快一些，查询所需的指令也更少一些，这里可以优化的地方就更多了。
比如由于 grep 是按行查找的，许多版本的 grep 实现都会去遍历查找\n 换行符先进行分行，但 GNU Grep 则是将搜索文本直接读入一个缓冲区优先查找目标字符串，只有命中时才会在命中位置的前后进行换行符的查找；又比如，GNU Grep提供了基于mmap映射内存到文件的参数，可以减少一些内存拷贝的时间开销。具体的细节还有很多，比较繁琐，有兴趣的同学可以自行查阅 Mike Haertel 的邮件。
这个例子也再次说明了一件事情，要写出真正高性能的程序，不只要懂算法，也要懂计算机底层原理；只有这样，才能真正了解程序在运行时可能存在的各种性能瓶颈，找到不同场景下的最优解。
好我们回到今天的主题，字符串匹配。这也是一个经典问题了，相关算法非常多种，比如最暴力的 Brute-Force 算法、将前缀信息运用到极致理论性能极佳的KMP算法，还有利用哈希思想和滑动窗口思想的Rabin-Karp算法等等。
那为什么BM算法的性能在工程实战中最好呢？
别急，老规矩，我们还是先来严谨地定义一下字符串匹配问题，方便展开后面的讨论。
字符串匹配问题
假设给定长度为n的主串 s[0…n-1] 和长度为m的模式串 p[0…m-1]，一般n远大于m，请实现一个函数 match(string s, string p) 用于找出所有的p在s中出现的位置。
那如何解决这个问题呢？
容易理解、复杂度也相对差的方法就是，遍历主串的每一个位置，看当前位置是否能和模式串匹配上；能否匹配的判断方式也很简单，从主串的当前位置开始，逐一对比主串对应字符是否和模式串相等。如果可以匹配，说明找到了一个匹配的位点，记录下来；如果不可以匹配，我们就继续尝试下一个位置，直到整个主串遍历完全。这也是最暴力的Brute-Force算法的思路。
写成代码如下：
/*
* s: 主串
* p：模式串
*/
std::vector<intstring> match(string s, string p) {
std::vector<int> ans;
int n = s.size();
int m = p.size();
int i, j;
for (i = 0; i < n - m + 1; i++) {
for (j = 0; j < m; j++) {
if (s[i + j] != p[j]) break;
}
if (j == m) ans.push_back(i);
}
return ans;
}
代码非常清晰易懂，相信你看懂没什么压力。
通常在字符串不长的时候，不同的匹配算法之间的效率差异不大。Brute-Force算法的实现和理解都非常简单，不容易出错，完美地符合了KISS（Keep it simple, stupid）原则，也就是让代码尽量简单从而避免出错。所以BF算法在真实开发的环境中出镜率很高，在日常工作中如果有手写字符串匹配的需求，你也可以考虑这种方式。
但这个算法在最坏的情况下时间复杂度确实不是很理想。
比如s = AAAAAAAA、p = AAAB时，在每个位置匹配p最终都会失败，但是都需要匹配到p的最后一个字母“B”才能发现匹配失败；这就导致我们总共需要匹配 m_n 次，其时间复杂度就是 O(m_n)。
那有没有办法优化它呢？我们再来认真观察一下BF算法，首先会从主串和模式串的头开始遍历匹配，看第一次匹配的情况，BF算法之所以慢，就在于匹配p[3]失败后，我们又从模式串的第一个字符p[0]和主串的下一个位置s[1]开始比较，而s[1]这个位置其实在之前的搜索过程中出现过了。
所以，我们有没有办法通过一些预处理的手段，利用p[0…2]和当前正在匹配的主串中s[0…2]相等的已知信息，跳过一些肯定不可能的匹配，从失配处s[3]继续匹配呢？ KMP和BM算法其实都是这样做的，只不过手段有些差别。
KMP算法将前缀的信息利用到了极致，用匹配串自身的信息建立了一张部分匹配表，在每次失配的时候可以用来加速模式串，而不是每次都只向后移动一位。其算法逻辑整体比较复杂，感兴趣的同学可以网上搜索一下相关资料自行学习。
而GNU Grep 中用到的BM（Boyer Moore）算法，不仅理解起来容易很多，实际应用时性能也更好，它同样是基于预处理来避免不必要的重复匹配。但BM算法引入了两条很好懂的规则，“坏字符”和“好后缀”规则，并采用从后往前的匹配顺序进行匹配，构思非常巧妙。
后面的内容我们就用 moore 教授本人提供的例子来讲解。
其中模式串p是EXAMPLE，主串s是 HERE IS A SIMPLE EXAMPLE。
坏字符规则
先来看第一条规则：“坏字符”规则，描述的是主串上的失配字符，目的就是为了跳过一些肯定不可能成立的匹配位置。
在BM算法中，我们同样将s和p对齐，开始遍历匹配，但匹配的顺序和BF算法不同，采用从后往前匹配的方式。这其实是一种非常巧妙的设计，你马上可以看到它配合坏字符规则使用时有着绝佳的效果。
所以在例子中，第一次尝试匹配，首先会把p[6]的“E”和s[6]的“S”匹配，发现它们不匹配，所以这里的“S”就是一个坏字符。
那此时我们有两种选择，一种就是直接将模式串往后移动一位尝试继续匹配，这就和之前BF算法的想法差不多，没有利用到模式串中任何先验的信息。
而另一种呢，就是BM的做法了。
我们先看失配的坏字符“S”在模式串p中是否有出现，如果没有出现，那说明模式串其实不可能和这个位置有重叠，可以直接跳过这段位置，从主串的下一个位置开始匹配。在例子中，“S”显然不属于模式串EXAMPLE，我们就应该跳过“S”继续匹配，这样就大大加速了匹配的过程。
同样在下一步匹配时，因为主串的“P”和模式串的末尾“E”不匹配，但失配的“P”在模式串中就有出现，我们可以将模式串中最后一次出现的“P”和主串中的“P”对齐，同样从模式串尾开始匹配。
至此，坏字符的主要内涵就全部展示出来了，也就是，每次失配的时候，我们需要将匹配串往后移动 （失配位置下标 - 失配字符最右出现的位置下标） 位；如果失配字符不存在，则位置为-1。
这里你可能会有个疑问，为什么是最右的位置呢，不应该是记录上一次出现的位置吗？我的理解是，如果在每个位置都存储相比于当前位置的上一次失配字符出现的位置，存储开销会大得多；而如果只存每个字符最右出现的位置，我们所需要的只是一个字符集大小的哈希表，用一个长度为256的数组即可实现。
当然，这个公式会导致我们有时候求出的移动值可能是负的，让模式串反而向前移动了。比如在 BBBBBB 和 ABB 匹配时，第一次失配的坏字符B，会让匹配串往后移动（0-2=）-2位，导致前移。
那往前移显然是没有意义的，因为当前位置之前的匹配可能我们已经全部排除了；所以当移动位数出现负数时，我们也要让模式串至少往后移动一位，这点通过对基于坏字符的移动值和1取max操作即可实现。
而在这种时候，我们另一条规则“好后缀”也就可以发挥作用了。
好后缀规则
我们继续来看刚刚的例子。
在SIMPLE和EXAMPLE的匹配中，我们发现“MPLE”都匹配得上，但主串中的“I”和模式串中的“A”出现了失配。那这里的“MPLE”，我们就会称之为好后缀；同样“PLE”、“LE”、“E”其实也都是好后缀。
此时如果应用之前的坏字符规则，我们应该将模式串往后移动（2-(-1)=）3位，因为“I”在模式串中不存在。
但是，有没有办法利用已经匹配上的好后缀“MPLE”的信息，往后移动更多位呢？
当然是可以的，我们只要看匹配上的好后缀“MPLE”及它的子串“PLE”、“LE”、“E”是否之前也出现在模式串中即可。这里只有子串“E”之前也出现在了模式串中，所以我们可以直接把模式串移动至和这里主串的“E”对齐即可，这样我们向后移动了6位，显然比坏字符规则跳过了更多不可能的情况。
总结起来，好后缀规则移动的方式就是，**找到好后缀在模式串中最右的匹配位置，总计向后移动（模式串字符长度 - 1 - 好后缀在模式串上次出现的最右位置）位。**以EXAMPLE为例，好后缀“E”在模式串中上一次出现的下标是0，整个字符串长度为7，所以向后移动（7-1-0）6个位置。
这里还需要注意一点，好后缀匹配的时候，只有最长的好后缀被允许出现在模式串的中间位置；其余子串只能匹配在模式串的前缀中。比如下面的例子，主串中的“A”和模式串中的“C”失配，“MABC”是最长好后缀，但之前并没有出现在模式串中。
- 我们不能直接将模式串直接移到“MABC”之后，因为这样会错过好后缀子串“ABC”的匹配点。
- 但同样我们也不用匹配红色虚线框中的“ABC”，因为“MABC”没有匹配上，后面所有的MABC的子后缀匹配肯定只能发生在模式串的前缀中。
好后缀和坏字符规则其实都是可以单独使用的；BM算法，为了尽可能多地跳过不可能匹配的字符，会选择两条规则中的较大移动值来往后移动。而且这两个规则和主串都没有关系，只和模式串自身有关，我们显然可以通过预处理得到两个规则的偏移表，来加速整个模式匹配的过程。
好了，现在讲完了BM算法“好后缀”、“坏字符”的两个规则和从后往前匹配的策略，我们一起来把例子匹配完成吧。
在查表发现好后缀的规则能跳过更多的位置后，我们选择将模式串往后移动了6位。这时“P”和 “E”没有匹配成功，我们采用坏字符规则，拿着坏字符“P”，找到模式串中出现的“P”位于p[4]，向后移动(6-4=) 2位和主串的“P”对齐。从尾部往前遍历匹配，此时，我们发现所有的字符都匹配上了，因而找到了一个完全匹配的位置。
具体实现
相信你现在已经大体理解整个BM算法的思路了，但正所谓，“细节是魔鬼”，BM算法从概念上理解其实并不是很难，但真要手写实现还是比较困难的，不熟练的时候debug很容易花费很多的时间。为了方便起见，我们就用Python来实现这个算法。
具体实现我们可以分为三个大块：“坏字符”最右位置计算、“好后缀”偏移表计算、在主串上的搜索实现。
坏字符最右位置计算
“坏字符”的部分是最简单的，只需要开一个dict，遍历一次模式串，找到每个字符出现在模式串中的最右侧的那个位置即可。事实上，我们可以用一个[0,256]的数组来替代HashMap以提高性能，大部分工业级实现也都是这样做的。
def get_bc(pattern):
bc = dict() # 记录每个badchar最右出现的位置
for i in range(len(pattern) - 1):
char = pattern[i]
bc[char] = i + 1
return bc
由于遍历的时候我们会不断地覆写dict，所以最后遍历完成，就能得到每个badchar在模式串中最右侧的位置。
好后缀偏移表计算
“好后缀”的部分相对来说比较复杂，尤其是工业级的实现对性能要求很高，代码有很多trick，非常不易于理解，这里我们做一些简化的处理；而且在大部分时候，由于模式串比主串要短的多，即使预处理时间复杂度稍微高一些，问题也不是很大。
def get_gs(pattern):
gs = dict()
gs[''] = len(pattern)
# suf_len 用于标记后缀长度
for suf_len in range(len(pattern)):
suffix = pattern[len(pattern) - suf_len - 1:]
# j 用于标记可用于匹配的位置
for j in range(len(pattern) - suf_len - 1):
substr = pattern[j:j + suf_len + 1]
if suffix == substr:
gs[suffix] = len(pattern) - j - suf_len - 1
for suf_len in range(len(pattern)):
suffix = pattern[len(pattern) - suf_len - 1:]
if suffix in gs: continue
gs[suffix] = gs[suffix[1:]]
gs[''] = 0
return gs
我们同样开一个dict，用于标记失配时每个字符串应该往后移动多少，也就是对应的好后缀应该和之前哪个子串或者前缀匹配。怎么做呢？
一种比较暴力的做法就是遍历所有可能的后缀，然后从前往后看这个后缀是否在模式串中的其他位置也出现了，后面遍历的会覆盖之前的记录，所以记录下来的就是最右的匹配位置。
记得前面说过如果一个后缀在模式串中不存在，我们不能直接跳过整个字符串，因为该后缀的子串还可能和模式串中的前缀重合。比如例子中的“MPLE”后缀虽然不再存在于“EXAMPLE”中，但是其子串“E”与“EXAMPLE”的前缀“E”是重叠的。
所以在后缀不存在的时候，还需要检查一下其子后缀是否在dict有对应的匹配，如果有的话，也应该采用；这个通过一次循环赋值即可实现，对应到代码里就是第14到17行。
我这里实现的时间复杂度为O(m^3)，你可以自己推导一下，也欢迎去留言区讨论。
匹配过程
有了好后缀的偏移表和坏字符的最右位置，我们就可以来实现整个匹配的过程了。
def bm(string, pattern, bc, gs):
# i 用于标记当前模式串和主串哪个位置左对齐。
i = 0
# j 用于标记当前模式串匹配到哪个位置；从右往左遍历匹配。
j = len(pattern)
while i < len(string) - len(pattern) and (j > 0):
# 从右往左匹配每个位置
a = string[i + j - 1]
b = pattern[j - 1]
if a == b: # 匹配的上，继续匹配前一位
j = j - 1
else: # 匹配不上，根据两个规则的预处理结果进行快速移动
i = i + max(gs.setdefault(pattern[j:], len(pattern)), j - bc.setdefault(a, 0))
j = len(pattern)
# 匹配成功返回匹配位置
if j == 0:
return i
# 匹配失败返回 None
return -1
if __name__ == '__main__':
string = 'here is a simple example '
pattern = 'example'
bc = get_bc(pattern) # 坏字符表
gs = get_gs(pattern) # 好后缀表
print(gs)
x = bm(string, pattern, bc, gs)
print(x)
参照详细的注释，整个过程和前面讲解的原理是一一对应的，你可以配合代码一起理解。 完整的代码我放到了GitHub上。
时间复杂度
Boyer-Moore 算法，在最好情况下复杂度可以达到 O(n/m)，在字符集比较大的时候，坏字符和好后缀规则可以帮助我们快速跳过大部分不必要的查询，达到接近最好的时间复杂度的概率是比较大。
但BM算法的最坏时间复杂度估计就是一个很难的数学问题了，许多学者都尝试做过相关的证明，目前我知道相对精细的比较上限次数的估计是Guibas和Odlyzko给出的3n，你感兴趣的话可以阅读原始论文了解。
因而和KMP一样，BM算法的理论时间复杂度也在O(m+n)之内，但由于字符集比较大的时候，BM常常能达到更好的时间复杂度，所以在实际应用中得到了更广泛的使用。
总结
我们来总结一下BM算法的特性。
BM算法，最大的特点就是利用了对目标串的预处理，用空间换时间，避免了许多不必要的比较，预处理的方式主要来自于对“坏字符”和“好后缀”两条规则的观察，因为这两个规则和主串都没有关系，只和模式串自身有关，显然可以通过预处理得到两个规则的偏移表，来加速整个模式匹配的过程。
总的来说，BM算法不难理解但实现起来有一定复杂度，感兴趣的同学可以自行练习。不过这一个特定的字符串匹配算法的学习其实还是次要的，空间换时间和预处理的思想你可以好好感受。
课后作业
相信通过今天的学习，你已经知道了如何基于Boyer-Moore算法实现一个高效的grep命令了吧。这里我也把grep源码中BM算法出现的地方分享给你，代码中运用了许多不同的技巧，可读性其实并不是很好，作为今天的课后作业，留给你课后研究。
如果你在阅读代码的时候有什么问题欢迎留言和我一起讨论。如果你觉得有收获，也欢迎分享给身边的朋友一起学习，我们下节课见～