AXIOM v1.3.24 · 算法库扩展十四：LZ77 / Huffman 最优前缀码 / Monotone Chain 凸包

零依赖单文件自验证 AI 微指令操作系统。本版算法库扩展十四：补全压缩族（接 BWT、算术编码）并开辟计算几何新域，三项均带 0 精确硬不变量。

① LZ77 压缩（Lempel–Ziv 1977，DEFLATE 骨干）— 滑动窗口贪心最长匹配，解码按 off 回读（支持自重叠匹配）。不变量：round-trip ≡ 原串 + 每个匹配复现所引用历史子串 + 贪心最长匹配 + 重复串有效压缩，0 精确。

② Huffman 编码（最优前缀码）（Huffman 1952）— 与算术编码成对（整数 bit vs 分数 bit）。不变量：round-trip ≡ 原消息 + 前缀无冲突 + Kraft 等式 Σ2^{-l}=1 + 加权码长 ≡ 暴力枚举最优前缀码 + 熵界，0 精确。

③ Monotone Chain 凸包（Andrew 1979，计算几何）— O(n log n)。不变量：顶点集 ≡ 独立 Jarvis 礼物包装法（两算法交叉）+ 严格凸 + 全部输入点在包内或边上 + 顶点合法，0 精确。

诚实记录：LZ77 检查体尾匹配消费计数 off-by-one（lit=null，往返本就正确）；Huffman 暴力最优 Math.pow 热循环逼近 3s 上限，改预计算 + 增量 + Kraft 早剪枝（三项新检查隔离合计仅 ~27ms）。

指标：核心不变量 377 → 380 · 算法库 63 → 66 组 · 无头 390/390 · UI 冒烟 32/32 · 算法层唯一检查 73 → 76 · verified 811/1024 不变 · axiom.html 1020.3 KB。

AXIOM v1.3.23 · 算法库扩展十三：带权带花树 / 算术编码 / 正交归一 DCT

零依赖单文件自验证 AI 微指令操作系统。本版算法库扩展十三，补齐图匹配的最后一块拼图，并新增压缩与信号变换两个疆域，三项均带可独立复算的硬不变量。

① Edmonds 带权带花树（一般图最大权匹配） — Edmonds 1965 / Gabow 1985 / Kolmogorov 2009 Blossom V 思想；原始-对偶 + 奇环收缩为花，移植自 e-maxx 加权 blossom（UOJ #81 验证实现）。补齐 v1.3.15 无权 blossomMatching 的权匹配空白。不变量：≙ 暴力枚举全部匹配子集（n≤10）+ 权全 1 退化 ≡ blossomMatching 最大基数 + 对称对合，0 精确。

② 算术编码（无损压缩） — Witten-Neal-Cleary 1987，BigInt 整数区间精确版，与 v1.3.22 的 BWT/FM-index 构成压缩族。不变量：round-trip ≡ 原消息（0 误差）+ 码长 ∈ [理想−1, 理想+2] Shannon 界。

③ 正交归一 DCT-II / IDCT — Ahmed-Natarajan-Rao 1974，JPEG/MPEG 谱基，与 v1.3.21 的 FWHT 同属正交变换族。不变量：IDCT(DCT(x)) ≡ x 完美重构 + CᵀC = I + Parseval 能量守恒 + 直流分量，≤1e-12。

注入期诚实记录 6 类缺陷（详见 CHANGELOG）：get_pr 花内下标反转、C++ 整除 vs JS 浮点破坏 dist===0 紧边判定、2D 数组下标 0 未初始化、算术解码后缀恢复、合法性检查对称伙伴误判、压缩位数浮点误差。

指标：核心不变量 374 → 377 · 算法库 60 → 63 组 · 无头 387/387 · UI 冒烟 32/32 · 算法层唯一检查 70 → 73 · verified 811/1024 不变 · axiom.html 1014.3 KB（零依赖单文件）。

v1.3.22 · 算法库扩展十二：Aho–Corasick / CDCL SAT / BWT+FM-index（374 不变量 · 60 组算法）

