Cursor 三元组索引用于快速正则搜索

Cursor 的本地三元组索引加速大型仓库中的正则搜索

Cursor 在 IDE 中直接实现了用于正则搜索的本地索引。这解决了大型单体仓库中扫描缓慢的问题，在那里，经典的 ripgrep 每次调用都需要 15 秒以上，而 AI 代理会生成数十个这样的查询。

该技术基于 1993 年的三元组倒排索引。文本被分解成所有 3 个字符序列（trigrams），这些序列作为字典中的键。每把键对应一个包含该序列的文件列表。正则查询被分解成一组 trigrams，倒排列表被交集以选择候选文件。然后仅对数十个文件而不是数千个文件应用 grep。

用于精确范围限定的稀疏 n-grams

在基础索引之上，添加了稀疏 n-grams。每 个 n-gram 的长度是确定性地计算的：使用基于 crc32 的字符对权重，或从数 TB 开源代码构建的频率表。

索引时生成所有可能的 n-grams；搜索时使用最小覆盖集。这减少了查找次数并提高了过滤精度。

// Example dekompozitsii regex in n-grams
regex: \w+@\w+\.com
n-grams: ['@', 'w+', '.c', 'com', ...]  // sparse pokryodkrycie
candidates = intersect(postings(ngrams))

本地存储与提交绑定

索引以两个 mmap 文件的形式本地存储在用户机器上。原因：

• AI 代理反正仍会本地读取文件进行最终验证。
• 网络往返会破坏速度提升。

索引绑定到特定的 git 提交。未提交更改会叠加在其上，而无需重建。

• mmap 优势： 加载零开销，通过倒排列表的快速导航。
• 更新： 在 git pull/push 或手动重建时触发。
• 大小： 与代码库成比例；对于 1000 万行代码 — ~500MB。

性能对比

| 方法 | 每个查询时间（1 万文件） | grep 候选文件数 |

|-----------------------|--------------------------|-----------------|

| ripgrep | 15–20 秒 | 10k |

| Cursor 索引 | 50–200 毫秒 | 10–50 |

在代理发出 100+ 个查询的实际场景中，整体加速可达 100 倍。

Trigrams 确保完整性（精确子串 recall=1），而稀疏 n-grams 增加精确度而无假阳性。

关键点

• 三元组索引将候选文件从数千减少到数十个。
• 稀疏 n-grams 通过最小覆盖集最小化查找次数。
• 本地 mmap 存储消除网络延迟。
• 绑定到 git 提交，并叠加未提交更改。
• 为大型单体仓库中 AI 代理的正则搜索带来 100 倍加速。

— Editorial Team