The Construction of Near-optimal Universal Coding of Integers

Universal Coding of Integers (UCI) is suitable for discrete memoryless sources with unknown probability distributions and infinitely countable alphabet sizes. The UCI is a class of prefix codes, such that the ratio of the average codeword length to max\1, H(P)\ is within a constant expansion factor KC for any decreasing probability distribution P, where $H(P)$ is the entropy of P. For any UCI code C, define the minimum expansion factor KC* to represent the infimum of the set of extension factors of C. Each C has a unique corresponding KC*, and the smaller KC* is, the better the compression performance of C is. A class of UCI C (or family ᵢ\ᵢ₌₁∞) achieving the smallest KC* is defined as the optimal UCI. The best result currently is that the range of CC* for the optimal UCI is 2≤ CC*≤ 2.5. In this paper, we prove that there exists a class of near-optimal UCIs, called $ν$ code, to achieve K_ν=2.0386. This narrows the range of the minimum expansion factor for optimal UCI to 2≤ CC*≤ 2.0386. Another new class of UCI, called $Δδ$ code, is specifically constructed. We show that the $Δδ$ code and $ν$ code are currently optimal in terms of minimum expansion factor. In addition, we propose a new proof that shows the minimum expansion factor of the optimal UCI is lower bounded by $2$.