# 架构与算法

## 数据流

`JSON/PGM/库调用 → 校验与距离/嵌入/像素解析 → Rips 或 cubical 过滤复形 → GF(2) 约化 → 区间/代表链 → 比较或导出`

| 文件 | 职责 |
| --- | --- |
| types.mbt | 过滤细胞、区间、结果类型；稳定排序与面索引 |
| geometry.mbt | 有界点云校验、欧氏距离矩阵、圆形样本 |
| rips.mbt | 截止距离下的点、边、三角形 |
| cubical.mbt | 顶点 lower-star 的网格顶点、边与方格 |
| pgm.mbt | P2/P5 单图像解析、像素范围与大小校验 |
| image_processing.mbt | 灰度反转、Otsu 直方图阈值估计 |
| batch.mbt | 有界批量清单的严格解析与案例引用校验 |
| batch_matrix.mbt | 全对瓶颈矩阵、JSON/CSV 序列化与静态离线热图 |
| embedding.mbt | 有滞后与步长的时间序列窗口 |
| persistence.mbt | 输入复形校验、稀疏列约化、代表链、Betti 数 |
| diagrams.mbt | 图点提取、瓶颈距离、未死亡类匹配、Betti 曲线 |
| comparison.mbt | 匹配见证、原始区间索引映射、比较 JSON/CSV |
| comparison_dashboard.mbt | 离线双侧持续图、比较条件提示与匹配表 |
| json_io.mbt | 请求解析、报告序列化 |
| render.mbt | 独立 SVG 条形码与持续图 |
| features.mbt | 观察寿命、区间筛选/排名、有限持续熵、CSV 导出 |
| events.mbt | 出生/死亡事件排序、同尺度聚合、精确 Betti 阶梯曲线 |
| snapshot.mbt | 带路径压缩的并查集、指定尺度的分组与快照 |
| recommendations.mbt | H1 区间寿命排序、合并前 H0 尺度、推荐 JSON/CSV |
| landscape.mbt | 有限区间帐篷函数、按层采样、向量与 CSV |
| scale_render.mbt | 等比例投影、连通分组着色、存活代表链 SVG |
| dashboard.mbt | 自包含 HTML；显示预先计算的区间与几何投影 |
| cmd/main | MoonBit CLI + 仅处理参数/文件的 Node 宿主适配 |
| cmd/demo | 无宿主文件操作的可运行库示例 |

## 过滤与边界

按数值、维度、稳定键排序；同尺度面先于高维细胞。边界引用排序后的较早细胞。
GF(2) 下边的边界为两个端点、三角形为三条边、方格为四条边。
公共过滤结构在计算前验证值的单调性、面维数、索引顺序和 `∂²=0`。

Rips 只构建到二维，因为 H1 死亡由二维边界确定。高维复形无需为 H0/H1 创建，
但这种截断不能用于完整 H2 计算。网格采用另一种复形，并共享同一约化器。

## 稀疏约化

以排序整数索引表示边界列。GF(2) 列加法是有序数组的对称差。
从左到右处理列，若最大非零行已有主元列，就加该列以消去该行。
空列产生同调类；非空列的主元行与当前列形成出生/死亡配对。

对 0/1 维列同时累计换基链，得到出生时的代表。二维换基链无需保留，
因为只输出 H0/H1 代表。零长度类可在 API 中启用，CLI 默认省略。
代表不是最短环，不保证在其他同调实现中选出相同边集合。

## 瓶颈距离

有限图点使用 L∞ 距离；点到对角线的代价为 `(death-birth)/2`。
扩充左右二分图，使双方的点都可匹配到对角线副本。
最优阈值必在有限候选代价中：排序后对候选值二分，使用增广路检查完美匹配。
这计算瓶颈最小最大代价，不是贪心最近邻。

未死亡区间单独匹配；数量相等时按出生值排序做一维最优匹配。
数量不等时没有有限匹配，返回 None。输入截止会影响这一结论。

匹配见证复用同一代价矩阵与增广路求解器，在最优阈值重建列拥有者。
去除对角线到对角线的虚拟配对，把有限图索引映射回原始区间索引。
有限类到对角线的代价为寿命的一半；未死亡类仅按出生值匹配未死亡类。
当两侧未死亡数量不同，标记全部未死亡类为未匹配，代价与完整距离为 null。
报告给出一种最小最大代价匹配，不承诺唯一性或最小代价和，不解释为对象身份识别。
12 对形状检查每个区间恰好出现一次、各配对代价和最大代价。

## 复杂度与资源

