时间像一只被压扁的圆环。1973 年第一版 grep 发布时，它只是一个在文件系统中文本文件上匹配正则表达式的简单工具。多年来，随着开发者工具愈发先进，它逐渐被更专业的工具取代。先是像 ctags 这样大致基于语法的索引。后来，许多开发者转向针对特定编程语言的专业 IDE，通过解析并构建语法索引 (通常还会补充类型级信息) ，来非常高效地在代码库中导航。最终，这在 Language Server Protocol (LSP) 中被标准化，把这些索引带到了所有文本编辑器里，无论新旧。就在 LSP 成为标准之际，Agentic 编码出现了，然后你会发现：Agents 简直 太爱 用 grep 了。

还有其他最先进的技术可以为 Agents 收集上下文。我们之前写过，在很多任务中，你可以通过使用语义索引大幅提升 Agent 的表现，但也有一些特定查询，模型只能通过正则表达式搜索来解决。这意味着我们得回到 1973 年的那一套，尽管这个领域后来已经进步了不少。

大多数 Agent 框架 (包括我们的) 在提供搜索工具时，默认使用 ripgrep。它是 Andrew Gallant 开发的一个独立可执行程序，是经典 grep 的替代品，但有更合理的默认行为 (例如在忽略文件方面) ，而且性能好得多。ripgrep 以速度快而闻名，因为 Andrew 在如何让正则匹配更快这件事上投入了非常多的思考。

不管 ripgrep 在单个文件内容上匹配得多快，它都有一个严重限制：它必须在_所有_文件内容上进行匹配。这在小项目里还可以接受，但许多 Cursor 的用户，尤其是大型企业客户，都是在非常庞大的 monorepo 上工作——大到令人头疼。我们经常看到一次 rg 搜索要跑超过 15 秒，这会严重拖慢任何需要主动与 Agent 交互、边指导边写代码的人的工作流。

正则表达式匹配如今已是 Agentic 开发中至关重要的一环，我们认为必须明确针对这一点：就像传统 IDE 会在本地创建语法索引来支持“转到定义” (Go To Definition) 这类操作一样，我们正在为现代 Agents 在查找文本时执行的核心操作构建专门的索引。

#经典算法

为了加速正则表达式匹配而对文本数据建立索引，这个想法早已有之。它最早由 Zobel、Moffat 和 Sacks-Davis 在 1993 年的一篇论文 "Searching Large Lexicons for Partially Specified Terms using Compressed Inverted Files" 中系统提出。他们给出了一种使用 n-grams（宽度为 n 个字符的字符串片段）来创建倒排索引的方法，以及一种将正则表达式分解为 n-gram 树、从而在索引中进行查找的启发式策略。

如果你之前听说过这个概念，很可能并不是来自那篇论文，而是来自 Russ Cox 在 2012 年、Google Code Search 关闭后不久发表的 一篇博客文章。我们先快速回顾一下用于构建这类索引的基本“积木”，因为此后几乎所有其他索引方案都在不同程度上沿用了这些思路。

#倒排索引

倒排索引是搜索引擎背后的基础数据结构。给定一组需要建立索引的文档，你可以通过把每个文档拆分成一系列 token（词元）来构建倒排索引。这叫作分词（tokenization），而实现方式有很多种——在本例中，我们会使用最简单的方式：把每个单词视作一个 token。然后，这些 token 会变成类似字典结构中的键，而对应的值则是在每个 token 下，它出现过的所有文档列表。这个列表通常被称为 posting list（倒排列表），因为每个文档都会由一个数值或“posting”唯一标识。当你搜索一个或多个 token 时，我们会加载它们的 posting list；如果有不止一个 posting list，就对这些列表做交集，以找到那些在_所有列表中都出现_的文档。

这种设计（再在其之上附加大量复杂功能）是当今大多数搜索引擎的基础。但这些搜索引擎是为_自然语言_设计的，而我们想搜索的是正则表达式，而且是要在源代码上匹配正则表达式。这套方法就不太奏效了。

你可以尝试通过深入思考分词策略来构建一些有用的东西——了解每种编程语言的语法、拆分源代码中的标识符，等等。但要把这件事做好非常困难。早期 GitHub 的 Code Search 功能就是这么做的：使用对编程语言极其复杂的分词器，再配上一大规模的 Elasticsearch 集群。效果并不好，用户对这个功能的评价也很差。你可以搜索标识符（勉强算是），但没法匹配正则表达式。要做到这一点，你需要一种更好的分词方式。

