论文标题
加权自适应编码
Weighted Adaptive Coding
论文作者
论文摘要
霍夫曼编码是最佳的，但其动态版本在实践中可能更有效。最近提出了一种新的Huffman编码版本，证明其性能比至少$ M-1 $位的静态Huffman编码更好，其中$ m $表示字母的大小，并且比标准的动态huffman编码更好。本文引入了一种新的通用编码方法，扩展了已知的静态和动态变体，并将其作为特殊情况。实际上，概括适用于所有统计方法，包括算术编码。然后，这导致了一种新的自适应编码方法的形式化，该方法至少与迄今已知的最佳动态变体一样好。此外，我们提出的经验结果表明，即使编码文件包含模型描述，也可以通过提出的方法进行的静态和动态霍夫曼和算术编码进行改进。
Huffman coding is known to be optimal, yet its dynamic version may be even more efficient in practice. A new variant of Huffman encoding has been proposed recently, that provably always performs better than static Huffman coding by at least $m-1$ bits, where $m$ denotes the size of the alphabet, and has a better worst case than the standard dynamic Huffman coding. This paper introduces a new generic coding method, extending the known static and dynamic variants and including them as special cases. In fact, the generalization is applicable to all statistical methods, including arithmetic coding. This leads then to the formalization of a new adaptive coding method, which is provably always at least as good as the best dynamic variant known to date. Moreover, we present empirical results that show improvements over static and dynamic Huffman and arithmetic coding achieved by the proposed method, even when the encoded file includes the model description.
