On universal codes for integers: Wallace Tree, Elias Omega and beyond

LA home
 DCC 2021

also see

Lloyd Allison, Arun S. Konagurthu and Daniel F. Schmidt

Data Compression Conference (DCC), pp.313-322, 22-26 March 2021

Abstract: A universal code for the (positive) integers is a variable length code that can be used to store or compress a sequence of integers. It also implies a probability distribution on integers which can be a natural choice when the true distribution of a source of integers is unknown; such a code and distribution may be useful in statistical inference. This paper provides two improvements to the theory and practice of universal codes. First, it defines and examines a new universal code omega* (omega-star) that asymptotically beats the Elias omega code. Second, it analyses the properties of a code proposed by Wallace based on trees, and shows it to be a universal code, to have desirable properties for use in inference, and to beat the Elias omega code on almost all integers up to the 1697-bit code-word mark. Encoding and decoding routines for the codes described here are implemented and available for interactive use1.

Download at the IEEE [doi:10.1109/DCC50243.2021.00039], or here [paper.pdf].

[1] ← click.

www #ad:

↑ © L. Allison, www.allisons.org/ll/   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Tuesday, 21-Sep-2021 22:09:01 EDT.

Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.