Huffman coding is one of the oldest and most fundamental problems in computer science. Given a string of length $n$ over an arbitrary alphabet, the task is to assign a binary codeword to each character so that no codeword is a prefix of another and the total encoded length is minimized. The technique is widely used in practical compression systems such as file compression. As datasets keep growing, it is natural to ask whether a Huffman code can be built efficiently in the massively parallel computation (MPC) model. The classic Huffman algorithm admits two straightforward MPC implementations: for any constant $0<\epsilon<1$, one uses $O(n^{\epsilon})$ memory per machine but requires $\Theta(\log n)$ rounds, while the other runs in $O(1)$ rounds at the cost of $\Theta(\sqrt{n})$ memory per machine. We present the first non‑trivial MPC algorithm that bypasses both limitations. For every constant $\epsilon>0$, our algorithm finishes in $O_{\epsilon}(\log\log n)$ rounds and needs $\tilde O(n^{\epsilon})$ memory per machine, while the total memory and total computation are $\tilde O(n)$. Although the framework is tailored to the MPC model, it also applies to the PRAM setting, yielding near‑linear total work. In particular, when the text length satisfies $n \le 2^{O\bigl((\frac{\log \sigma}{\log\log \sigma})^2\bigr)}$ (with $\sigma$ the alphabet size), the parallel running time improves over all previously known PRAM algorithms and is essentially optimal.
Review