AI 搜索内核（一）：从字符串到符号

TL;DR

这是「AI 搜索内核」系列的第一篇，聚焦工具层：grep 和 LSP 是 AI 代码助手最底层的两个搜索原语。

grep 和 LSP 解决的是两个完全不同层次的问题。grep 是词法搜索：把代码当作字节流，在其中寻找匹配某个模式的子串。LSP（Language Server Protocol）是语义导航：理解代码的结构，知道 foo 这个名字在哪里被定义、在哪里被调用。

Claude Code 同时使用两者：先用 grep 快速探索，再用 LSP 精确定位。这不是随意的组合，而是对两种工具各自边界的精确利用。

1. 同一个问题，两个答案

假设 Claude 需要找到 authenticate 函数的所有调用点。

• 用 grep 搜索 authenticate，会返回：函数定义、所有调用、字符串 "authenticate"、注释里的 authenticate、变量名 isAuthenticated、文档里的 re-authenticate。在一个中等规模的代码库里，这可能是几百条结果。Claude 需要逐一判断哪些是真正的函数调用，代价是大量上下文消耗。

• 用 LSP 的 textDocument/references（Chen 注：`textDocument/references` 是 LSP 规范定义的请求方法，返回工作区内所有指向同一符号的引用位置（`Location[]`）。与 `textDocument/definition`（跳转定义）不同，它查的是「谁用了这个符号」而不是「这个符号在哪里定义」。），返回的是且仅是指向同一个符号的引用——定义在哪里、被谁调用。过滤在读任何文件之前就完成了。

但如果没有 grep，LSP 也无法独立工作：当 Claude 面对一个陌生代码库，它需要先找到切入点。没有索引，没有地图，第一步只能是搜索。grep 的价值在于零启动成本的探索能力。

这是两种工具的分工：grep 负责探索，LSP 负责精确。理解它们各自为什么快、为什么有上限，需要从算法内核开始看。

具体来说，Claude Code 的搜索通过 Bash 工具调用标准 grep，不依赖 ripgrep，环境里有什么用什么。一次典型的搜索任务会经过几轮递进：

第一轮：找到候选文件

grep -rl "authenticate" src/ --include="*.ts"

src/auth/middleware.ts
src/api/user.ts
src/utils/session.ts

第二轮：定位定义行

grep -n "function authenticate\|const authenticate\|authenticate\s*=" src/auth/middleware.ts