#三元组分解

对源代码进行朴素的分词对匹配正则表达式作用不大。我们需要把文档拆分成更基础的片段。经典算法会选择三元组（trigram）：一个 token 是输入字符串中每一个重叠的 3 个字符的片段。

为什么是 3？我们会把这些三元组作为倒排索引中的键。如果我们选择二元组（长度为 2 的片段），索引中的键就会很少，最多大约 64k，但每个键上的 posting list 会非常巨大——大到无法高效处理。如果我们选择四元组（长度为 4 的片段），posting list 会非常小，这本身是件好事，但我们会在倒排索引中拥有数十亿个键，也同样难以处理。

因此，三元组是一个不错的折中选择。这样在对文档做索引时的分词就非常简单：从被索引文档中提取所有重叠的长度为 3 的字符序列，并将它们作为倒排索引中的 token。

真正的复杂性出现在对正则表达式进行分词以便能与索引匹配时。正则表达式有_语法_，所以你需要对它们进行解析，并使用启发式方法来判断哪些三元组可以从实际代表文本的表达式片段中提取出来。

将一个 字面量字符串 分解为三元组是很直接的，因为这和你对文档建立索引时使用的算法相同。提取字符串中所有重叠的三元组；包含_所有_这些三元组的文档大概率会包含这个字面量（但不一定！）。交替（Alternations） 会被分别分解，得到两个分支，只要文档中包含_其中任意一个_分支就可以匹配。我们在倒排索引上通过_合并_ posting list，而不是对它们做交集来实现这一点。字符类可以被分解成许多三元组。像 [rbc]at 这样的小字符类，会为类中的每个元素生成一个三元组。使用 更宽泛的字符类 时，我们会直接在这些边界上跳过三元组的提取。

#综合起来看看

我们已经知道三元组是对这些文档进行分词的正确方式，也知道在构建索引时如何对文档进行分词，以及在搜索时如何对查询进行分词。现在我们可以把这一切整合成一个真正的搜索索引，用来 非常高效地 匹配正则表达式。通过把任意正则表达式分解成一组三元组，然后从倒排索引中加载所有相关的倒排列表，我们最终会得到一个文档列表，这些文档 有可能 匹配我们的正则表达式。这一点很重要！最终的结果集仍然需要通过实际加载所有这些候选文档，并用“传统方式”再跑一遍正则匹配才能得到。但有了这个子集，总是比必须逐个文件扫描并匹配整个代码库要快得多。

就设计而言，这个方案是完全可用的。像 google/codesearch 和 sourcegraph/zoekt 这样的项目，就使用三元组倒排索引在大型索引上提供了不错的性能（而且和所有搜索引擎一样，它们在此之上又叠加了大量复杂功能）。但这里也有明显的不足：索引体积并 不 小，而且在查询时的分解必须做权衡。如果你使用简单的启发式方法，你会把查询分解成很少的几个三元组，这会导致需要匹配的候选文档很多。如果你使用复杂的启发式方法，你可能会得到几十个——甚至上百个——三元组，而从倒排索引中加载所有这些三元组对应的倒排列表的开销，可能会慢到还不如直接从头扫描所有内容。

我们可以做得更好。

#后缀数组：一次小小的番外

既然我们在讲解用于正则表达式搜索的文本数据索引历史，我想稍微岔开一下话题，讨论 Nelson Elhage 在 2015 年为他的 livegrep 网络服务开发的这个实现。与其他大型业界项目相比，livegrep 规模很小——它只为最新版本的 Linux Kernel 建索引——但也正因为范围更小，它的实现方式几乎与业界所有其它方案都截然不同，也因此格外有意思，值得单独拿出来聊一聊。

Nelson 从第一性原理来解决这个问题：这个搜索引擎并没有使用倒排索引。相反，所有源代码都被索引在一个后缀数组里。

