企业官网建设流程全解析

PIVCO-Huffman

🚧 WIP — 进行中 🚧

PivCo-Huffman 是一个优化 Huffman 编码性能的研究项目。虽然它提供了库和大量代码，但远未达到生产就绪的程度。

论文（HTML、PDF）是权威的详细阐述；本 README 是简短摘要。

TL;DR

在 Apple M4 上的具体数据，pivco_bu解码 vshuf0_x2：

• proba80高度倾斜：15.3 GB/s，是huf0_x2的 5.9 倍。
• proba50/proba14：9.2 / 5.2 GB/s，3.6 倍 / 2.1 倍。
• flat_M*完全平坦：20–24 GB/s，4.1–4.8 倍。
• english/prose_pride/html_wiki/chinese_text真实文本：4.3–4.8 GB/s，是huf0_x2的 2.0–2.5 倍。
• gzip_random/image_jpeg高熵：4.1–4.9 GB/s，2.7–3.2 倍。

PHA（PH + 每节点 FSE/ANS 编码的分区位图）以部分解码带宽换取倾斜数据上更好的压缩率（M4 数据；huf0/oo-huff产生相同的 Huffman 压缩率）：

• proba80：压缩率 8.45 倍 vshuf0/oo-huff的 6.40 倍（+32%）；解码 5.9 GB/s，仍是huf0_x2的 2.2 倍。
• calgary_pic（真实的 proba80 形态 1bpp 扫描页）：压缩率 6.13 倍 vs 4.79 倍（+28%）；解码 6.4 GB/s，是huf0_x2的 2.6 倍。
• 中等熵 / 真实文本分布（english、prose_pride、html_wiki、image_jpeg）：当分区位图不倾斜时，FSE 门控不会触发，因此 PHA 的压缩率在普通 Huffman 的 ±1% 以内。PHA 是压缩率的安全默认选择，PH 是峰值解码带宽的选择。

跨 ISA 峰值倍率随 SIMD 原语宽度扩展：Xeon AVX-512 1.43–13.8 倍 · Apple M4 NEON 1.43–10.7 倍 · Graviton 4 NEON 1.29–8.59 倍 · Zen 3 SSE/AVX2 0.94–22.5 倍（三行深层真实文本在 Zen 3 上落后约 6%）。

编码大小在传统 Huffman 的 1–4% 以内。

每主机表格、方法以及整个基准测试网格的观察结果在docs/BENCHMARKS.md中。

什么是 PIVCO-Huffman？

PIVCO-Huffman 将 PIVoted COding（枢轴编码）方法应用于 Huffman。PIVCO 不是通过表查找一次解码一个符号，而是同时处理整个 N 个符号的块，使用两种互补策略中更适合每个 Huffman 子树形态的那一种：

• SIMD 树遍历分区，用于混合深度子树，它根据每个内部节点的位图拆分块的索引集并递归；
• 平坦子树快速路径，用于所有叶子都位于相同相对深度的子树，它用每个元素一个打包的 D 位码和底部一次直接的code_to_sym[code]查找来替代一系列逐层位图。

检测和分派在pivco_huffman_build_table时发生一次——编码器遍历树并标记每个最大平坦子树（local_min_depth == local_max_depth >= 2），为每个平坦子树预计算code_to_sym，编码器和解码器都查询这些标志以在每个节点选择正确的路径。

完整的算法描述、动机和分析在论文中。给好奇读者的指引：

• 线格式 —docs/DATA_FORMAT.md和src/pivco_huffman_wire.h。
• SIMD 内核走查 —docs/KERNELS.md（NEONpartition_8、tree_merge、flat_dN_unpack及示例）。
• 每个原语的微基准成本 —docs/KEY-PRIMITIVES.md。
• 性能分析笔记（历史） —docs/PROFILING.md。
• 块大小扫描 —docs/BLOCK_SIZE.md。
• 相关工作 + 小波树联系 —docs/RELATED-WORK.md和docs/WAVELET_TREES.md。
• 测试数据集 —extras/datasets/（合成 + 真实世界分布）。
• 优化想法日志 —IDEAS.md（已发布 / 已丢弃 / 开放，含周期级分析）。

基线

基准测试网格将 PIVCO-Huffman 解码与我们认为是业界最先进的两种生产级 Huffman 解码器进行比较：