12:export async function authenticate(req: Request) {

第三轮：读文件，切换到 LSP

知道了定义在 middleware.ts:12，此时 Claude 读这个文件，再用 LSP 的 textDocument/references 拿到所有调用点，而不是继续 grep。

这个模式有几个值得注意的细节：

• -l 优先于直接输出匹配行——先拿文件列表，控制上下文消耗，再按需精读
• --include="*.ts" 过滤文件类型，grep -r 本身不感知 .gitignore，所以通常配合路径限定
• 正则模式从宽（第一轮）到窄（第二轮），逐步过滤，而不是一步到位
• grep 用来定位，LSP 用来导航：找到符号位置之后，跨文件引用追踪交给 LSP，不继续 grep

这也解释了 ripgrep 在这个场景里的价值：Claude Code 用标准 grep，但如果 codebase 里配置了 rg，它会自然用上——.gitignore 自动过滤、并行搜索、更快的大文件处理。差距在有 node_modules 的前端项目里尤其明显。

2. grep 的内核

2.1 暴力匹配的代价

最朴素的字符串搜索算法：对文本中每个位置，尝试从该位置开始匹配模式串。

def naive_search(text: str, pattern: str) -> list[int]:
    n, m = len(text), len(pattern)
    results = []
    for i in range(n - m + 1):
        if text[i:i+m] == pattern:
            results.append(i)
    return results

最坏情况复杂度是 $O(nm)$。对于文本长度 $n=10^8$（100MB 文件）、模式长度 $m=20$，这意味着 $2\times 10^9$ 次字符比较。即使每次比较只需 1ns，也要 2 秒——而 ripgrep 在同样规模的文件上通常在 100ms 以内完成。

差距来自三个层次的优化：字符串匹配算法、正则引擎设计、系统层 I/O 与 SIMD。

2.2 Boyer-Moore-Horspool：跳过，而不是逐一比较

朴素算法每次匹配失败只向右移动一位。Boyer-Moore-Horspool（BMH）（Chen 注：BMH 是 Boyer-Moore 算法的简化变体，由 R. Nigel Horspool 于 1980 年提出。完整的 Boyer-Moore 同时使用「坏字符规则」和「好后缀规则」，BMH 只保留坏字符规则，实现更简单，实际性能与完整版相近。）的核心思想是：利用模式串自身的结构，在失配时跳过尽可能多的位置。

BMH 从模式串的最右端开始比较（而不是从左到右）。当文本中某个字符与模式串最右端的字符失配时，查询「坏字符表」：如果这个失配字符在模式串中根本不存在，直接跳过整个模式串长度；如果存在，跳到模式串中该字符最靠右的出现位置对齐。

def build_bad_char_table(pattern: str) -> dict[str, int]:
    m = len(pattern)
    # 对模式串中除最后一个字符外的每个字符，记录从右端的跳跃距离
    table = {ch: m - i - 1 for i, ch in enumerate(pattern[:-1])}
    return table
 
def bmh_search(text: str, pattern: str) -> list[int]:

下图展示在文本 HERE IS A SIMPLE EXAMPLE OF 中搜索 EXAMPLE（坏字符表：E→6, X→5, A→4, M→3, P→2, L→1）时的跳跃过程：

BMH 的平均复杂度接近 $O(n/m)$——模式串越长，每次跳跃越远，搜索越快。这与朴素算法正好相反：模式串越长，BMH 越快。

2.3 多模式匹配：Aho-Corasick 自动机

grep 通常要同时处理多个关键词（如 -e pattern1 -e pattern2），或者处理从正则表达式中提取出的多个字面量前缀。对 $k$ 个模式分别跑 BMH 的复杂度是 $O(kn)$——模式数量翻倍，时间翻倍。

Aho-Corasick（AC）自动机（Chen 注：Aho-Corasick 由 Alfred Aho 和 Margaret Corasick 于 1975 年提出，原用于 Unix grep 的关键词检索。核心思想是在 Trie 上增加「failure link」（失配指针），使状态机在失配时能跳到最长匹配后缀对应的节点，而非回到根节点重新开始。这与 KMP 的 failure function 是同一思想在多模式场景下的推广。）把所有模式串编译成一个有限状态机，单次遍历文本就能同时匹配所有模式，复杂度 $O(n+z)$（$z$ 为总匹配数），与模式数量无关。

构建过程分两步：

1. 建 Trie（前缀树）：把所有模式串插入 Trie，每个叶节点标记对应模式。

2. 建 failure function（失配指针）：对 Trie 中每个节点，计算「当前前缀的最长真后缀对应的 Trie 节点」——失配时沿指针回退，而不是从头开始。这是 AC 自动机与朴素 Trie 搜索的关键区别。

ripgrep 依赖的 aho-corasick crate（同样由 Andrew Gallant 维护）实现了这个算法，并在此基础上加入了 SIMD 加速的 Teddy 算法——用 128/256-bit SIMD 寄存器同时检查多个字节位置是否是某个模式的起始字节，在多模式场景下可以达到接近内存带宽的搜索速度。

2.4 正则引擎：Thompson NFA

字面量搜索解决了精确匹配，但 grep 的核心能力是正则表达式。fn\s+\w+ 这样的模式无法用字面量匹配——需要一个正则引擎。

正则引擎有两种主流实现路线：

• 回溯引擎（Perl、Python re、JavaScript）：把正则编译成递归的回溯搜索。实现简单，支持反向引用，但存在指数级回溯的病态情况（ReDoS（Chen 注：ReDoS（Regular Expression Denial of Service）：构造特定输入使回溯引擎陷入指数级回溯。经典案例：正则 `(a+)+` 匹配字符串 `aaaaaaaab`——末尾的 `b` 无法匹配，引擎穷举所有分组方式后才放弃，复杂度 $O(2^n)$。Node.js、Ruby 等生产环境均有过因此引发的服务中断。））。
• Thompson NFA（Chen 注：NFA（Non-deterministic Finite Automaton，非确定性有限自动机）：状态机的一种，允许在同一输入下从一个状态转移到多个状态，也允许不消费输入字符的 $\varepsilon$ 转换。与 DFA（确定性有限自动机）相比，NFA 更容易从正则表达式直接构造，但模拟时需要同时追踪所有可能的活跃状态集合。）（RE2、Rust regex crate、ripgrep）：编译为 NFA，用 NFA 模拟保证 $O(nm)$ 的最坏复杂度，彻底消除 ReDoS。代价是不支持反向引用。

Thompson 构造法把正则表达式递归地编译成 NFA。四条基本规则：

• 字符：一条带字符标签的边，一个起始态，一个接受态。

• 连接 AB：把 A 的接受态用 $\varepsilon$ 转换连到 B 的起始态。

• 选择 A|B：新建起始态，用 $\varepsilon$ 分叉到 A 和 B 各自的起始态；新建接受态，A 和 B 的接受态各用 $\varepsilon$ 汇入。

• 闭包 A*：新建起始态和接受态，$\varepsilon$ 边允许跳过 A（零次），A 的接受态用 $\varepsilon$ 回到 A 的起始态（重复），也用 $\varepsilon$ 通向新的接受态。

以正则 ab*c 为例，编译出的 NFA：

NFA 模拟不是「选择一条路径走下去」，而是同时追踪所有可能的活跃状态集合。遇到字符 x，把当前活跃状态集中所有能消费 x 的状态转换后的目标状态合并，再做 $\varepsilon$-closure（沿所有 $\varepsilon$ 边扩展），得到下一个状态集。任意时刻的活跃状态集大小不超过 NFA 的状态数 $m$，因此复杂度严格是 $O(nm)$。

Rust regex crate 在此基础上实现了「惰性 DFA（Chen 注：DFA（Deterministic Finite Automaton，确定性有限自动机）：每个状态在同一输入下只有唯一的转移目标，无 $\varepsilon$ 转换，匹配时每个字符只需一次查表，复杂度 $O(n)$。代价是从正则表达式预先构造完整 DFA 的状态数可能是指数级的（最坏 $O(2^m)$）。「惰性 DFA」是折中方案：不预先构造全部状态，而是在 NFA 模拟过程中按需生成并缓存 DFA 状态，兼顾了构造代价和运行速度。）」：NFA 模拟过程中，把遇到的状态集缓存为 DFA 状态，重复访问时直接跳转，避免重复计算 $\varepsilon$-closure。对实际代码模式，大多数匹配路径会命中缓存，性能接近预先完全编译的 DFA，而不需要预先计算指数级数量的 DFA 状态。

2.5 ripgrep 的四层加速

ripgrep 的速度不来自单一技巧，而是四层优化的叠加。

第一层：字面量预筛。在运行正则引擎之前，从正则表达式中提取出必须出现的字面量子串（比如 fn\s+authenticate 中的 authenticate），用 memchr 或 Teddy SIMD 算法快速扫描整个文件，只把包含该字面量的行送入正则引擎。对大多数真实搜索模式，这一层过滤掉了 99% 以上的文本。

let regex = meta::Regex::new(pattern)?;
if let Some(lits) = regex.literal_lits() {
    // 用 Aho-Corasick/Teddy 做预筛，只有命中行才送入完整正则匹配
}

第二层：I/O 策略。ripgrep 根据文件类型动态选择 read() 还是 mmap()。mmap 让内核按需换入页面，避免把整个文件读入用户空间缓冲区；但对非普通文件（管道、设备文件）和空文件，mmap 无法使用。核心分支：

fn search_file_maybe_path<M, S>(/* ... */) -> Result<(), S::Error> {
    // 尝试 mmap；失败或禁用时返回 None
    if let Some(mmap) = self.config.mmap.open(file, path) {
        // 整个文件映射到内存，直接在字节切片上搜索
        return self.search_slice(matcher, &mmap, write_to);
    }

没有文件大小阈值——只要是普通文件且非空，就尝试 mmap。

第三层：目录遍历与过滤。ripgrep 内置了 .gitignore、.ignore、全局 ignore 规则的解析（ignore crate），在遍历文件系统时直接跳过不需要搜索的路径，而不是找到再过滤。这在 node_modules、target/、.git/ 这类目录上节省了大量 I/O。

第四层：并行搜索。ripgrep 用 crossbeam channel 把文件路径分发给线程池，多个文件并行搜索，结果汇总排序后输出。这一层在多核机器上带来线性加速，但排序输出保证了结果的确定性。

这四层共同解释了 ripgrep 比 GNU grep 快 5-10 倍的实测数据（Chen 注：数据来源：Andrew Gallant（ripgrep 作者）在 2016 年发布的基准测试博文[《ripgrep is faster than {grep, ag, git grep, ucg, pt, sift}》](https://blog.burntsushi.net/ripgrep/)，测试环境为 Linux，搜索 Linux 内核源码。不同场景倍数差异较大：`.gitignore` 过滤收益明显的前端项目可超过 10 倍，纯正则匹配场景下差距较小。）——不是因为算法更聪明，而是每一层的工程细节都做到了位。

3. LSP 的内核

3.1 N×M 问题

LSP 出现之前，每个编辑器需要为每种语言单独实现语言支持：跳转定义、查找引用、自动补全、悬浮文档。$N$ 个编辑器、$M$ 种语言，意味着 $N×M$ 个集成需要维护。

LSP 把这个问题变成 $N+M$：每种语言只需要实现一个 Language Server，每个编辑器只需要实现一个 LSP Client。两者通过标准协议通信，互不感知对方的内部实现。

Claude Code 作为 LSP Client，可以复用代码库中已有的 Language Server——clangd（C/C++）、rust-analyzer（Rust）、typescript-language-server（TypeScript）——直接获得符号级精度的导航，不需要自己实现任何语言分析。

3.2 传输层：JSON-RPC over stdio

LSP 的传输层是 JSON-RPC 2.0，默认通过 stdio 通信：编辑器启动 Language Server 进程，通过进程的 stdin/stdout 发送和接收消息。也支持 TCP socket，但 stdio 是最常见的模式。

消息格式是带 HTTP 风格 header 的 JSON：

Content-Length: 119
 
{
  "jsonrpc": "2.0",
  "id": 1,
  "method": "textDocument/definition",
  "params": { ... }
}

LSP 有三种消息类型：

• Request：有 id，需要对方返回 Response
• Response：对应某个 Request 的 id，携带 result 或 error
• Notification：无 id，不需要回复（如文件内容变更通知）

3.3 生命周期：能力协商

LSP 连接不是无状态的 HTTP——它有明确的生命周期，核心是启动时的「能力协商」：

initialize 时双方交换 capabilities：Client 告诉 Server 自己支持哪些客户端特性（比如是否支持增量文档同步），Server 告诉 Client 自己实现了哪些能力（是否支持 textDocument/references、workspace/symbol 等）。如果 Server 不支持某个能力，Client 就不发对应请求。

3.4 一次 textDocument/definition 的完整链路

跳转定义是 LSP 最基础的请求之一。请求结构：

{
  "jsonrpc": "2.0",
  "id": 42,
  "method": "textDocument/definition",
  "params": {
    "textDocument": { "uri": "file:///project/src/auth.rs" },
    "position": { "line": 47, "character": 12 }
  }
}

Server 收到请求后：

1. 根据 uri 找到对应文件的语法树（已在 didOpen（Chen 注：`textDocument/didOpen` 是 LSP 的 Notification（无需回复），Client 在打开文件时发送，携带文件 URI 和完整文本内容。Server 收到后开始解析该文件并建立语法树，后续对该文件的所有请求都基于这份已解析的状态。文件关闭时发 `textDocument/didClose`，修改时发 `textDocument/didChange`。） 时解析）
2. 根据 position 定位到具体的 AST 节点，提取符号名称
3. 在符号表（或 HIR（Chen 注：HIR（High-level Intermediate Representation，高级中间表示）：比 AST 更接近语义的内部表示，已完成名字解析（name resolution）和类型推断。不同语言的 Language Server 叫法不同：rust-analyzer 叫 HIR，clangd 内部类似概念叫 AST with semantic info，typescript-language-server 基于 TypeScript compiler API 的 TypeChecker。））中查找该符号的定义位置
4. 返回 Location：{ uri, range }

响应结构：

{
  "jsonrpc": "2.0",
  "id": 42,
  "result": {
    "uri": "file:///project/src/user.rs",
    "range": {
      "start": { "line": 12, "character": 7 },
      "end":   { "line": 12, "character": 19 }
    }
  }

注意整个过程没有任何字符串搜索——定位是通过符号表的索引完成的，复杂度接近 $O(1)$。

3.5 Language Server 内部：tree-sitter + HIR + 符号表

Language Server 要回答「第 47 行第 12 列是什么符号、定义在哪里」，需要三层内部结构：

• 解析层（tree-sitter）：大多数现代 Language Server 用 tree-sitter 做增量解析。tree-sitter 能在文件修改时只重新解析变更的部分，生成精确的具体语法树（CST）。对于一个 10 万行的文件，用户每次按键只触发局部重解析，而不是全量。

• 语义层（HIR / type resolution）：CST 只有结构，没有语义。Language Server 在 CST 上构建 HIR——解析名字绑定：foo 在当前作用域指的是哪个定义？是局部变量、函数参数、还是某个模块中的类型？

• 索引层（符号表 / workspace index）：跨文件查询需要知道整个 workspace 的符号分布。Language Server 在启动时对 workspace 全量索引，之后通过 textDocument/didChange 通知增量更新。rust-analyzer 的符号数据库基于 salsa（增量计算框架），只重新计算依赖了变更文件的那部分查询。

pub(crate) fn goto_definition(
    db: &RootDatabase,
    position: FilePosition,
) -> Option<RangeInfo<Vec<NavigationTarget>>> {
    let sema = Semantics::new(db);
    // 从语法树节点解析出语义实体
    let name_like = sema.find_node_at_offset

实际实现中 name_to_def 会处理所有情况：函数调用、类型引用、宏调用、trait 方法、生命周期标注……每种都有对应的 HIR 查询路径。

4. 两种精度的权衡

4.1 对比

这个对比解释了 Claude Code 的组合策略：grep 的启动成本是零，适合「我不知道该去哪里找，先搜一下」；LSP 的查询精度高，适合「我已经找到了这个符号，我需要知道所有引用它的地方」。

4.2 各家的选择

不同代码助手在这两个工具的组合上做了不同的权衡：

• Claude Code 采用「运行时主动搜索」（Chen 注：依据：Claude Code 官方文档描述的工具调用机制——通过 `Bash`、`Read`、`Grep` 等工具按需访问文件系统，没有预建的代码索引层。参见 [Claude Code 概览文档](https://docs.anthropic.com/en/docs/claude-code/overview)。）的架构：没有预建索引，每个会话按需 grep 和调用 LSP。优点是始终操作最新代码，没有索引陈旧问题；代价是第一次探索陌生代码库时效率较低。

• Cursor 在 grep/LSP 之上额外构建了向量嵌入索引（Chen 注：依据：Cursor 官方文档的 Codebase indexing 章节，描述了对本地代码库做向量嵌入并存储在本地的机制。参见 [Cursor Codebase Indexing](https://docs.cursor.com/context/codebase-indexing)。）：对整个 codebase 做语义向量化，查询时先通过向量相似度找到相关文件，再用 LSP 精确定位。这个分层让 Cursor 对「模糊的语义描述」（如「找到处理用户认证的逻辑」）有更强的处理能力，但需要维护索引的时效性——这正是 Claude Code 主动规避的问题。

• Kilo Code（开源）作为 VS Code 扩展，直接复用 VS Code 内置的 LSP 客户端：通过 vscode.executeDefinitionProvider 和 vscode.executeReferenceProvider 调用宿主编辑器已有的语言服务，不需要自己管理 Language Server 的生命周期。这是「站在编辑器基础设施上」的路线，实现最轻，但依赖用户已经配置好对应语言的 Language Server。

// Kilo Code 调用宿主 VS Code 的 LSP 能力
const definitions = await vscode.commands.executeCommand<vscode.Location[]>(
    'vscode.executeDefinitionProvider',
    document.uri,
    position,
);

三种路线对应三种不同的基础假设：Claude Code 假设「代码变化快，索引是负担」；Cursor 假设「语义相似度能弥补 grep 的不足」；Kilo Code 假设「编辑器基础设施已经足够好，不需要重建」。

5. 两个工具的上限

grep 的上限是词法边界。它无法区分同名函数的不同重载，无法理解 foo.bar() 中 bar 属于哪个类型，无法知道某个字符串是变量名还是注释。这些问题不是工程优化能解决的，是字节流搜索的根本局限。

LSP 的上限是 Language Server 的存在性和质量。对于一门没有成熟 Language Server 的语言（大量内部 DSL、遗留语言、新兴语言），LSP 无从提供帮助。对于 Python 这类动态语言，符号解析本身有歧义（变量类型在运行时才确定），Language Server 给出的「引用」可能是不完整的。

更深的局限在于：这两个工具都只回答「在哪里」的问题，不回答「为什么」。找到了 authenticate 的所有调用点，不代表理解了认证逻辑的整体结构；知道了 Config 结构体的定义，不代表理解了配置系统的设计决策。

这个局限引出了一个问题：AI 代码助手如何从「找到代码」进化到「理解代码库」？下一篇会讨论这个问题——不是用更好的搜索工具，而是从搜索架构层重新思考：什么时候应该预建索引，什么时候应该主动探索，以及向量检索在代码场景下真正能做什么、不能做什么。