Abstract
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 factor CC for any decreasing probability distribution P, where H(P) is the entropy of P. For any UCI code C, the minimum expansion factor C∗ C is defined to represent the infimum of the set of extension factors of C. Each C has a unique corresponding C∗ C, and the smaller C∗ C is, the better the compression performance of C is. The class of UCIs C (or a family {Ci}∞ i=1) that achieves the smallest C∗ C is defined as the optimal UCI. The best current result is that the range of C∗ C for 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, achieving Cν = 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.
Funding Information
  • National Natural Science Foundation of China (62401599)

This publication has 34 references indexed in Scilit: