Optimal Universal Lossless Compression with Side Information

Yeohee Im; Sergio Verdu

doi:10.1109/TIT.2018.2868053

Optimal Universal Lossless Compression with Side Information

Yeohee Im, Sergio Verdu

Research output: Contribution to journal › Article › peer-review

Abstract

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 language	English (US)
Journal	IEEE Transactions on Information Theory
DOIs	https://doi.org/10.1109/TIT.2018.2868053
State	Accepted/In press - Aug 30 2018

All Science Journal Classification (ASJC) codes

Information Systems
Computer Science Applications
Library and Information Sciences

Keywords

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

Access to Document

10.1109/TIT.2018.2868053

Cite this

@article{0c5cb1a6fa364515a5f7117fdd3c4be4,

title = "Optimal Universal Lossless Compression with Side Information",

abstract = "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.",

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

author = "Yeohee Im and Sergio Verdu",

note = "Publisher Copyright: IEEE",

year = "2018",

month = aug,

day = "30",

doi = "10.1109/TIT.2018.2868053",

language = "English (US)",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - JOUR

T1 - Optimal Universal Lossless Compression with Side Information

AU - Im, Yeohee

AU - Verdu, Sergio

N1 - Publisher Copyright: IEEE

PY - 2018/8/30

Y1 - 2018/8/30

N2 - 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.

AB - 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.

KW - Bioinformatics

KW - Data compression

KW - Encoding

KW - Image coding

KW - Indexes

KW - Lempel-Ziv coding

KW - Microsoft Windows

KW - Silicon

KW - Universal lossless compression

KW - compression with side information

KW - repeated recurrence time

UR - http://www.scopus.com/inward/record.url?scp=85052824457&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85052824457&partnerID=8YFLogxK

U2 - 10.1109/TIT.2018.2868053

DO - 10.1109/TIT.2018.2868053

M3 - Article

AN - SCOPUS:85052824457

SN - 0018-9448

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

ER -

Optimal Universal Lossless Compression with Side Information

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this