# 压缩列表游标分页与字节模糊检索

## Elias–Fano 去重游标分页

`EliasFano::page_distinct(after, limit)` 返回严格大于可选值游标的至多 limit 个
不同整数，`DistinctPage::next_after()` 仅在还有数据时返回本页最后值。
首次传 None；`has_more()` 为 false 后停止。游标属于同一不可变列表，不能在末页
把 None 当继续标志，否则会重新开始。大小限制 1..65536，UInt64 最大值无需加一。

用于压缩倒排表分批传输、索引合并输入、低内存检索 API。重复值通过 upper_bound
跳过，无需解压整个列表。设 U(n) 是现有 upper_bound 代价、A(n) 是 at 代价，
一页 p 个值时间 O((p+1)*U(n)+p*A(n))，新增空间 O(p)；返回数组为独立副本。

## LOUDS 字节编辑距离检索

`Trie::fuzzy_terms(query, distance, max_results~, max_work~)` 在压缩字典上按
Levenshtein DP 行逐层推进并剪枝，返回含词条和距离的结果，按无符号字节字典序排列。
支持插入、删除、替换，不支持相邻交换；不是 Unicode 字符距离，也不做规范化。
可用于 ASCII 标识符、命令名、协议字段与词典容错输入。

query 最多 1024 字节，距离 0..8，结果最多 4096，默认工作预算 1000000 个
DP 单元（上限 10000000）；超工作量或结果预算直接失败，不返回不完整命中集。
设 q 为查询长度、V 为实际访问的边数、F 为待处理前沿节点数、D 为保留前缀深度：
DP 时间 O(V*(q+1))，加上前缀复制 O(V*D) 和现有 LOUDS 子节点导航开销；
工作空间 O(F*(q+1+D))，另加输出。剪枝使保留前缀深度不超过 q+distance。
预算在分配下一 DP 行前检查；不是对整棵树声明无条件常数空间。

## 验证范围

`eliasfano/page_test.mbt` 比对普通数组分页、重复段、最大值和副本隔离；
`louds/fuzzy_test.mbt` 检查插入/删除/替换、空词、精确模式、参考距离与预算拒绝。

## 本地复现

要求 moonc >= 0.10.16。在本地源码目录执行：

```sh
moon update
python tools/verify_toolchain.py
moon check --target all --deny-warn
moon build --target all --deny-warn
moon test --target all --deny-warn
moon run examples/search_pages --target wasm-gc --deny-warn
moon run examples/search_pages --target native --deny-warn
```

Windows 如遇 OCaml 扩展路径问题，使用仓库提供的 `tools/windows/moon.ps1`
代替 `moon`。

以上 API 从 **0.2.0** 起提供：`moon add binhongcha/moonsuccinct@0.2.0`。
全部示例为可运行断言，不代表已有生产部署。