Performance of universal codes over infinite alphabets
Alon Orlitsky, Narayana Santhanam · 2003
It was known that universal compression of strings generated by independent and identically distributed sources over infinite alphabets entails infinite per-symbol redundancy. Alternative compression schemes, which decompose the description of such strings into a description of the symbols appearing in the string, and a description of the arrangement of the symbols form were presented. Two descriptions of the symbol arrangement were considered: shapes and patterns. Roughly speaking, shapes describe the relative magnitude of the symbols while patterns describe only the order in which they appear. The per-symbol worst-case redundancy of compressing shapes is a positive constant less than one, and the per-symbol redundancy of compressing patterns diminishes to zero as the block-length increases were proven. Some results on sequential pattern compression were also mentioned.