tgrep核心原理24位Trigram索引如何把候选文件缩小90%以上【免费下载链接】tgrepTrigram-indexed grep with a client/server architecture for fast regex search in large codebases locally项目地址: https://gitcode.com/gh_mirrors/tg/tgreptgrep 是一个基于Trigram三元组索引的快速正则搜索工具采用客户端/服务端架构专为大型代码库设计已被集成进 GitHub Copilot CLI 来驱动仓库级 grep 搜索。它的核心思想只有一句话先用 24 位 Trigram 倒排索引把可能包含匹配的候选文件集合缩小 90% 以上再对剩余少数文件运行完整的正则引擎。这篇文章会用通俗的方式带你理解这套原理。什么是 Trigram24 位密钥的由来所谓 Trigram三元组就是把一段文本按滑动窗口切成连续的 3 个字节。以hello为例会切出hel、ell、llo三个 Trigram。tgrep 把每个 Trigram 打包进一个 32 位整数里(a 16) | (b 8) | c实际占位恰好24 位3 字节 × 8 位。这意味着全部可能的 Trigram 数量上限约为16.7M2^24种打包是单射injective——任意两个不同的 3 字节序列绝不会被压成同一个值零哈希冲突连加密哈希函数都不需要 这也是为什么源码里把 Trigram 的哈希器写得极其简单tgrep-core/src/trigram.rs 中的hash函数只做三次移位和或运算。三步流水线建索引 → 拆查询 → 求交集第 1 步索引——把文件→内容倒过来存tgrep index .执行时tgrep 遍历仓库遵守.gitignore等规则对每个文本文件并行提取所有去重后的 Trigram构建一张倒排表Trigram → [包含它的文件列表]。磁盘格式刻意做得极简见 tgrep-core/src/ondisk.rs文件内容单条记录大小lookup.bin按 Trigram 排序的查找表支持二分查找16 字节index.bin拼接的倒排列表file_id 两个掩码字节仅 6 字节files.binfile_id → 文件路径映射变长整个索引可以直接**内存映射mmap**进进程查询时几乎零解析成本。第 2 步查询规划——把正则拆成 Trigram 条件这是缩小 90%发生的关键一步。tgrep 用regex-syntax把你的正则解析成 HIR正则语法树提取其中必然出现的字面量片段每个片段转成一组 Trigram 查询。以搜索fn main为例字面量贡献fn、n m、ma、mai、ain五个 Trigram构成一个AND 计划tgrep-core/src/query.rs 定义了And/Or/MatchAll三种计划节点搜索foo|bar→OR 计划两个分支的候选集取并集搜索mutex.*mutex_lock→ 两段字面量分别展开合并为一个大AND 计划模式太短或全是通配符 →MatchAll无法利用索引退化为全量扫描保证不漏第 3 步执行——先小后大的列表交集执行时tgrep-core/src/query.rstgrep 对每个 Trigram 二分查找lookup.bin取出倒排列表然后选出最短的列表作为起点最少的假设文件数依次与其他列表做有序交集两个指针归并极快中间结果一旦为空立即短路退出交集做完后正则引擎只在这些候选文件上验证完整匹配。假设 50 万个文件中只有 3000 个同时包含fn和ain等 Trigram正则引擎要读的字节量就少了两个数量级——这就是 90% 以上缩减率的具体来源。藏起来的 2 个字节如何进一步剔除假阳性倒排列表里每条记录只有 6 字节其中除 file_id 外还有两个信息量很大的掩码tgrep-core/src/trigram.rsloc_mask位置掩码记录该 Trigram 出现在文件里哪些offset % 8位置。字面量中相邻的两个 Trigram 要真相邻出现它们的位置掩码旋转后按位与必须非零否则该文件直接淘汰next_mask下一字节 Bloom 过滤器8 位微型过滤器记录该 Trigram 后面跟过哪些字节。比如abc后面没跟过d那含abcd的查询就可以提前排除它这两个字节让候选集在不打开任何文件的情况下进一步收缩且代价几乎为零。实测验证用 --stats 亲眼看到缩减率你可以用--stats标志亲眼看到索引的裁剪效果tgrep --stats -- pub fn .输出类似Query plan: AND(4 trigrams) (candidates: 217/152340; raw candidates: 4831/152340)含义是索引先筛出 4831 个原始候选再经 glob/类型等过滤后只剩217 个文件——缩减率约99.9%。如果打印出(no index narrowing)说明该查询退化为全量扫描候选数等于索引总数实现见 tgrep-cli/src/search.rs。索引什么时候会失效诚实来说Trigram 索引并非万能以下情况会退化为扫描所有索引文件模式提取不出 ≥3 字节的字面量如.、a{0,3}、纯字符类→ MatchAll交替分支中有一支不可索引foo|.→ 整个 OR 计划吸收为 MatchAll-P高级 PCRE 特性tgrep 会先尝试放宽模式删掉零宽断言等能救回字面量就继续走索引救不回才全量扫描。放宽只允许扩宽匹配语言、绝不允许收窄以免漏掉真命中tgrep-core/src/query.rs显式指定文件、--no-index、转码场景直接绕过索引读磁盘这种宁可多搜、绝不漏搜的保守设计是正确性的底线。效果有多快大仓库基准测试官方基准在 6 个真实大仓库上对比 ripgrep索引预先建好测量纯搜索延迟见 BENCHMARKS.md仓库文件数最大加速比chromium/chromium504,35117.6xmozilla/gecko-dev387,84151.9xtorvalds/linux95,83134.8xrust-lang/rust62,3267.69x仓库越大、可索引查询占比越高候选集缩减的红利越明显而在匹配量极大的小仓库如 kubernetes 上的 Linux 环境中投递匹配行的成本可能超过索引节省的选文件成本tgrep 与 ripgrep 基本打平——这是基准数据里唯一 ripgrep 胜出的组合。核心源码地图想深入阅读重点看这几处核心库位于tgrep-core/CLI 与服务端位于tgrep-cli/Trigram 提取与掩码计算tgrep-core/src/trigram.rs正则 → 查询计划含 PCRE 放宽逻辑tgrep-core/src/query.rs磁盘索引格式与读写tgrep-core/src/ondisk.rs客户端/服务端混合索引mmap 增量层tgrep-core/src/hybrid.rs查询统计与--stats输出tgrep-cli/src/search.rs总结tgrep 用 24 位无冲突的 Trigram 键 16 字节查找表 6 字节倒排记录把在整个仓库跑正则变成先查倒排表、交集、再验证三步走。索引负责选对文件正则引擎负责选对行——分工明确才是快 90% 的真正原因。【免费下载链接】tgrepTrigram-indexed grep with a client/server architecture for fast regex search in large codebases locally项目地址: https://gitcode.com/gh_mirrors/tg/tgrep创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考