原文标题：Fast regex search: indexing text for agent tools
原文链接：https://cursor.com/blog/fast-regex-search

快速正则搜索：为 Agent 工具构建文本索引

作者：Vicent Marti — 2026 年 3 月 23 日

时间是一个扁平的圆。当 grep 的第一个版本于 1973 年发布时，它只是一个在文件系统中对文本文件进行正则表达式匹配的基础工具。多年来，随着开发工具日趋先进，它逐渐被更专业的工具取代。先是大致基于语法的索引，如 ctags。后来，许多开发者转向了针对特定编程语言的专用 IDE，通过解析和构建语法索引（通常还辅以类型级别的信息）来高效地浏览代码库。最终，这些能力被标准化为 Language Server Protocol（LSP），将索引带到了所有文本编辑器中，无论新旧。然后，就在 LSP 正成为标准之际，Agentic 编程到来了——你猜怎么着：Agent 们就是喜欢用 grep。

还有其他先进的技术可以为 Agent 收集上下文。我们之前讨论过，在许多任务中使用语义索引可以大幅提升 Agent 的性能，但有些特定的查询只能通过正则表达式搜索来解决。这意味着我们要回到 1973 年——尽管这个领域自那以来已经有了不小的进步。

大多数 Agent harness（包括我们的）在提供搜索工具时默认使用 ripgrep。这是 Andrew Gallant 开发的独立可执行程序，提供了经典 grep 的替代方案，拥有更合理的默认设置（例如在忽略文件方面），以及更优越的性能。ripgrep 以其速度著称，因为 Andrew 在正则表达式匹配的速度优化上投入了大量心血。

无论 ripgrep 匹配文件内容有多快，它都有一个严重的局限性：它需要匹配所有文件的内容。这在小项目中没问题，但 Cursor 的许多用户——尤其是大型企业客户——在非常庞大的 monorepo 中工作。令人痛苦的庞大。我们经常看到 rg 调用耗时超过 15 秒，这确实会严重阻碍任何正在与 Agent 交互、引导其编写代码的人的工作流程。

匹配正则表达式现在已是 Agentic 开发的关键环节，我们认为必须明确地针对它进行优化：就像传统 IDE 在本地为 Go To Definition 等操作创建语法索引一样，我们正在为现代 Agent 查找文本时执行的核心操作创建索引。

经典算法

为加速正则表达式匹配而对文本数据建立索引的想法远非新鲜事。它最早由 Zobel、Moffat 和 Sacks-Davis 于 1993 年在一篇名为”Searching Large Lexicons for Partially Specified Terms using Compressed Inverted Files”的论文中发表。他们提出了一种使用 n-gram（宽度为 n 个字符的字符串片段）创建倒排索引的方法，以及将正则表达式分解为可在索引中查找的 n-gram 树的启发式方法。

如果你之前听说过这个概念，可能不是来自那篇论文，而是来自 Russ Cox 在 2012 年 Google Code Search 关闭后不久发布的一篇博客文章。让我们快速回顾一下这些索引的构建模块，因为它们适用于此后开发的几乎所有其他索引方法。

倒排索引

倒排索引是搜索引擎背后的基础数据结构。在一组待索引的文档上，你通过将每个文档拆分为 token 来构建倒排索引。这被称为分词（tokenization），有许多不同的方法——在这个示例中，我们使用最简单的方法：以单个词作为 token。然后 token 成为类字典数据结构的键，而值则是对每个 token 而言包含该 token 的所有文档的列表。这个列表通常被称为 posting list（倒排列表），因为每个文档都由一个数值或”posting”唯一标识。当你搜索一个或多个 token 时，我们加载它们的 posting list；如果有多个 posting list，我们对它们取交集以找到出现在所有列表中的文档。

这种设计（在其上附加了大量复杂性）是当今大多数搜索引擎的基础。但这些是针对自然语言的搜索引擎，而我们试图搜索正则表达式，并在源代码上进行匹配。这并不能直接适用。

你可以尝试在这里通过深入思考分词来构建有用的东西——了解每种编程语言的语法，拆解源代码中的标识符，等等。这非常难做对。在 GitHub 的早期，他们的 Code Search 功能就是这样实现的：使用一个非常复杂的编程语言分词器和一个非常庞大的 ElasticSearch 集群。效果并不好，人们对这个功能评价很差。你可以搜索标识符（算是可以），但不能匹配正则表达式。你需要更好的分词方式才能做到这一点。

Trigram 分解

对源代码进行朴素分词对于匹配正则表达式没有用处。我们需要将文档拆分成更基础的块。经典算法选择了 trigram：token 是输入字符串中每个重叠的三字符片段。