• huf0—cyan4973/FiniteStateEntropy，zstd 中的 Huffman 解码器。4 流交错，11 位主表（X1）或 11+5 位双查找（X2）。原版自动分派是默认的头条基线。
• oo-huff— Oodle 的newlz_arrays_huff（RAD 发布的 OodleUE 源码），6 流手工调优 ASM。被认为是 Huffman 解码的绝对 SotA。当 Oodle SDK 符号链接在ext/oodle时链接到bench/bench_fair.c。

较旧的遗留基线（树内trad_1s/trad_4s4 流参考解码器）已从头条表格中退役。ph是与人们实际发布的两种编解码器进行对比定位的。

构建与测试

# 前置条件（仅首次）gitsubmodule update--initext/fse# FSE 熵编码器（PHA 必需）# 构建cmake-Bbuild-DCMAKE_BUILD_TYPE=Release cmake--buildbuild# 测试./build/pivco_huffman_tests# 基准测试（参数 = 每次运行的重复次数，默认 100）./build/pivco_huffman_bench20# 快速./build/pivco_huffman_bench100# 彻底

在你自己的数据上试用

PIVCO-Huffman 可作为库使用——你不必采用我们的文件格式来测量它。三种方式，从最简单开始：

CLI—pivcohuf压缩文件并打印大小 / 压缩率 / 时间 / 带宽：

./build/pivcohuf c yourfile# PH -> yourfile.ph./build/pivcohuf c-ayourfile# PHA （ANS 编码位图；倾斜数据上压缩率更好）./build/pivcohuf d yourfile.ph# 解压（自动检测 PH vs PHA）

示例—examples/try.c（CMake 目标pivco_try）用 PH 和 PHA 压缩一个文件并报告压缩率 + 编码/解码吞吐量：

./build/pivco_try yourfile# yourfile (2000000 bytes) [ratio = in/out, higher = better]# ph 6.28x (2000000 -> 318379) enc 704 MB/s dec 5405 MB/s roundtrip ok# pha 8.44x (2000000 -> 236833) enc 495 MB/s dec 3578 MB/s roundtrip ok

库— 链接libpivco_huffman.a并调用include/pivcohuf_file.h中的缓冲区 API（无需了解线格式）：

#include"pivcohuf_file.h"size_tcap=pivcohuf_compress_bound(in_len);uint8_t*out=malloc(cap);size_tout_len=cap;pivcohuf_compress_ex(in,in_len,out,&out_len,/*use_ans=*/1);// PHA; 0 = PHsize_tusz;pivcohuf_peek_uncompressed_size(out,out_len,&usz);uint8_t*dec=malloc(usz);size_tdlen=usz;pivcohuf_decompress(out,out_len,dec,&dlen);// 自动检测 PH/PHA

要将编解码器嵌入你自己的容器/帧格式，请使用include/pivco_huffman.h中的块原语（先pivco_huffman_build_table，然后对PIVCO_BLOCK_SIZE符号块调用pivco_huffman_encode/pivco_huffman_decode；为 PHA 调用pivco_huffman_set_fse_enabled(1)）。

编译时自定义块大小：

cmake-Bbuild-DCMAKE_BUILD_TYPE=Release\-DCMAKE_C_FLAGS="-DPIVCO_BLOCK_SIZE=16384"

与 zstd / FSE 一起链接—libpivco_huffman.a内置了 FiniteStateEntropy（FSE_*/HUF_*/HIST_*/g_debuglevel），因此将其链接到任何也内置 FSE 的东西（zstd、lz4 的熵层……）旁边会遇到重复符号错误。对于这种情况，构建会生成一个可直接替换的可重定位对象build/libpivco_huffman_local.o，其中这些符号被本地化，而 pivco 的公共pivco_*/pivcohuf_*API 保持全局——链接它而不是.a，冲突就消失了：

cmake--buildbuild--targetpivco_huffman_local# 默认也会构建cc your_app.c build/libpivco_huffman_local.o-Iinclude-oyour_app

例如extras/phaz就是这样链接的。

交互式树可视化

figures/tree_viz.html是一个自包含的 HTML/JS 探索器，用于查看 Huffman 树并叠加平坦子树快速路径。它从figures/tree_viz_data.js加载 29 个基准分布（由./build/pivco_dump_distributions > figures/tree_viz_data.js重新生成），接受文件/文本上传，并允许你切换平坦子树检测、点击平坦根来（取消）扁平化以进行 ops/leaf 和链式规则熵总计的假设分析，以及拖动最大码长滑块。直接在浏览器中打开该文件——无需构建服务器。