# 架构与算法

## 数据流

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

| 文件 | 职责 |
| --- | --- |
| types.mbt | 过滤细胞、区间、结果类型；稳定排序与面索引 |
| geometry.mbt | 有界点云校验、欧氏距离矩阵、圆形样本 |
| rips.mbt | 沿邻接表枚举截止距离下的点、边、三角形及可选四面体 |
| cubical.mbt | 顶点 lower-star 的网格顶点、边与方格 |
| volume.mbt | 三维顶点值网格的顶点、棱、面与立方体；形状和资源预算校验 |
| volume_view.mbt | 体数据的离线 Z 层切片、三维代表面投影和全局 Betti 数展示 |
| volume_surfaces.mbt | H2 出生代表面导出、角点映射与解释 |
| representative_simplify.mbt | 在出生过滤层内用边界异或贪心缩短 H1/H2 代表链 |
| volume_resample.mbt | 有界粗网格采样与显式近似体数据分析 |
| volume_sequence.mbt | 有序体数据的 H2 区间轨迹与相邻帧距离 |
| nifti.mbt | NIfTI-1 三维头部、数据类型和强度缩放解析 |
| nifti_study.mbt | NIfTI-1 4D 帧序列、sform/qform/pixdim 仿射与时空元数据 |
| field_stability.mbt | 网格与体数据的确定性强度扰动及距离汇总 |
| pgm.mbt | P2/P5 单图像解析、像素范围与大小校验 |
| image_processing.mbt | 灰度反转、Otsu 直方图阈值估计 |
| batch.mbt | 有界批量清单的严格解析与案例引用校验 |
| batch_matrix.mbt | 全对瓶颈矩阵、JSON/CSV 序列化与静态离线热图 |
| batch_clustering.mbt | H0/H1 单链接层次分组、建议切分尺度及 JSON/CSV/SVG |
| 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 |
| stability.mbt | 点云确定性有界扰动与 H0/H1 结果敏感性统计 |
| series_sweep.mbt | 延迟嵌入参数扫描与有限 H1 候选排序 |
| series_hints.mbt | 逐滞后配对自相关、等宽分箱互信息与探索性参数提示 |
| sequence.mbt | 有界多帧点云分析、相邻帧瓶颈距离与 H1 区间轨迹 |
| study_report.mbt | 时间序列和稳定性研究的离线 HTML |
| scale_render.mbt | 等比例投影、连通分组着色、存活代表链 SVG |
| dashboard.mbt | 自包含 HTML；显示预先计算的区间与几何投影 |
| cmd/main | MoonBit CLI + 参数/文件/PNG 字节解码的 Node 宿主适配 |
| cmd/demo | 无宿主文件操作的可运行库示例 |

## 过滤与边界

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

Rips 默认只构建到二维，因为 H1 死亡由二维边界确定。显式请求 H2 时，
完整枚举阈值内的四面体，构建三维骨架，H2 的出生和死亡才能正确计算。
二维网格和三维体数据使用 cubical 复形，并共享同一约化器。三维体素
同时构造方形面与立方体，默认计算 H0/H1/H2。

## 稀疏约化

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

对需输出的维度累计换基链，得到出生时的代表。默认仅保留 0/1 维链；
请求 H2 时还保留二维链，不保留三维链。零长度类可在 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 已在 30 个 Rips/cubical 案例上与 MoonBit 的相应 H0/H1/H2 区间一致；
外部差分不覆盖瓶颈匹配与代表链，细节见 [外部对照](reference-validation.md)。
已有 8–28 点稠密、32–128 点稀疏输入的耗时与分析后进程 RSS 基准，尚无峰值内存或无限规模保证，
见 [性能记录](performance.md)。最短代表算法和在线上传应用仍未实现。

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