Relative entropy coding (REC) algorithms encode a random sample following a
target distribution $Q$, using a coding distribution $P$ shared between the
sender and receiver. Sadly, general REC algorithms suffer from prohibitive
encoding times, at least on the order of $2^{D_{\text{KL}}[Q||P]}$, and faster
algorithms are limited to very specific settings. This work addresses this
issue by introducing a REC scheme utilizing space partitioning to reduce
runtime in practical scenarios. We provide theoretical analyses of our method
and demonstrate its effectiveness with both toy examples and practical
applications. Notably, our method successfully handles REC tasks with
$D_{\text{KL}}[Q||P]$ about three times what previous methods can manage and
reduces the compression rate by approximately 5-15\% in VAE-based lossless
compression on MNIST and INR-based lossy compression on CIFAR-10 compared to
previous methods, significantly improving the practicality of REC for neural
compression.

使用空间分割减少运行时间的相对熵编码（REC）算法可成功处理具有三倍于先前方法的 KL 散度，并将压缩率与先前方法相比提高了约 5-15％，显著改善了神经压缩中的 REC 方法的实用性。