v1.3.22 · 算法库扩展十二：Aho–Corasick 多模式匹配 / CDCL SAT / BWT+FM-index

核心不变量 371 → 374 · 算法库 57 → 60 组 · 无头 384/384 PASS · UI 冒烟 32/32 · verified 811/1024 不变

新增三组旗舰算法（不占 1024 ISA 网格，各带硬不变量，全部 0 精确）

算法	世界顶级来源	硬不变量（独立复算路径）	残差
ahoCorasick 多模式匹配	Aho & Corasick (1975), SIAM J. Comput. 14(1)	匹配集 ≡ 暴力逐起点逐模式扫描（15 seed + 重叠模式族 a/aa/aaa/aaaa/aaaaa/she/hers + 5 大规模实例 20 模式 × 200 字符）+ fail 深度严格递减 + 转移 ≡ 最长后缀 + out ≡ 后缀模式集	0 精确
cdclSat CDCL SAT 求解器	Marques-Silva & Sakallah (1996)；GRASP/Chaff (2001)	SAT/UNSAT ≡ 暴力 2ⁿ ≡ 纯 DPLL（15 seed nv 6..12 + 8 相变区实例 nv 13..15）+ 模型逐子句合法 + 每条学习子句被原公式蕴涵（枚举全部满足赋值）+ 鸽巢原理 PHP(3→2)…PHP(6→5) 必 UNSAT（nv=30 用 CDCL + 纯 DPLL 双实现互证，CDCL 仅 157 次冲突）	0 精确
bwtTransform / bwtInverse / fmIndex / fmSearch BWT + FM-index	Burrows & Wheeler (1994)；Ferragina & Manzini (2000)	BWT 列 ≡ 暴力循环移位排序（15 seed + 6 长串/周期串 + 9 边界串含空串）+ 逆变换 ≡ 原文 + LF 为置换 + occ 语义逐位核验 + backward search ≡ 暴力 ≡ kmpSearch ≡ saSearch	0 精确

填补三个疆域：多模式串匹配（GNU grep / Snort / 编辑器高亮底座）· SAT 求解（MiniSat / CaDiCaL / Z3 SAT 后端同骨架）· 压缩与自索引全文检索（bzip2 / 基因组定位索引）。

沙盒/注入期抓获缺陷

• Aho–Corasick BFS 双入队（算法真 bug）：root 子节点在循环内外各入队一次 → 状态处理两次、out[u] concat 两遍 → 匹配集重复。
• 暴力「最长后缀」循环方向反了（检查体）：substring(L) 的 L 是起始下标，L=0 才是整串（最长）；反向遍历使期望值恒为 root。
• _bwtTables 字符表未去重（注入期算法真 bug，沙盒未暴露）：keys 逐位置 push → C 表被重复计数、FM 检索全错。再次印证「沙盒与注入实现结构不同时，必须让注入代码重跑同一套不变量」。
• demo 禁写死教科书常量：BWT demo 原本要写死经典 BWT 值（且记忆有误），改为运行时暴力循环移位排序对照。

指标

• 核心不变量 371 → 374（新增 3 条）
• 算法库 57 → 60 组（算法层唯一检查 67 → 70）
• 无头 384/384 PASS（整套自检 2.6 秒）· UI 冒烟 32/32（60 数据行 / 61 按钮 / 演示汇总 121 条）
• axiom.html 963.2 → 992.7 KB（零依赖单文件）
• verified 811/1024 不变（算法库不占 ISA 网格）

验证

npm test        # 384/384 + UI 冒烟 32/32
open axiom.html # 七视图仪表盘：「算法库 · 60」每组可一键运行真实计算

作者：晨星

v1.3.21 · 算法库扩展十一：Bron–Kerbosch 最大团 / 后缀数组+Kasai LCP / FWHT+zeta 集合卷积（371 不变量 · 57 组算法）

v1.3.21 · 算法库扩展十一：Bron–Kerbosch 最大团 / 后缀数组+Kasai LCP / FWHT+zeta 集合卷积