这里的不足之处是什么？后缀数组必须基于一个输入字符串来构造，这是一个很大的限制。如果你要为一个大型代码库（或许是很多不同的代码库）建立索引，首先需要把所有内容拼接成一个单一字符串，然后再据此构建后缀数组。在后缀数组中找到匹配之后，还需要一个辅助数据结构来把匹配位置映射回包含它的原始文件。这种复杂度并非完全不可接受，但会让动态更新索引的成本非常高。这种方案非常难以扩展。

#带概率掩码的三元组查询

回到一些更传统的设计：这里介绍一种最初在 GitHub 为 Project Blackbird 开发的方法。这个研究项目的目标是替换旧的 Code Search 功能。正如我们之前讨论的，旧搜索通过对源代码进行分词实现，无法匹配正则表达式。而这次新实现的目标，就是设计出一种可以支持正则匹配的方案。

最初的几版尝试使用以三元组为键的经典倒排索引，但很快就遇到了容量问题。GitHub 里有非常多的代码，用三元组为其建立索引会产生过于庞大的 posting list，根本没法高效搜索。

既然三元组效果并不理想，下一步就是寻找一个更合适的 n-gram 大小来建索引。我们已经看到，二元组太宽泛，因为它们的 posting list 大到无法管理；而四元组又太具体，因为这会让我们的索引中出现过多的键。三元组在这两者之间是_一个_不错的折中点，但在实践中，理想的大小更像是……3.5-gram。不过我们总不能把一个字符劈成两半，对吧？

实际上，我们可以做一件非常接近这点的事情：这个设计建议仍然使用三元组作为倒排索引的键，但在 posting list 中增加额外信息，用来表示在该文档中紧跟在这个三元组之后的那个“第四个字符”。为此，我们可以简单地将第四个字符按一个额外字节存储起来，但那样就把索引变成了四元组索引，而我们已经知道那样会太大，难以存储。我们实际存储的是一个 布隆过滤器（Bloom filter），其中包含所有跟随该三元组的字符。

生成的索引事实上极其高效，但 也有一个主要缺点。布隆过滤器可能会被“灌满”。 这是布隆过滤器一个不太妙的性质：它可以被更新，但如果往里加的数据太多，最终 filter 中的所有比特都会被置位。一旦布隆过滤器饱和， 它就会匹配所有内容，我们又回到了最开始提到的那个 索引的性能水平。

这是一个在存储上极度节省的索引，但当你需要就地更新它时，就会变得非常麻烦。

#稀疏 N-grams：更聪明的 trigram 选择

这里还有一个非常聪明的想法。你可能在 ClickHouse 的正则表达式运算符中见过它的用法，也可能在 GitHub 几年前上线的 Code Search 新功能中见过，它支持匹配正则表达式。这种技术叫做 Sparse N-grams，是各种方案之间一个非常理想的折中。

传统的 trigram 索引会提取_每一个_连续的 3 字符序列，但你可以看到，这会产生_大量冗余_。每个 trigram 中的字符都会在相邻的 trigram 中被重复！在这个算法里，我们会提取一定数量的随机 n-gram，并且每个 n-gram 的长度也是随机的。

当然，这里的_随机_不能是真正意义上的随机，否则索引就无法被查询。我们会为文档中的每一对字符分配一个“权重”。这个权重可以是任何值，只要它是确定性的即可（ClickHouse 使用的是这两个字符的 crc32 哈希）。然后，我们的稀疏 n-gram 就是所有这样一些子串：其两端的权重大于其内部包含的所有权重，并且是严格大于。

关键在于，这意味着稀疏 n-gram 可以有_任意长度_。它们并不统一。这也意味着我们可能会生成很多稀疏 n-gram——比单纯提取 trigram 还要多。但因为 n-gram 是以确定性的方式生成的，我们在查询时就可以做一些非常重要的优化。我们来看看怎么做。

我们还能做得更好吗？当然可以！而且能好很多。前面的示例算法里，我们一直用的是 crc32 作为权重函数。不过，只要是确定性的哈希函数，其实都可以用在这里。现在我们来选一种更聪明的方式：让这个哈希函数对那些实际上 非常罕见 的字符对赋予高权重，对那些 非常频繁 的字符对赋予低权重。