为什么是三？我们要将这些 trigram 作为倒排索引中的键存储。如果选择 bigram（2 字符块），我们的索引中键的数量会很少（最多 64k），但每个键的 posting list 会非常庞大——大到难以高效处理。如果选择 quadgram（4 字符块），posting list 会非常小（这是好事），但我们的倒排索引中会有数十亿个键，这也很难处理。

因此 trigram 是一个相当不错的折中方案。这使得索引文档时的分词变得非常简单：从被索引的文档中提取每个重叠的 3 字符序列，将其用作倒排索引中的 token。

真正的复杂性在于对正则表达式进行分词，使其能够在索引上匹配。正则表达式有自己的语法，因此你需要解析它们，并使用启发式方法从实际表示文本的表达式片段中提取 trigram。

将一个字面字符串分解为 trigram 很直接，与索引文档时的算法相同。提取字符串中包含的每个重叠 trigram；一个包含所有这些 trigram 的文档很可能包含该字面量（但不一定！）。交替项（alternation）被分别分解，产生两个分支，其中任一包含在文档中即可匹配。我们在倒排索引上通过合并（union）而非交集 posting list 来查询。字符类可以被分解为多个 trigram。像 [rbc]at 这样的小型字符类会为类中的每个元素产生一个 trigram。当使用更宽泛的字符类时，我们简单地跳过在这些边界上提取 trigram。

整合

我们知道 trigram 是分词这些文档的正确方式，我们知道如何在构建索引时对文档分词，以及如何在搜索时对查询分词。我们可以将所有这些组合成一个能够非常高效地匹配正则表达式的实际搜索索引。通过将任意正则表达式分解为一组 trigram 并从倒排索引中加载所有相关的 posting list，我们最终得到一个可能匹配我们正则表达式的文档列表。这很重要！最终的结果集只能通过实际加载所有潜在文档并”以传统方式”匹配正则表达式来获得。但拥有这个子集总比必须逐文件扫描和匹配整个代码库要快。

这种设计完全可以正常工作。像 google/codesearch 和 sourcegraph/zoekt 这样的项目使用 trigram 倒排索引提供了良好的大型索引性能（和所有搜索引擎一样，它们在此基础上附加了大量额外的复杂性）。但这里有明显的不足：索引大小不小，且查询时的分解必须做出权衡。如果使用简单的启发式方法，你会将查询分解为少量 trigram，这将导致大量潜在的匹配文档。如果使用复杂的启发式方法，你可能最终得到数十个——甚至数百个——trigram，从倒排索引中加载所有这些可能会变得和直接搜索一切一样慢。

我们可以做得更好。

Suffix Array：一次绕道

既然我们在回顾为正则表达式搜索索引文本数据的历史，我想绕个道讨论一下 Nelson Elhage 在 2015 年为其 livegrep Web 服务开发的实现。与其他大型行业项目相比，livegrep 很小——它只索引最新版本的 Linux 内核——但正因为其范围有限，它的实现与其他任何东西都截然不同，这使它非常有趣，值得一谈。

Nelson 从第一性原理出发攻克了这个问题：没有倒排索引驱动这个搜索引擎。相反，所有源代码都被索引在一个 suffix array（后缀数组）中。

Suffix array 的概念是不言自明的：一个字符串所有后缀的排序数组。如果你尝试为更长的字符串构建数组，你会看到这个数据结构增长很快。它看起来可能是一种特别昂贵的索引，在许多方面确实如此，但如果你有原始字符串的访问权限，其存储可以被很好地压缩：你只需存储每个后缀起始位置的偏移量。

一旦我们为要搜索的语料库构建了 suffix array，就可以通过将正则表达式分解为字面量来高效地执行正则表达式搜索。然后可以通过在 suffix array 上执行二分搜索来找到正则表达式的每个潜在匹配位置。

正则表达式语法中更复杂的结构可以利用 suffix array 的相同属性来匹配。例如，如果你要匹配一个字符范围如 [a-z]，可以通过二分搜索范围的起点和终点来缩小数组的范围。这两个端点之间的内容必然匹配该范围。

这里的不足是什么？Suffix array 必须从一个输入字符串构建。这是一个很大的限制。如果你试图索引一个大型代码库（或者可能是多个不同的代码库），你首先需要将所有内容连接成一个字符串，然后从中构建 suffix array。在 suffix array 中匹配时，你还需要一个辅助数据结构来将匹配位置映射到包含它的原始文件。这不是不可逾越的复杂性，但使得动态更新索引变得非常昂贵。这是一个非常难扩展的解决方案。