核心不变量 365 → 371 · 算法库 54 → 57 组 · 无头 381/381 PASS · UI 冒烟 32/32 · verified 811/1024 不变

新增三组旗舰算法（不占 1024 ISA 网格，各带硬不变量，全部 0 精确）

算法	世界顶级来源	硬不变量（独立复算路径）	残差
maxClique Bron–Kerbosch 最大团（pivot）	Bron & Kerbosch (1973)；Tomita (2006)	ω ≙ 暴力枚举 2ⁿ 子集（25 seed + 40 实例 n≤16 稀疏/稠密 + 5 经典实例）+ 全部极大团极大性 + α(G) = ω(Ḡ) + ω ≤ 贪心着色数	0 精确
suffixArray / saSearch 后缀数组 + Kasai LCP	Manber–Myers (1990)；Kasai (2001)	SA ≙ 朴素后缀排序 + LCP ≙ 暴力逐对 LCP（含全同字符/高度重复最坏情形）+ SA 为排列 + 二分搜索 ≙ 朴素匹配 ≙ kmpSearch	0 精确
fwht / fwhtConvolve FWHT + zeta/Möbius 集合卷积	Walsh–Hadamard (1923)；快速 zeta 变换	xor/or/and 三算子 ≙ 朴素 O(N²)（N=8..64，含负值）+ H² = N·I 正交性 + 线性性 + 单位元	0 精确

三个新领域：稠密子结构精确枚举（团/独立集/着色）· 字符串全文索引（BWT/FM-index 底座）· 布尔格变换（集合幂级数与子集卷积）。

沙盒 / 注入期抓获缺陷

• 递归函数原地 splice 容器参数：_cliqueExpand 复用同一个 P 数组 → 补图调用拿到空 P、α(G) 恒 0 → 多次调用各传独立副本。
• 计数排序关键字误传函数（算法真 bug）：key[src[t]] 取到 undefined → 排序退化为恒等排列、SA 全错 → 关键字一律传数组。
• 单位元随运算而变（检查体）：and 卷积单位元是 δ_{N−1}（全 1 元，i & (N−1) = i），不是 δ₀ → 断言按算子分别取单位元。

指标

• 核心不变量 365 → 371（新增 6 条）· 算法层唯一检查 61 → 67
• 算法库 54 → 57 组
• 无头 381/381 PASS · UI 冒烟 32/32（57 数据行 / 58 按钮 / 演示汇总 115 条全绿）
• axiom.html 937.2 → 963.2 KB（零依赖单文件）
• verified 811/1024 不变
• 仓库内文档行尾统一为 LF

验证

npm test        # 381/381 + UI 冒烟 32/32
open axiom.html # 七视图仪表盘：「算法库 · 57」每组可一键运行真实计算

作者：晨星

v1.3.20 · 算法库扩展十：有向最小树形图 / 精确 TSP / AC-3+CSP（365 不变量 · 54 组算法）

v1.3.20 · 算法库扩展十：有向最小树形图 / 精确 TSP / AC-3+CSP

核心不变量 359 → 365 · 算法库 51 → 54 组 · 无头 375/375 PASS · UI 冒烟 32/32 · verified 811/1024 不变

新增三组旗舰算法（不占 1024 ISA 网格，各带硬不变量，全部 0 精确）

算法	世界顶级来源	硬不变量（独立复算路径）	残差
arborescence 有向最小树形图	Edmonds (1967)；Chu–Liu (1965)	≙ 暴力父边组合枚举（负权/平行边/多根/不可行，25 seed）+ 结构自校验（每非根恰一入边、根可达、cost=Σ父边权、边序置换不变性）+ 40 实例稠密应力（n≤9）	0 精确
heldKarpTSP 精确 TSP	Bellman (1962)；Held & Karp (1962)	≙ 暴力 (n−1)! 排列（对称 + 非对称，n≤7，25 seed）+ 环游合法 + cost 自一致 + 2-opt 局部最优 + ≤ 最近邻贪心	0 精确
ac3CSP AC-3 + CSP 求解	Mackworth (1977)；MAC (Sabin–Freuder 1994)	决策 ≡ 暴力枚举全部域组合（SAT/UNSAT 双侧，25 实例）+ 解合法 + AC-3 不动点（双向弧逐值有支持）+ 不删解值	0 精确

