The Construction of Near-Optimal Universal Coding of Integers

The Universal Coding of Integers (UCI) is suitable for discrete memoryless sources with unknown probability distributions and infinitely countable alphabet sizes. A UCI is a class of prefix codes for which the ratio of the average codeword length to max{1,H(P)} is within a constant expansion factorCCfor any decreasing probability distributionP, whereH(P)is the entropy ofP. For any UCI codeC, the minimum expansion factor C∗Cis defined to represent the infimum of the set of extension factors ofC. EachChas a unique correspondingC∗C, and the smallerC∗Cis, the better the compression performance ofCis. The class of UCIsC(or a family {Ci}∞i=1) that achieves the smallestC∗Cis defined as theoptimal UCI. The best current result is that the range ofC∗Cfor the optimal UCI is 2 ≤C∗C≤ 2.5. In this paper, we prove a tighter probability inequality for decreasing distributions, which serves as a new tool for studying the properties of UCIs. On the basis of this inequality, we prove that there exists a class of near-optimal UCIs, called the ν code, achievingCν= 2.0386. This narrows the range of the minimum expansion factor for the optimal UCI to 2 ≤C∗C≤ 2.0386. We show that the ν code is currently optimal in terms of the minimum expansion factor. In addition, we propose a new proof showing that the minimum expansion factor of the optimal UCI is lower bounded by 2.