距离矩阵 O(n²d)；三角形枚举最坏 O(n³)；过滤排序 O(M log M)。
边界约化最坏仍可达立方级，实际由稀疏性决定，不承诺 Ripser 的性能。
明确限制输入大小、细胞数、列加法数和总稀疏存储，避免无界计算。
匹配规模为有限区间总数，采用增广路和候选代价二分，小规模使用。

## 验证方法

已知答案测试覆盖正方形、三角形、重复点、分离簇、方格环和周期嵌入。
稠密参考算法直接计算 `β0=V-rank(∂1)`、`β1=E-rank(∂1)-rank(∂2)`，
独立于稀疏持续区间提取路径；在每个采样尺度核对结果。
瓶颈距离使用枚举所有扩充匹配的最小最大代价作参考。

## 解释与展示层

过滤结构保留可选二维显示坐标。点云距离仍从全部输入维度计算，
显示投影不会替代原始距离；网格索引保持原始行列位置，距离矩阵不虚构坐标。

有限区间的完整寿命为 death-birth；截止时未死亡类的观察寿命为 cutoff-birth 下界。
排名使用观察寿命，并在文档/界面提示截断语义。
有限持续熵是正寿命有限区间的 Shannon 熵（自然对数），不混入未死亡类。

离线 HTML 内嵌 JSON 结果与样式，不含外部资产或请求；数据中的 `<` 以 Unicode 转义，
防止细胞键中出现脚本结束标签。表格文本使用 textContent 创建，未将数据拼成 HTML。
JavaScript 只进行显示筛选、Betti 计数和投影；同调与瓶颈求解仍由 MoonBit 实现。
Betti 曲线读取 MoonBit 输出的全部事件，按真实尺度绘制阶梯线；滑块操作不重新计算同调。

## 事件、快照与持久景观

对每个区间生成出生 `+1`、死亡 `-1` 事件；排序后聚合同一尺度的全部增减。
记录聚合后的计数，因此严格遵守 `[birth,death)`。零长度区间贡献为零，
未死亡类没有伪造的截止死亡事件。首个细胞尺度与截止值也加入事件表。
复杂度 O(B log B)，不会因为均匀采样间隔漏掉短暂区间。

尺度快照筛选已进入的零细胞与边，以原始顶点编号建立并查集；路径压缩，
较大根连接到较小根，保证输出按最小顶点稳定排序。两个端点必须均为活跃顶点。
分组只依赖活跃一维骨架；H1 仍从约化区间计算。超出截止的快照拒绝查询。

持久景观采用公开定义：有限区间 `(b,d)` 在尺度 t 产生
`max(0,min(t-b,d-t))`；第 k 层取所有帐篷高度中第 k 大值，不足补零。
每个采样点以固定长度的有序数组保留前 K 个值，时间 O(BSK)，空间 O(SK)。
最多两百万次候选插入步骤；输入范围必须有限、严格递增。
从首尾都包含的均匀网格采样，输出按层排列与拼接；不采用额外缩放。
排除截断时未死亡的区间，并输出排除数量。不同库的采样和归一化约定可能不同。

算法定义参考 Peter Bubenik 的原始论文：
[Statistical Topological Data Analysis using Persistence Landscapes (JMLR, 2015)](https://jmlr.csail.mit.edu/papers/v16/bubenik15a.html)。
此实现未复制该论文工具包或 GUDHI 源码。

HTML 交互逻辑使用 Node VM 与 DOM 替身验证；不等同于真实浏览器渲染检查。
GUDHI 3.13.0 已在 22 个 Rips 案例上与 MoonBit H0/H1 区间一致；
外部差分不覆盖 cubical 网格、瓶颈匹配与代表链，细节见 [外部对照](reference-validation.md)。
已有 8–28 点的定规模耗时与分析后进程 RSS 基准，尚无峰值内存或大规模性能保证，
见 [性能记录](performance.md)。最短代表算法和在线上传应用仍未实现。

尺度 SVG 使用 MoonBit 并查集分组给顶点着色，以统一比例投影原始二维展示坐标。
网格报告与尺度 SVG 只绘制已经进入过滤复形的二维方格面，按四角原始索引形成非自交多边形；
点云的 Rips 三角形不在二维投影上填色，因为高维点的前两维投影可能误导几何解释。
离线报告的区间表对完整筛选结果排序，再以每页 50 条分页显示，筛选条件变化时重置页码。
所选索引必须是当前存活的 H1；代表链经过边索引校验再高亮。
无几何坐标时独立绘图 API 报错，CLI 可仅导出快照 JSON。
离线比较报告内嵌两侧持续图，JavaScript 仅筛选 MoonBit 已求得的匹配，不在浏览器求解。