带有概率掩码的 Trigram 查询

回到一些更传统的设计：这是最初在 GitHub 的 Project Blackbird 中开发的方法。这是一个研究项目，旨在替换旧的 Code Search 功能。如我们之前所讨论的，旧的搜索是通过对源代码分词实现的，不能匹配正则表达式。这个新实现的目标就是开发一个可以做到这一点的系统。

最初的迭代尝试使用以 trigram 为键的经典倒排索引，但很快就遇到了容量问题。GitHub 上有大量的代码，使用 trigram 来索引导致 posting list 大到无法搜索。

由于 trigram 效果不太好，下一步是找到一个更好的 n-gram 大小来索引。我们已经看到 bigram 太宽泛（因为它们的 posting list 大得无法管理），而 quadgram 太具体（因为索引中会有太多键）。Trigram 是两者之间的甜蜜点，但在实践中，理想的大小更像是……3.5-gram。然而我们不能将一个字符分成两半，对吧？

实际上，我们可以做一些非常接近的事情：这种设计提议使用 trigram 作为倒排索引的键，并用关于”第四个字符”的额外信息来增强 posting list——即在该特定文档中跟在该 trigram 后面的字符。为此，我们可以简单地将第四个字符作为额外的字节存储，但这会把我们的索引变成 quadgram 索引，而我们已经看到那样太大无法存储。我们存储的是一个 bloom filter，它包含了跟在该特定 trigram 后面的所有字符。

你可能认为 bloom filter 是一个非常大且复杂的数据结构，但事实不必如此。你可以将 bloom filter 压缩到非常少的位中。如果编码时足够小心，8 位可以容纳大量信息。每个 posting 只需两个字节，我们就可以解决经典 trigram 索引中的两个最大问题。

通过拥有一个包含每个 trigram 后续字符的掩码，我们的倒排索引可以使用 trigram 键构建，但可以使用 quadgram 来查询！这已经比简单的 trigram 索引能更大幅度地缩小潜在文档的范围。

第二个增强掩码包含了 trigram 在文档中出现位置的偏移，解决了 trigram 歧义问题：仅仅因为一个文档包含两个 trigram 并不意味着它们实际上是相邻的，而这正是我们匹配查询所需要的。通过将第二个 trigram 的位置掩码左移一位并与第一个 trigram 的掩码进行比较，我们可以确保它们确实相邻。对于特别常见的 trigram，这对于进一步缩小候选文档列表来说是非常宝贵的。

当然，所有这些信息都是概率性的：和 bloom filter 中存储的任何东西一样，它可能产生假阳性。但在这里假阳性始终是可接受的，因为最终匹配是在文本本身上确定性地执行的。目标是使用我们的索引来最小化需要扫描的潜在文档数量。

由此产生的索引非常高效，但它们有一个主要的不足。Bloom filter 会饱和。这是 bloom filter 的一个不幸属性；它们可以被更新，但如果你往里面添加太多数据，最终过滤器中的所有位都被置位了。一旦 bloom filter 饱和，它就匹配所有东西，我们就回到了最初讨论的索引的性能水平。

这是一种最小化存储的索引，但当你需要就地更新它时会变得很痛苦。

Sparse N-gram：更智能的 Trigram 选择

这是另一个非常聪明的想法。你可能见过它被用在 ClickHouse 的正则表达式操作符中，也在 GitHub 新的 Code Search 功能中（几年前上线的，确实允许匹配正则表达式）。它被称为 Sparse N-gram，是各种折中方案中最甜蜜的。

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

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

关键在于，这意味着 sparse n-gram 可以有任意长度。它们是不一致的。这也意味着我们最终可能生成大量的 n-gram——比简单提取 trigram 要多。但因为 n-gram 是确定性生成的，我们可以在查询时做一些非常重要的优化。

那么这里的关键是什么？我们是不是做了什么蠢事？并非如此。我们在索引时支付了高昂的前期成本，以便在查询时能够非常快速。你现在看到的 build_all 算法就是我们在索引文档时使用的。它提取所有可能的 sparse n-gram。但请注意，我们在查询时不必这样做。因为权重是随机但确定性的，在查询时我们可以使用一个 covering 算法，只生成在索引中匹配所需的最少量 n-gram。

我们知道这些 n-gram 是最小的，因为在索引时，我们只在内部所有权重都小于边缘权重时才生成它们。因此，我们只需要提取边缘处的 sparse n-gram——远少于提取所有 trigram 的数量——就能以非常高的特异性选择我们的潜在文档。