三个新领域：有向图优化（此前全为无向图/流/匹配）、NP-hard 精确组合 DP、约束满足与符号推理。

沙盒抓获缺陷（再次印证两条铁律）

• 树形图层级展开丢失（算法真 bug）：迭代式「暂定父边后写覆盖」在高层簇取代低层簇时无法回滚被覆盖成员的低层选择（seed 5/14/22 暴露）→ 改为**递归收缩 + 每层返回最终父边表（chosen map）**的结构化展开。
• 暴力参照负权剪枝失效 + 平行边字典后写覆盖（检查体）：cost >= best 早停在有负权时错误 → 改用后缀最小剩余权 minRem；平行边权字典应保留最小权。
• AC-3 断言分支错位（检查体）：「域擦空 ⇒ 暴力须 UNSAT」误注入 consistent 分支 → 该断言仅属 UNSAT 分支。

指标

• 核心不变量 359 → 365（新增 6 条）
• 算法库 51 → 54 组（算法层唯一检查 55 → 61）
• 无头 375/375 PASS · UI 冒烟 32/32（54 数据行 / 55 按钮 / 演示汇总 109 条全绿）
• axiom.html 793.5 → 937.2 KB（零依赖单文件）
• verified 811/1024 不变（算法库不占 ISA 网格）

验证

npm test        # 375/375 + UI 冒烟 32/32
open axiom.html # 七视图仪表盘：「算法库 · 54」每组可一键运行真实计算

作者：晨星

v1.3.19 算法库扩展九

集大成验证算法库扩展九（48 → 51 组，核心不变量 356 → 359）——三组分别覆盖指派问题的价格机制、无货币房屋交换核心配置、通用线性规划三个新方向，各带可独立复算的硬不变量：

新增三组旗舰算法

1. 拍卖算法解指派问题（Bertsekas 1981）

ε-标度价格拍卖：未匹配者对「效益−价格」最高与次高对象竞价（加价 = 差 + ε），ε 逐相 ÷n 至 < 1/n；每相重启匹配、保留价格（首相后若不重启则只具 ε₀-最优性）。

• 不变量：≙ hungarianMaxWeight（−费用对偶一致）≙ 暴力枚举 n! 排列（最小费用，n≤7，25 seed）→ 0 精确

2. Top Trading Cycles（Shapley–Scarf 1974）

函数图逐轮找环交易（初始禀赋 + 严格偏好）；输出 = 唯一弱核配置（Roth–Postlewaite 1977）且必在强核中；防策略操纵。

• 不变量：≙ 暴力枚举 n! 配置的弱核/强核扫描（弱核唯一 + TTC=弱核 + TTC∈强核，n≤5，25 seed）→ 0 精确

3. 两阶段单纯形 LP（Dantzig 1947 + Bland 1977）

max cᵀx s.t. Ax {≤|≥|=} b, x≥0（可选上界）；阶段一人工变量判可行，阶段二原始单纯形 + Bland 规则防退化循环。

• 不变量：≙ 暴力顶点枚举（m 约束取 n 等式组 + solveLinear，混合约束，25 seed）→ 1.42e-14

沙盒抓获缺陷（4 处，其中 1 处算法真 bug）

• 拍卖首相后 ε₀-最优性丧失 → 每相重启匹配保留价格
• TTC 强核唯一性误判（严格偏好下强核不必唯一，唯一的是弱核；强核阻塞须「全体严格更优」）
• LP 行取反翻向（a·x≤b, b<0 取反得 ≥）+ 人工列号须终值两遍分配
• 选前查库避重复（CG 已存在于 OPTIM.cg → 改选单纯形）

指标

