PivCo-Huffman

# PivCo-Huffman 来源：https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html Marcin Żukowski *v\.1\.0，2026\-06\-04* ## 摘要 霍夫曼编码是一项**经久不衰**的技术，自发明以来已有70多年历史，在压缩算法中无处不在。本文提出了一种基于**小波树**数据结构的新霍夫曼编码方法。由此产生的**枢轴编码霍夫曼**（**PivCo-Huffman**）实现了高性能、适合 SIMD 的编码和解码操作。在我们的测试中，PivCo-Huffman 在解码吞吐量上持续优于最先进的霍夫曼编解码器。此外，我们还展示了如何将 ANS 编码**有选择地**应用于此结构中的**偏斜**节点，从而在保持非常高解压速度的同时，获得接近基于 ANS 的编解码器的压缩比。 本文基本上是 arXiv:2606.05765 (https://arxiv.org/abs/2606.05765) 论文的逐字副本。但在像这样的方框中，你会看到一些额外的作者思考，这些内容可能不适合放入“官方”科学论文。此 HTML 版本还提供了一些不错的**体验增强**功能： - 点击树形图可将读者引导至可视化工具 - SIMD 代码通过 simd.dev (https://simd.dev/) 提供了内部函数工具提示，例如 `vqtbl2\_u8` - 右侧有活动的目录 - 评论！(https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#comments) ## 目录 1. 摘要 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-1) 2. 1. 引言 1. 1\.1\. 经典霍夫曼树 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-8) 2. 1\.2\. 现代霍夫曼解决方案 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#sota) 3. 1\.3\. 动机示例：数据库中的哈希连接 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#hj) 3. 2. 枢轴化霍夫曼 1. 2\.1\. 朴素实现 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#naive) 2. 2\.2\. 树优化 1. 2\.2\.1\. 合并叶节点 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-18) 2. 2\.2\.2\. 频繁符号优化 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-19) 3. 2\.2\.3\. 扁平子树 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-20) 4. 2\.2\.4\. 非规范子树 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-21) 3. 2\.3\. 树优化的影响 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-22) 4. 2\.4\. 原语 1. 2\.4\.1\. `partition` (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-24) 2. 2\.4\.2\. `scatter` 原语 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#scatter) 5. 2\.5\. 结果 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-25) 4. 3. 自底向上 PivCo-Huffman 1. 3\.1\. 自底向上的树优化 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-27) 2. 3\.2\. 自底向上的树操作 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-28) 3. 3\.3\. 自底向上原语性能 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-29) 4. 3\.4\. 自底向上解码性能 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-30) 5. 4. 编码 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#encoding) 6. 5. PivCo-Huffman + ANS 1. 5\.1\. 霍夫曼树中的偏斜分析 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-33) 2. 5\.2\. PivCo-Huffman+ANS 实现 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-34) 3. 5\.3\. 优势 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-35) 4. 5\.4\. 结果 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-36) 7. 6. 讨论 1. 6\.1\. 数据规模 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-39) 2. 6\.2\. SIMD 聚焦 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-40) 3. 6\.3\. 原语优化 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-41) 4. 6\.4\. 探索位图压缩替代方案 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-42) 5. 6\.5\. 对 LZ 编解码器的影响 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-43) 6. 6\.6\. CPU 发展趋势 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-44) 8. 7. 相关工作 1. 7\.1\. 熵编码 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#entropy) 2. 7\.2\. 小波树 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#wt) 3. 7\.3\. 位打包 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#bitpack) 9. 8. 结论 1. 8\.1\. AI 披露 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-59) 2. 8\.2\. 致谢 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-60) 10. 参考文献 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-61) 11. 附录 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-92) 12. A 数据集 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#datasets) 13. B 测试机器 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#machines) 14. C 测试方法论 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#testing-method) 15. D 压缩数据组织 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#wire) 16. E 更多 PivCo-Huffman 优化 1. E\.1 根层解码 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-94) 2. E\.2 融合 `scatter` 和 `partition` (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-95) 3. E\.3 针对 FSE 的树优化 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-96) 4. E\.4 将 FSE 与 `merge` 融合 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#fuse-fse-merge) 17. F 调优 FSE (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#tuning-fse) 18. G PivCo-Golomb (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#app-golomb) ## 1\. 引言 霍夫曼编码[\[1\]](https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-62)是压缩领域最重要的算法之一。Moffat 和 Turpin 在[\[2\]](https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-63)中描述得非常恰当——它非常**经久不衰**：尽管出现了压缩效果更好的编码（例如[\[3\]](https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-64)或[\[4\]](https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-65)），但70多年后它仍然无处不在。 注意：形式上，大多数现代系统不一定使用[\[1\]](https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-62)中提出的**确切**编码，而是使用来自[\[5\]](https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-66)的“规范”编码。 ### 1\.1\. 经典霍夫曼树 [](https://marcinzukowski.github.io/pivco-huffman/paper-1.0/figures/fig-web.html?name=huf-tree) 图 1：单词“huffman”的经典霍夫曼树 `` node = root while not is_leaf(node) if read_bit() == 1: node = node->right else: node = node->left return node.symbol `` 清单 1：单个符号的朴素霍夫曼解码 在经典霍夫曼编码中，每个符号使用一个代码（一个比特序列）进行编码，较频繁的符号获得较短的代码。图 1 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#fig-huf-tree) 展示了单词“huffman”的霍夫曼树，清单 1 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#fig-huf-decode) 展示了解码一个符号的朴素算法。例如，要解码符号 **`"h"`**，我们使用比特 **`"1 0 1"`** 遍历树，到达代表该符号的适当叶节点。 ### 1\.2\. 现代霍夫曼解决方案 清单 1 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#fig-huf-decode) 中的实现性能不高，因为它使用了大量操作，并且对现代 CPU 不友好。相反，现代霍夫曼解码实现使用**解码表**，允许解码整个符号而无需逐位遍历其代码。支持的代码长度通常受到约束，例如限制为*L=11*位。然后创建大小为*2^L*的表，从而实现以下实现： `` code_bits = peek_bits(L); emit_symbol(decoding_table[code_bits].symbol); skip_bits(decoding_table[code_bits].numBits); `` 这类代码可以通过使用多个游标 ([\[6\]](https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-67)，[\[7\]](https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-68))，或者通过构建一个在一次迭代中解码两个符号而非一个符号的表来进一步加速。我们测量了各种霍夫曼解码实现，发现性能最高的解决方案是： - **Huff0** —— 开源 FSE ([\[8\]](https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-69)) 库的一部分，也是流行 zstd 压缩库 ([\[9\]](https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-70)) 的构建模块。纯 C 实现，许可宽松。 - **Oodle Huffman** —— 来自 Oodle ([\[10\]](https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-71)) 的霍夫曼解码器，这是 RAD Game Tools 的专有压缩库。使用 C 实现并包含大量汇编优化。Oodle 在大多数用途下需要许可证。 以下是两个主机上两个示例数据集的测量带宽（更多信息请参见附录 C (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#testing-method)）： **数据集** | **主机** | **Huff0** | | **Oodle Huffman** | | | | | 编码 MB/s | 解码 MB/s | 编码 MB/s | 解码 MB/s | proba80M | M4 | 1334 | 2929 | 1740 | 3343 | | c8i | 1471 | 936 | 1295 | 2131 prose\_pride | M4 | 1722 | 2547 | 2325 | 3158 | | c8i | 1267 | 1758 | 1364 | 2120 这些是令人印象深刻的结果。尽管如此，在本文中我们研究是否可以通过使用一种完全不同的方法进一步提高性能。 ### 1\.3\. 动机示例：数据库中的哈希连接 哈希表查找是许多系统中性能最密集的操作之一，包括数据库。下面我们可以看到简单线性哈希查找的伪代码： `` hash = compute_hash(key) pos = hash_table_first(hash) while not hash_table_empty(pos) val = hash_table_value(pos) if val == key: return true pos = hash_table_next(pos) return false `` 与清单 1 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#fig-huf-decode) 中的霍夫曼解码一样，这个问题可以被看作是一个状态机遍历。在这两种情况下，循环中的数据依赖和不可预测的分支阻止了 CPU 实现高性能。哈希连接还会执行昂贵的内存查找，导致额外的停顿。 [\[11\]](https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-72)（第5.3.3.2节）提出了一种替代的哈希表查找方法，其基础不是为单个记录遍历状态机中的每个节点，而是为**一组向量**的记录遍历，如下面的伪代码所示： `` misses = [] // 未命中的输入位置 hits = [] // 命中的输入位置 hash = compute_hash(keys) // 所有输入的哈希值 active = hash_table_first(hash) // 我们仍在查找的输入位置 while not active.empty(): // 如果我们还有工作要做 // 将空槽位移到 misses，减少 active hash_table_split_empty(&active, &misses) // 获取 active 索引的所有哈希表值 vals = hash_table_vals(active) // 计算比较 comp_results = compare(vals, keys, active) // 如果相等则拆分为 hits，否则为 active——那些需要更多工作 split_on_equality(comp_results, &active, &hits) // 获取所有仍活跃记录的下一个位置 active = hash_table_next(active) // misses 包含所有未命中的位置，hits 包含所有命中的位置 `` 这种方法虽然更复杂且看似更费力（肯定发出更多 CPU 指令），但在每个阶段向 CPU 暴露了大量简单、独立的操作，避免了任何数据或控制依赖，并允许重叠内存访问。结果，它相对于**标量**方法实现了显著的性能优势（甚至超过10倍）。 所以我一直在尝试将这种通用方法应用于几个不同的问题，包括压缩，也涉及正则表达式处理之类的事。在 VarInt 上取得了一些不错的结果，但后来我看到了 Daniel Lemire 的 Stream VByte[\[12\]](https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-73) 就放弃了——无法超越。幸运的是，对于霍夫曼，这种方法似乎“契合”得相当好。 ## 2\. 枢轴化霍夫曼 按照第 1.3 节 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#hj) 中的例子，应该可以使用类似的原理创建霍夫曼解码器。然而，为了使霍夫曼树中的每个节点都能访问到流中的相关比特，需要一种不同的数据布局。我们在**小波树**结构[\[13\]](https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-74)中找到了一个很好的解决方案。 [](https://marcinzukowski.github.io/pivco-huffman/paper-1.0/figures/fig-web.html?name=pivot-bitmaps) 图 2：枢轴化霍夫曼编码字符串的示例。所有共享相同前缀（引号内注明）的比特被分组在一起成为一个位图。用颜色编码的字母加下标表示哪个字母的哪个比特位置。 **\*** 标记代码终止位。 [](https://marcinzukowski.github.io/pivco-huffman/paper-1.0/figures/fig-web.html?name=pivot-tree) 图 3：使用“枢轴化”数据遍历它的霍夫曼树示例，重复使用前面的示例。每个节点为其符号生成一个索引列表。 图 2 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#fig-pivot) 展示了编码单词“huffman”的另一种表示。不是代码接代码的流，我们根据（可能为空的）前缀将所有流的比特进行划分。图 3 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#fig-pivot-tree) 展示了在解码数据时这种布局如何映射到霍夫曼树上。每个节点接收所有通过它的代码的比特，并将这些代码引导至其子节点，在那里使用另一个位图进行下一步。 请注意，虽然逻辑上这种表示包含与标准霍夫曼编码相同的信息，但它通常按字节对齐存储位图。由于字节填充，这可能导致**略微更差**的压缩比。然而，对于非平凡数据集，如果这种方法能提供其他好处，这种开销是可以接受的。 这种数据表示和树遍历是本论文中提出的***枢轴编码霍夫曼*（PivCo-Huffman）**的基础。在本节中，我们介绍这种方法的*初始*实现，它实际上*并未*用于最终解决方案。尽管如此，由于它是一种更*自然*的方法，我们首先描述它，并利用它引入一组优化和实现技术。在第 3 节 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#bottom-up) 中，我们将提出最终的、性能更高的解决方案。 如前所述，所使用的树表示等价于**小波树**，具体来说是**霍夫曼形状的小波树**（例如[\[14\]](https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#loc-75)）。但我们将 PivCo-Huffman 视为一个相关但独立的解决方案——更多讨论请参见第 7.2 节 (https://marcinzukowski.github.io/pivco-huffman/paper-1.0/ph.html#wt)。 在 PivCo-Huffman 的工作过程中，我做了大量文献调研，很长一段时间没有找到类似的东西。接近研究/实验工作结束时，Claude 找到了小波树。一开始我恐慌了（几周的生命白费了？），但更深入的审查表明……