这个哈希函数计算起来很简单。因为我们要为源代码建立索引，可以从互联网抓取几 TB 的开源代码，并为其中出现的所有字符对构建一个频率表。这个频率表就是我们的哈希函数。看看在我们把它应用到算法上时会发生什么：权重最高的项现在落在最不常见的字符对上，因此，covering 模式 会让需要查找的 n-gram 进一步减少，可能匹配的文档数量也随之减少。

这种尽量减少倒排列表查找次数的方法，是在用户本地机器上构建可高效查询索引的理想起点。

#所有这一切，都在你的本地机器上完成

用于加速正则表达式搜索的索引必须存放在_某个地方_。到目前为止我们看到的所有设计都部署在服务器端，而前面提到的语义索引同样是在服务器上进行管理和查询。不过这一次，我们选择走一条不同的路线：在用户自己的机器上构建和查询索引。

将这些索引保存在本地有多方面的好处。首先，索引只是完成正则表达式匹配所需的_一_个部分。它们只是帮你把可能匹配正则表达式的文档范围缩小到一个子集，但你仍然需要逐个扫描每个文件。如果在服务器上做这件事，就意味着要么同步所有文件，要么在客户端和服务器之间进行代价高昂的多次往返请求。而在客户端上完成这件事就非常简单，同时还能绕开大量与数据存储相关的安全和隐私问题。

延迟对这类功能也至关重要。我们的 Composer 模型拥有行业内最快的每秒 token 数 (TPS) 之一，我们也在持续努力让它既更智能_又_更快速。如果再为这样一个模型_持续_ (并且经常是并行地) 使用的关键操作增加网络往返，只会增加摩擦、带来停顿，并且把我们从与 Agent 交互时所追求的目标推向反方向。

与语义索引不同，用于正则表达式搜索的索引还必须保持_非常新鲜_，尤其是在模型需要读取自己刚写入内容的场景下。我们不需要持续更新语义索引，是因为在文件修改后重新计算该文件的 embedding，并不会让新的 embedding 在多维空间中发生显著位移。我们执行的最近邻搜索仍然会把 Agent 引导到正确的方向。然而，如果 Agent 在搜索某段具体文本时没有找到，它往往就会开始到处乱找，浪费 token，最终完全违背我们最初的性能优化目标。

把这些索引带到客户端也带来了一系列新的挑战。同步磁盘数据可能既复杂又昂贵，但在实践中我们让这件事变得非常高效：我们基于底层 Git 仓库中的某个提交来控制索引的状态。用户和 Agent 的变更则作为一个额外的层叠加在其之上。这样既能非常快速地更新索引，也能在启动时非常快速地加载和同步。

为了确保编辑器中的内存占用保持在最低水平，我们把索引存储在两个单独的文件中。第一个文件包含索引的所有 posting list，顺序存放——在构建的过程中我们会直接将其刷写到磁盘。另一个文件包含一张排好序的表，里面记录了所有 n-gram 的哈希值以及它们在 postings 文件中对应 posting list 的偏移量。在这里仅存储哈希而不存储完整的 n-gram 总是安全的：在极小概率发生哈希碰撞时，可能会让某个 posting list 的结果范围变得更宽泛，但不会产生错误结果。同时这也让查找表的布局非常紧凑。然后我们在编辑器进程中只对这张表执行 mmap，并用二分查找来处理查询。搜索返回一个偏移量，我们再直接根据这个偏移量去读取 postings 文件中的数据。

#结论

我们发现，为像我们的 Composer 2 这样的高速模型提供文本搜索索引，会为 Agentic 工作流带来质的变化。在更大的企业级代码仓库中，这种影响尤为明显，因为 grep 是少数几个其延迟会随着所处理代码的规模和复杂度而增长的 Agent 操作之一。可以看看这些使用 Composer 2 运行的示例工作流：完全消除在代码库中搜索所花费的时间，可以带来可观的时间节省——尤其是在 Agent 调查 bug 时——并让迭代更加高效。

至于接下来是什么，谁也说不准呢！在为 Agents 提供上下文方面，有许多令人兴奋的进展，且有大量研究人员——包括我们自己——在这个领域深耕。我们会继续优化当前方法的性能，包括 语义索引，并希望推出全新的方法，进一步提升 Agents 的表现，同时始终确保它们能在真正关键的场景中真正可用：那些全球最大规模的代码仓库中——那才是 Agentic 开发未来真正开始加速发展的地方。