Bounds of compression of unknown alphabets
Alon Orlitsky, Narayana Santhanam, J. Zhang · 2003
It is known that the redundancy of universally compressing i.i.d. strings increases to infinity as the alphabet size grows. It is also apparent that any string can be described by separately conveying its symbols, and their pattern-the order in which they appear. Concentrating on the latter, we show that the patterns of iid strings drawn from any, possibly infinite or even unknown, alphabet, can be universally compressed with diminishing worst-case redundancy, both in block, and sequentially.