论文标题
整数的通用通用编码
Generalized Universal Coding of Integers
论文作者
论文摘要
整数〜（UCI）的通用编码是一类可变长度代码，因此，预期的代码字长度与$ \ max \ {1，h（p）\} $的比率在恒定因素之内，其中$ h（p）$是减少概率分布$ p $ p $的shannon entropy。但是，如果我们考虑预期的代码字长度与$ h（p）$的比率，那么当$ h（p）$趋于零时，该比率倾向于使用UCI。为了解决此问题，本文介绍了一类代码，称为整数〜（GUCI）的通用通用编码，因此，预期的代码文长与$ h（p）$的比率在恒定的因子$ k $之内。首先，提出了GUCI的定义，并引入了GUCI的编码结构。接下来，我们提出一类Guci $ \ Mathcal {C} $，以实现扩展因子$ k _ {\ MathCal {c}}} = 2 $，并证明最佳GUCI在范围内$ 1 \ leq k _ {\ Mathcal {\ Mathcal {C}}}}}^{*}^{*} \ leq leq 2 $。然后，通过比较UCI和GUCI，我们表明，当熵很大或$ p（0）$不大时，在某些情况下，Guci的平均编码长度较短。最后，提出了渐近最佳的GUCI。
Universal coding of integers~(UCI) is a class of variable-length code, such that the ratio of the expected codeword length to $\max\{1,H(P)\}$ is within a constant factor, where $H(P)$ is the Shannon entropy of the decreasing probability distribution $P$. However, if we consider the ratio of the expected codeword length to $H(P)$, the ratio tends to infinity by using UCI, when $H(P)$ tends to zero. To solve this issue, this paper introduces a class of codes, termed generalized universal coding of integers~(GUCI), such that the ratio of the expected codeword length to $H(P)$ is within a constant factor $K$. First, the definition of GUCI is proposed and the coding structure of GUCI is introduced. Next, we propose a class of GUCI $\mathcal{C}$ to achieve the expansion factor $K_{\mathcal{C}}=2$ and show that the optimal GUCI is in the range $1\leq K_{\mathcal{C}}^{*}\leq 2$. Then, by comparing UCI and GUCI, we show that when the entropy is very large or $P(0)$ is not large, there are also cases where the average codeword length of GUCI is shorter. Finally, the asymptotically optimal GUCI is presented.
