Optimal Universal Lossless Compression with Side Information

Yeohee Im, Sergio Verdu

Research output: Contribution to journalArticlepeer-review


This paper presents conditional versions of the Lempel-Ziv (LZ) algorithm for settings where compressor and decompressor have access to the same side information. We propose a fixed-length-parsing LZ algorithm with side information, motivated by the Willems algorithm, and prove its optimality for any stationary processes. In addition, we suggest strategies to improve the algorithm which lower the non-asymptotic data compression rate. A modification of a variable-length-parsing LZ algorithm with side information is proposed and proved to be asymptotically optimal for stationary and ergodic processes.

Original languageEnglish (US)
JournalIEEE Transactions on Information Theory
StateAccepted/In press - Aug 30 2018

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


  • Bioinformatics
  • Data compression
  • Encoding
  • Image coding
  • Indexes
  • Lempel-Ziv coding
  • Microsoft Windows
  • Silicon
  • Universal lossless compression
  • compression with side information
  • repeated recurrence time


Dive into the research topics of 'Optimal Universal Lossless Compression with Side Information'. Together they form a unique fingerprint.

Cite this