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 \1, H (P) \ is within a constant expansion factor K₂ for any decreasing probability distribution P, where H (P) is the entropy of P. For any UCI code C, define the minimum expansion factor K₂^* to represent the infimum of the set of extension factors of C. Each C has a unique corresponding K₂^*, and the smaller K₂^* is, the better the compression performance of C is. A class of UCI C (or family \Cᵢ\₈=₁^) achieving the smallest K₂^* is defined as the optimal UCI. The best result currently is that the range of C₂^* for the optimal UCI is 2 C₂^* 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 C₂^* 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.