A New Class of the Universal Representation for the Positive Integers

A new class of the universal representation for the positive integers is proposed. The positive integers are divided into infinite groups, and each positive integer $n$ is represented by a pair of integers $(p,q)$, which means that $n$ is the $q$-th number in the $p$-th group. It is shown that the new class includes the message length strategy as a special case, and the asymptotically optimal representation can easily be realized. Furthermore, a new asymptotically and practically efficient representation scheme is proposed, which preserves the numerical, lexicographical, and length orders.
Key words: universal code, universal representation of the positive integers, message length strategy, grouping strategy

東京大学 大学院新領域創成科学研究科 複雑理工学専攻