The redundancy and distribution of the phrase lengths of the fixed-database Lempel-Ziv algorithm

The fixed-database version of the Lempel-Ziv algorithm closely resembles many versions that appear in practice. We ascertain several key asymptotic properties of the algorithm as applied to sources with finite memory. First, we determine that for a dictionary of size n, the algorithm achieves a redu...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 1997-09, Vol.43 (5), p.1452-1464
Main Author: Wyner, A.J.
Format: Article
Language:English
Subjects:
Algorithms
Computer memory
Computer programming
Data compression
Dictionaries
Encoding
Entropy
Information theory
Loss measurement
Mathematical models
Random sequences
Statistics
Studies
Upper bound
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The fixed-database version of the Lempel-Ziv algorithm closely resembles many versions that appear in practice. We ascertain several key asymptotic properties of the algorithm as applied to sources with finite memory. First, we determine that for a dictionary of size n, the algorithm achieves a redundancy /spl rho//sub n/=Hlog log n/log n+0(log log n/log n) where H is the entropy of the process. This is the first, nontrivial, lower bound on any Lempel-Ziv-type compression scheme. We then find the limiting distribution and all moments of the lengths of the phrases by comparing them to a random-walk-like variable with well-known behavior.
ISSN:0018-9448
1557-9654
DOI:10.1109/18.623144