A Self-contained Analysis of the Lempel-Ziv Compression Algorithm

2019/10/02 by Sudan, Madhu, Xiang, David
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.1910.00941

Abstract

This article gives a self-contained analysis of the performance of the Lempel-Ziv compression algorithm on (hidden) Markovian sources. Specifically we include a full proof of the assertion that the compression rate approaches the entropy rate of the chain being compressed.

Related

• Lempel-Ziv Complexity, Empirical Entropies, and Chain Rules
• Lossy Compression in Near-Linear Time via Efficient Random Codebooks and Databases
• Optimal Universal Lossless Compression with Side Information
• Distributed compression through the lens of algorithmic information theory: a primer
• LDPC-Based Iterative Algorithm for Compression of Correlated Sources at Rates Approaching the Slepian-Wolf Bound