• 核心不变量 356 → 359（369/369 PASS）
• 算法库 48 → 51 组；算法层唯一检查数 55（51 组 chk 前缀去重实测）
• UI 冒烟 32/32；axiom.html 793.5 KB；verified 811/1024 不变

v1.3.18 算法库扩展八

AXIOM v1.3.18 · 算法库扩展八

新增 3 组旗舰算法（不占 1024 ISA 网格），各带可独立复算的硬不变量，全部 0 精确：

• Push-Relabel 全局最小割（Goldberg 1985 / Goldberg–Tarjan 1988）
  以 Push-Relabel 最大流为引擎的第二种、原理不同的全局最小割（≙ stoerWagner）。
• 2-SAT 可满足性（Aspvall–Plass–Tarjan 1979）
  蕴含图 SCC 判定 + 缩点 Kahn 拓扑序贪心构造可行赋值（≙ 暴力枚举 2ⁿ）。
• 桥与割点（Tarjan 1974）
  DFS + disc/low 单遍线性算法（≙ 暴力删边/删点连通分量计数）。

指标

• 核心不变量 353 → 356
• 算法库 45 → 48 组
• 无头 366/366 PASS（verified 811/1024 不变）
• UI 冒烟 48/48（演示汇总 52 项检查全绿）
• axiom.html 773.0 KB

沙盒抓获缺陷（已修复）

• 2-SAT litNode 作用域 n 未传入的 ReferenceError。
• 2-SAT 初版依赖 tarjanSCC 非拓扑序的 comps 判赋值方向导致非法赋值 → 改缩点 + Kahn 拓扑序贪心（印证「tarjanSCC 排序不可据此判拓扑方向」铁律）。

完整记录见 CHANGELOG.md / docs/ALGORITHMS.md。

v1.3.17 算法库扩展七

算法库扩展七（42 → 45 组，核心不变量 350 → 353）

三组均为世界顶级算法，硬不变量全部 0 精确：

• Push-Relabel 最大流（Goldberg–Tarjan 1988）：预流推进 + 高度标号。≡ maxFlowEK ≙ maxFlowDinic（整数容量 0 容差，25 图）→ 0（精确）
• Hungarian 最大权二分匹配（Kuhn 1955 / Munkres 1957）：位势法 O(n³)。≡ mcmfSSPRef ≙ 暴力枚举排列（n≤8）（0 容差，25 图）→ 0（精确）
• Gale–Shapley 稳定婚姻（Gale & Shapley 1962，Shapley 诺贝尔）：求婚者主动算法。结构不变量——完美匹配 + 稳定（无 blocking pair），男/女主动均稳定（0 容差，25 实例）→ 0（精确）

沙盒抓获缺陷

• 随机最大流测试实例生成器偶发 s === t，maxFlowEK/maxFlowDinic 对 s===t 死循环（生产函数对 s≠t 正确，属测试输入 bug）。修正生成器保 s≠t。

指标

• 核心不变量 350 → 353
• 无头 363/363 PASS（verified 811/1024 不变）
• UI 冒烟 45/45（算法库 45 数据行 / 46 按钮 / 演示汇总 49 项检查全绿）
• axiom.html 760.8 KB

铁律：零重写 + 集大成 + 闭环交付（GitHub 可运行 / 可复现 / 可验证）。

v1.3.16 · 算法库扩展六

AXIOM v1.3.16 · 算法库扩展六

核心不变量 347 → 350；算法库 39 → 42 组；无头 360/360 PASS（verified 811/1024 不变）；UI 冒烟 42/42。

新增 3 组旗舰算法（不占 1024 ISA 网格，各带可独立复算的硬不变量）

1. Gomory–Hu 树（Gomory & Hu 1961）

经 n−1 次原图最大流（Edmonds–Karp + 残差可达集→源侧顶点集）缩并 laminar 割，构造一棵树——任两点 u,v 最小割 = 树中 u–v 路径最小边权。

• 硬不变量：≡ 暴力枚举 2^(n−1) 的 s-t 割（整数 0 容差，120 图）→ 0（精确）

2. Radix-4 FFT（Cooley–Tukey 基-4 DIT）

