linux - grep内部工作原理

Question

我想知道 grep 内部是如何工作的。具体来说，我想知道找到第一个匹配项是否比找到所有匹配项快得多？例如，第一个匹配项出现在文件从开始处开始的 10% 点，所有匹配项都分布在整个文件中。然后我认为只找到第一个匹配将使 grep 处理的文件内容比查找所有匹配少得多(在这种情况下 grep 必须遍历整个文件，相比之下 10%文件在较早的情况下)。我想知道我的假设是否正确，因为这种可能的改进可以极大地改进我的处理工作。谢谢。

Answer 1

如果您使用 grep 打印文件中所有匹配的行，那么它当然必须处理整个文件。

另一方面，如果您使用 grep -q 在至少找到一个匹配项的情况下生成成功终止状态，那么 grep 当然可以在第一场比赛。如果在文件的早期找到第一个匹配项，则可以节省时间，因为 grep 可以在该点立即退出并返回成功终止状态。如果文件中没有匹配项(最坏的情况)，则它必须处理整个文件。在这种情况下它必须处理整个文件，因为它怎么能确定没有匹配项呢？如果匹配只出现在最后一行，但 grep 忽略了那一行，那么它会错误地报告没有匹配。

Grep 将模式编译为正则表达式。正则表达式的结构对性能有影响。一些正则表达式比其他的表现更好。根据所使用的算法，一些看起来很小的正则表达式可以生成具有大量状态的状态机。

索引是一种加快搜索速度的技术。如果您经常在文本语料库中查找特定单词，那么如果您有一个单词索引可以更快地指示它们在语料库中的位置。索引的组织方式使得可以非常快速地检索找到单词的位置列表，而无需扫描文本。建立索引需要时间(需要对整个正文进行全文扫描)，而且当语料发生变化时，还得重新建立索引。

这是加速计算机程序源代码标识符搜索的工具的基础，例如 GNU Id-Utils。当然，索引是 Google 等万维网搜索引擎的基础。