Bounds on compression of unknown alphabets

A. Orlitsky, N. P. Santhanam, J. Zhang

Research output: Contribution to journalConference articlepeer-review

4 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)111
Number of pages1
JournalIEEE International Symposium on Information Theory - Proceedings
StatePublished - 2003
Externally publishedYes
EventProceedings 2003 IEEE International Symposium on Information Theory (ISIT) - Yokohama, Japan
Duration: Jun 29 2003Jul 4 2003

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics


Dive into the research topics of 'Bounds on compression of unknown alphabets'. Together they form a unique fingerprint.

Cite this