长度 N=4^k 拆 4 个 N/4 子问题，蝶形复用 radix-2 的 4 点 DFT；抽取 x[4p], x[4p+1], x[4p+2], x[4p+3]，旋转因子 w/w²/w³。

• 硬不变量：≡ 朴素 DFT ≙ fft（radix-2）（N = 4/16/64/256）→ 1.43e-12

3. NUTS 对角质量矩阵自适应（Hoffman–Gelman 2014 + Stan warmup）

warmup 期用 Welford 估计目标协方差对角，设对角质量矩阵 M=diag(Σ)；leapfrog 动力学改为 p∼N(0,M)、H=U+½pᵀM⁻¹p。

• 硬不变量：≡ 目标协方差对角（2D 异方差 σ²=[4,1]，20 seed 池化）→ 5.21e-2（容差 0.1，余量 ~1.9×）

沙盒抓获缺陷（再次印证铁律：检查体自身也会错）

Gomory–Hu 暴力 ground-truth 两处 bug（非算法本体，本体始终正确）：

1. rv 与 t 同侧时 t–rv 内部边被误计入割 → 修正为按侧仅计 cb(s,rv) 或 cb(t,rv)
2. s–t 边恒跨割却从未计入 → 修正为循环前先 cut = cb(s, t)

指标

• 核心不变量 347 → 350
• 无头 360/360 PASS（verified 811/1024 不变）
• UI 冒烟 42/42（算法库 39→42 数据行 / 43 按钮 / 演示汇总 85 条全绿）
• axiom.html 749.2 KB

铁律：零重写（锚定世界顶级成果语义）+ 集大成 + 闭环交付（GitHub 可运行/复现/验证）。每条 verified 须带可独立复算的硬不变量。

v1.3.15 · 算法库扩展五：Edmonds blossom / Split-radix FFT / Stoer–Wagner

算法库扩展五（36 → 39 组，核心不变量 344 → 347）

本轮三组均为确定性算法，硬不变量做到绝对 ground truth 交叉，三条全部 0 精确：

算法	来源	硬不变量	实测残差
Edmonds blossom 一般图最大匹配	Edmonds (1965)；Berge (1957)	≡ 暴力枚举全部匹配子集（200 图）+ 合法性 + 极大性 + 二分图退化 ≡ Hopcroft–Karp（120 图）	0（精确）
Split-radix FFT	Yavne (1968)；Duhamel–Hollmann (1984)	≡ 朴素 DFT ≙ fft（radix-2），N = 2..64	1.81e-13
Stoer–Wagner 全局最小割	Stoer & Wagner (1997)	≡ 暴力枚举 2ⁿ 划分 ≙ n−1 次 s-t 最小割（maxFlowEK，Gomory–Hu）	0（精确）

为何是它们

• blossom：Kuhn / Hopcroft–Karp 只在二分图成立。一般图的奇环会让交错树出现「花」，必须缩并才能继续增广 —— 组合优化的经典分水岭。
• split-radix：T(N)=T(N/2)+2T(N/4)+Θ(N)，把奇序号切成 4m+1/4m+3 共轭对子变换共享旋转因子，2 的幂长度已知最低运算量档。
• Stoer–Wagner：全局最小割无需指定 s/t，O(n³) 比跑 n² 次最大流小一个量级。

沙盒先行：三组算法本体在首轮即与暴力 ground truth 完全一致；连抓的 3 项缺陷全部落在检查体/测试侧——检查体双重计数虚报 826 次违规、二分图交叉索引用错绝对/相对索引造成 worst=3 假阳性、以及一行恒 0 死代码。UI demo 也已用真实 2⁸ 暴力枚举交叉替代硬编码期望值。

指标：核心不变量 344 → 347 · 无头 357/357 · UI 冒烟 33/33（算法库 36→39 数据行 / 40 按钮 / 演示汇总 79 条全绿）· verified 811/1024 不变 · axiom.html 731.6 KB。

单文件零依赖，浏览器打开 axiom.html 或 npm test 即可复现全部 347 项不变量。