# 十月第二轮开发与审查（2026-10-03）

> 本文保留开发阶段证据。后续发布与验证结果见
> [0.1.0 发布记录](RELEASE_0.1.0.md)。

## 【1. 总体评价】

静态紧凑结构的边界清楚。本轮新增 Trie 序号反查、最长已存前缀、全部已存前缀长度三项能力。确认 `louds/trie_query.mbt` 的 collect 递归为每个边复制路径，单条深路径长 D 时累计复制 O(D²) 字节且有深调用栈风险；现改为显式 DFS 栈及单一路径，复制只发生在输出终端。

修改前源码及材料在 `docs/archive/20261003`，新测试包含 6,000 字节深词项。当前工具链既有派生方法和黑盒测试未限定包名警告仍使用明确 CI 基线，不宣称完全无警告。外部验收条件未完成；资料稿 20 行，参赛者空白。

## 【2. 算法与性能分析】

- 词项反查：沿树检查终端并以子树词项计数跳过兄弟子树，不枚举较早词项。时间 O(路径深度 × 最大分支数 × LOUDS 导航成本)，字节 Trie 分支数至多 256；空间为路径和单节点子列表。当前 rank/select 实现本身有成本，不宣称每步常数或序号反查 O(1)。
- 前缀匹配：沿输入字节找子节点，记录终端长度。最长匹配额外结果 O(1)，全部匹配 O(M)，M 不超过预算；遍历的子列表最多 256 项，实际导航成本依赖位向量查询。
- 方法名称：迭代 DFS 与可复用路径。链状词项路径维护由 O(D²) 复制降为 O(D)，时间还包括每节点拓扑导航与输出总字节 L。一般枚举成本 O(访问边/节点的导航成本 + L)，额外空间为 DFS 前沿、路径及返回词项。改动保留词法序和结果限制，不消除导航开销。
- 空终端前缀长度为 0，任意二进制词项可查；应用要为 URL/配置层级自行编码分隔符。

## 【3. 具体优化步骤】

1. 保留旧枚举/类型文件，移除只被递归调用的路径复制 helper。
2. 使用 `(children, next_index)` 显式帧；下降追加字节，返回弹出字节。
3. 反查按计数跳子树，输入越界立即返回 None。
4. 前缀长度沿同一路径取终端，输出前检查数量限额。
5. 补充二进制、空词项、反演、预算和深路径测试，接入路由示例/CI。

## 【4. 推荐修改后的代码】

实现见 `louds/trie_select.mbt`、`louds/trie_match.mbt`、`louds/trie_query.mbt`；`examples/routing/main.mbt` 展示 rank 反演和显式分隔符前缀。

```text
找到下个子节点 -> path.push(label)
若 terminal 则复制 path 作为一个输出
节点遍历完成 -> 弹出帧与路径末字节
```

## 【5. 测试建议与已执行证据】

- 正常：所有词项 term_at 与 term_number 互逆，多个前缀按长度递增。
- 边界：空词项、空 Trie、无匹配、负/末尾序号、字节 255、0 输出预算。
- 异常：匹配超预算，已有序列/拓扑/解码测试继续覆盖损坏结构。
- 大规模：6,000 字节深词项与兄弟词项的枚举、最长匹配和反查正确。
- 新增 `louds/trie_match_test.mbt` 3 项；完整四后端各 99 项通过。
- 全后端 check/build 使用 `--deny-warn --warn-list '-implicit_impl_as_method-test_unqualified_package'` 通过，routing wasm-gc 示例通过。性能建议增加大量共享前缀词项，分别记录拓扑导航与输出复制成本。