我们能做得比这更好吗？可以！好得多。我们一直使用 crc32 作为算法中的权重函数作为示例。然而，任何哈希函数都可以在这里工作，只要它是确定性的。让我们选择一个非常聪明的：一个对实际上非常稀有的每对字符给予高权重、对非常频繁的每对给予低权重的哈希函数。

这个哈希函数很容易计算。由于我们要索引源代码，我们可以从互联网上获取几 TB 的开源代码，并为我们找到的所有字符对构建一个频率表。那个频率表就是我们的哈希函数。看看当我们将它应用到算法时会发生什么：最高的权重现在出现在最不频繁的字符对下面，正因如此，covering 模式产生的需要查找的 n-gram 甚至更少，可能匹配的文档也更少。

这种最小化 posting 查找数量的方法，将成为构建可在用户机器上高效查询的索引的完美起点。

所有这些，都在你的机器上

用于加速正则表达式搜索的索引需要存放在某处。到目前为止我们看到的所有设计都部署在服务器端，我们谈到的语义索引也是在服务器上管理和查询的。然而，我们在这里选择了不同的方向：我们在用户的机器上构建和查询索引。

将这些索引保持在本地有几个原因。首先，索引只是匹配正则表达式所需的一部分。它们提供了一个缩小范围的文档子集——正则表达式可能在其中匹配——但你仍然需要逐个扫描每个文件。在服务器上这样做意味着要么同步所有文件，要么进行昂贵的客户端-服务器往返。在客户端做这件事很简单，也回避了围绕数据存储的大量安全和隐私问题。

延迟对这个功能也非常重要。我们的 Composer 模型在行业中拥有最快的 token 每秒（TPS）之一，我们正在努力使其更智能且更快。为模型频繁使用的（通常是并行的）这样一个关键操作添加网络往返只会增加摩擦、阻塞，并将我们带向与 Agent 交互目标相反的方向。

与语义索引不同，正则表达式搜索的索引也需要非常新鲜，尤其是在模型读取自己写入的内容时。我们不必持续更新语义索引，因为在文件被修改后重新计算 embedding 不会导致新的 embedding 在多维空间中显著移位。我们执行的最近邻搜索仍然会将 Agent 引向正确的方向。然而，如果 Agent 在搜索特定文本却找不到，它通常会陷入一场无头苍蝇般的追逐，浪费 token，并让我们的性能优化前功尽弃。

将这些索引带到客户端确实有其自身的挑战。同步磁盘数据可能复杂且昂贵，但我们在实践中使其非常高效：我们通过将索引基于底层 Git 仓库中的一个 commit 来控制索引的状态。用户和 Agent 的变更作为一个层存储在其之上。这使得更新非常快，启动时的加载和同步也非常迅速。

为了确保编辑器中的内存使用保持最小，我们将索引存储在两个独立的文件中。第一个文件包含索引的所有 posting list，一个接一个——我们在构建过程中直接将其刷写到磁盘。另一个文件包含一个排序表，其中有所有 n-gram 的哈希值及其对应 posting list 在 postings 文件中的偏移量。这里只存储哈希值而不存储完整的 n-gram 始终是安全的：当两个哈希碰撞时（在实践中极不可能），它可能导致一个 posting list 变得更宽泛，但不会给出不正确的结果。这也为查找表提供了非常紧凑的布局。然后我们在编辑器进程中 mmap 这个表——且仅 mmap 这个表——并用二分搜索来处理查询。搜索返回一个偏移量，然后我们直接在 postings 文件的该偏移量处读取。

结论

我们发现，为快速模型（如我们自己的 Composer 2）提供文本搜索索引，为 Agentic 工作流创造了质的差异。这种影响在大型企业级仓库中更加显著，因为 grep 是少数几个延迟随所处理代码的大小和复杂度而增长的 Agent 操作之一。看看这些使用 Composer 2 运行的示例工作流：完全消除在代码库中搜索所花费的时间提供了有意义的时间节省——尤其是在 Agent 调查 bug 时——并允许更有效的迭代。

至于下一步会是什么，谁知道呢！围绕为 Agent 提供上下文有许多激动人心的发展，许多研究者在这个领域工作——包括我们自己的研究者。我们将继续优化当前方法的性能（包括语义索引），并希望能带来全新的方式来进一步提升 Agent 的性能，同时始终确保它们在真正重要的地方可以运行：在世界上最大的代码库中——那里 Agentic 开发的未来正真正获得牵引力。

引用

• 原文：Fast regex search: indexing text for agent tools — Cursor Research Blog, 2026-03-23
• Russ Cox, Regular Expression Matching with a Trigram Index, 2012
• Nelson Elhage, livegrep, 2015
• GitHub, The technology behind GitHub’s new code search, 2023