Huffman 编码是计算机科学中最古老且最基础的问题之一。给定长度为 $n$ 的字符串，字符来自任意字母表，需要为每个字符分配二进制码字，使得没有码字是另一个的前缀，并且编码后的总长度最小。该技术在文件压缩等实际系统中被广泛使用。随着数据规模的不断扩大，研究在大规模并行计算（\MPC）模型下高效构造 Huffman 编码显得尤为重要。传统的 Huffman 算法可以直接在 \MPC 中实现两种方式：一种在每台机器使用 $O(n^{\epsilon})$ 内存（其中 $0<\epsilon<1$ 为常数）但需要 $\Theta(\log n)$ 轮；另一种在 $O(1)$ 轮内完成，却需要每台机器 $\Theta(\sqrt{n})$ 内存。我们提出了首个突破这两种限制的非平凡 \MPC 算法。对于任意常数 $\epsilon>0$，该算法在 $O_{\epsilon}(\log\log n)$ 轮内完成，并且每台机器只需 $\tilde O(n^{\epsilon})$ 内存，同时整体内存和计算量均为 $\tilde O(n)$。虽然我们的框架专为 \MPC 设计，但同样适用于 \PRAM 模型，并能实现接近线性的总工作量。当文本长度 $n \le 2^{O\bigl((\frac{\log \sigma}{\log\log \sigma})^2\bigr)}$（其中 $\sigma$ 为字母表大小）时，得到的并行运行时间优于所有已知的 \PRAM 算法，并且基本达到最优。
点评