Universal compression of unknown alphabets
Nikola Jevtić, Alon Orlitsky, Narayana Santhanam · 2003
We consider universal compression of strings where the symbols are drawn independently according to the same unknown distribution over an unknown alphabet. We show that the order of the symbols can be conveyed using essentially as many bits as needed when the distribution is known in advance.