compression - 压缩具有已知概率分布的符号的最佳熵编码方案是什么？

Question

我正在寻找在一长串通话记录中对 user_ids 进行编码。这些记录中占用空间最多的部分是调用者和接收者的符号。我将创建一个映射，为最活跃的调用者分配较短的符号——这将有助于降低文件的整体大小（以及 I/O 时间）。

我事先知道每个符号将被使用多少次——换句话说，我知道相对概率分布。此外，生成的代码是否“无前缀”（例如霍夫曼代码）并不重要。那么最好的编码方案是什么，即能够提供最多压缩并且存在快速实现的方案？

答案不仅应指向压缩方案，还应指向该编码方案的实现。

Answer 1

@conradlee：重新“在什么情况下算术编码比霍夫曼编码更好？” 在压缩方面，几乎总是如此。如果您有一个符号 S，其概率为 Ps，那么编码它的理想位数 bs 是 -log(Ps)/log(2)。例如，如果 Ps 为 1/3，则 bs 为 ~ 1.585 位。使用 Huffman，您必须向上或向下舍入到最接近的整数位数（因此压缩率会降低）。算术编码将用小数位数存储它。

Answer 2

对于具有已知概率分布的通用无损编码，除了霍夫曼编码之外，另一个“教科书”答案是算术编码。

在实践中，有多种实现方式。请参阅这些通用编码器。每个都有不同的属性。没有更多信息，我们无法给您更准确的答案。