grep简介
在Linux里面，如果按照使用频率给命令排个序，那么grep绝对榜上有名。
grep的全称是Global Expression Print，用于正则表达式匹配文本，并把匹配到的行打印出来。
命令的基本形式是：
grep [option] pattern file
此处的file并不一定是特指某个文件，准确来说是指，任何的输入流。所以时常grep会合别的命令结合在一起来使用，例如查找Java进程:
ps -ef | grep java
在我机器上的输出是：
501 25223 16384 0 7:05下午 ttys002 0:00.00 grep --color=auto --exclude-dir=.bzr --exclude-dir=CVS --exclude-dir=.git --exclude-dir=.hg --exclude-dir=.svn java
grep作为一个基本工具，其性能是极高的:
image
现在我们就要思考一下，为什么grep会那么快呢？
grep那么快，就两个原因：
- 快的算法
- 快的输入。
我们先讨论快的算法。
字符串检索
我们先来了解一下字符串搜索，即如何在一个字符串中找到我们所需要的字符串，或者说子串。这些字符串一般都是符合某个规则，通常而言是使用正则表达式来进行描述。
在字符串检索里面，鼎鼎有名的就是Boyer-Moore字符串检索算法了额。这个算法阮一峰有过很精彩很简洁的介绍，地址是:
http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html
也可以阅读Moor教授对算法的介绍：
http://www.cs.utexas.edu/~moore/best-ideas/string-searching/fstrpos-example.html
我这里总结一下阮一峰文章的精髓：
这个算法的核心是“坏字符规则”和“好后缀规则”。
坏字符规则
坏字符是指，无法匹配上模式的字符，例如：
image
S和E无法匹配上，也就是一个坏字符。
而所谓坏字符规则就是：
后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置
所以下一次的匹配应该变成了：
image
；
在上图的情况下，可以进一步将字符串后移，将P对齐：
image
好后缀规则
image
这种所有尾部都匹配的字符串就叫做好后缀。当好后缀遇到第一个不匹配的字符的时候，在上图中也就是I和A，那么移动位数是:
后移位数 = 好后缀的位置 - 搜索词中的上一次出现位置
这就是Boyer-Moor算法的核心。
我们可以简单分析一下Boyer-Moor算法的效率。它是O(n)的，但是很多情况下，它并不需要遍历文本里面的每一个字符。
实现技巧
主要是使用了两个技巧：
- 循环展开。GNU grep将Boyer-Moor算法的内层循环展开了；
- 建立了一个jump table，也叫做delta table。通过该表可以避免进行循环退出判断了；
快的输入
grep在这方面所进行的优化，即使用系统调用，以避免数据拷贝的开销。
这是一种常见的优化手段，比如在Java NIO里面也使用到了类似的技术手段以避免数据从内核态拷贝到用户态，再由用户态拷贝到内核态
第二个优化是避免了对输入进行分行。grep直接将文本放在Buffer之中进行处理，在找到了匹配的字符串之后，再去查找里面有没有换行符。因为查找换行符是一个可怕的操作，这意味着需要逐个字符查找。
后记
原文是https://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html#
邮件里面还提到一个东西，即Fast String Search，这是一个关于Boyer-Moor算法实现优化的论文。我表示这篇论文没怎么读懂，我就不误人子弟了。
下载链接是:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.13.9460&rep=rep1&type=pdf
可以翻墙的同志可以看这个视频，对Boyer-Moor算法的讲解还是很好的：
https://www.youtube.com/watch?v=4Xyhb72LCX4
网友评论