标题： 保留长度前缀编码 显示英文标题

标题： Reserved-Length Prefix Coding

摘要： 霍夫曼编码为给定的概率质量函数找到最优前缀码。 考虑希望找到具有限制的最优码的情况，即所有码字的长度都位于用户指定的长度集合中（或等价地，没有码字的长度位于补集内）。 本文介绍了一种多项式时间动态规划算法，用于解决这种保留长度的前缀编码问题。 这在快速编码和解码无损码方面有应用。 此外，该方法的一个修改版本可以解决任何准算术前缀编码问题，而另一个则能找到受限于用户指定g个码字长度的最优码（例如，g=2）。 显示英文摘要

摘要： Huffman coding finds an optimal prefix code for a given probability mass function. Consider situations in which one wishes to find an optimal code with the restriction that all codewords have lengths that lie in a user-specified set of lengths (or, equivalently, no codewords have lengths that lie in a complementary set). This paper introduces a polynomial-time dynamic programming algorithm that finds optimal codes for this reserved-length prefix coding problem. This has applications to quickly encoding and decoding lossless codes. In addition, one modification of the approach solves any quasiarithmetic prefix coding problem, while another finds optimal codes restricted to the set of codes with g codeword lengths for user-specified g (e.g., g=2).