11｜字符串匹配：如何实现最快的grep工具

Jan 4, 2022

11｜字符串匹配：如何实现最快的grep工具-业务开发算法50讲-极客时间



下载APP





关闭

渠道合作

推荐作者

11｜字符串匹配：如何实现最快的grep工具

黄清昊 · 业务开发算法50讲

课程介绍



讲述：黄清昊

时长17:55大小16.36M



你好，我是微扰君。
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”才能发现匹配失败；这就导致我们总共需要匹配 mn 次，其时间复杂度就是 O(mn)。
那有没有办法优化它呢？我们再来认真观察一下 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 算法出现的地方分享给你，代码中运用了许多不同的技巧，可读性其实并不是很好，作为今天的课后作业，留给你课后研究。
如果你在阅读代码的时候有什么问题欢迎留言和我一起讨论。如果你觉得有收获，也欢迎分享给身边的朋友一起学习，我们下节课见～

Boyer-Moore算法是一种高效的字符串匹配算法，通过预处理模式串，利用“坏字符”和“好后缀”规则来加速匹配过程。该算法避免了不必要的比较，实现了极致的文本搜索功能。文章详细介绍了BM算法的实现原理和匹配过程，以及其在实际应用中的性能优势。此外，还介绍了Brute-Force算法、KMP算法和Rabin-Karp算法等不同的字符串匹配算法，以及它们的优缺点。总的来说，本文对于想要了解字符串匹配技术特点的读者具有很高的参考价值。BM算法的特点在于利用预处理和空间换时间的思想，避免了不必要的比较，实现了高效的字符串匹配。文章还提到了BM算法的时间复杂度和理论性能，以及对读者的课后作业建议。通过学习BM算法，读者可以深入理解算法和计算机底层原理，提高程序性能。

分享给需要的人，Ta购买本课程，你将得18元

生成海报并分享

2022-01-04

赞 4

提建议

10｜搜索算法：一起来写一个简单的爬虫？

12｜拓扑排序：Webpack是如何确定构建顺序的？

 写留言

全部留言(5)

最新
精选

Paul Shan
2022-01-04
BM算法和KMP算法是类似的，都是采用了预处理来加快查询，区别是KMP扫描和匹配方向是相同的，都是从左到右，BM扫描从左到右，匹配从右到左，在字符串差异比较大的情况，可以跳过更多，这也是坏字符算法的作用，但是仅仅凭着坏字符算法处理两个字符串比较接近的情况，复杂度就会退化为O(m*n),这个时候引入KMP类似的子串跳转算法，避免了最差的情况，可以取得O(m+n)。坏字符类似于粗调，只用到了当前不匹配的字符，好后缀类似于精调，用到了不包括当前字符所有已经匹配的字符串。BM和KMP算法和红黑树算法一样，属于我一看就忘的类型,:）。
展开
作者回复: 哈哈哈确实是看了就忘不过也不太有手写的机会，了解原理我觉得也差不多啦
7
Jump
2022-04-01
str = AMPLEMABCABCMABC，pattern = ABCABCMABC，示例代码有点问题。
作者回复: 示例代码确实有问题可以提个issue给我哈我上次没来得及修复
共 2 条评论
王建新
2022-01-25
leetcode好像有类似很多的字符串匹配题目思路就是这样的
作者回复: 一般面试的时候不会要求KMP这样难度的代码能写暴力对比的就行～
Daneil
2022-01-06
不好意思，刚才看错了
作者回复: 哈哈哈没事多多交流噻～
Daneil
2022-01-06
好后缀计算的代码中，14-17行后缀的遍历有误。应当让后缀从小到大去进行遍历，而不是让后缀从大到小，一旦有一个大的后缀在gs表中，那么他的所有子后缀都不需要遍历，一定在gs表中。

