On the redundancy of the fixed-database Lempel-Ziv algorithm for phi-mixing sources

被引：16

作者：

Yang, EH ^{[1
]}

Kieffer, JC ^{[1
]}

机构：

[1] UNIV MINNESOTA, DEPT ELECT ENGN, MINNEAPOLIS, MN 55455 USA

来源：

IEEE TRANSACTIONS ON INFORMATION THEORY | 1997年 / 43卷 / 04期

基金：

美国国家科学基金会;

关键词：

data compression; fixed-database Lempel-Ziv algorithm; phi-mixing sources; Shannon entropy rate; variable-length to variable-length codes;

D O I：

10.1109/18.605570

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The redundancy problem of the fixed-database Lempel-Ziv algorithm is considered. It is demonstrated that for a class of phi-mixing sources which includes Markov sources, unifilar sources, and finite-state sources as special cases, the redundancy of the fixed-database Lempel-Ziv algorithm with database size n is lower-bounded by H(log log n)/log n + O((log log log n)/log n) and upper-bounded by 2H(log log n)/log n + O((log log log n)/log n) where H is the entropy rate of the source. The method of proof is new and uses the concept of variable-length to variable-length codes.

引用

页码：1101 / 1111

页数：11

共 17 条

[1]

Billingsley P., 2013, CONVERGE PROBAB MEAS

[2] ASYMPTOTICALLY MEAN STATIONARY MEASURES [J].

GRAY, RM ;

KIEFFER, JC .

ANNALS OF PROBABILITY, 1980, 8 (05) :962-973

[3] DISCRETE-TIME DETECTION IN PHI-MIXING NOISE [J].

HALVERSON, DR ;

WISE, GL .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1980, 26 (02) :189-198

[4] VARIABLE-LENGTH-TO-BLOCK CODING [J].

JELINEK, F ;

SCHNEIDER, KS .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1972, 18 (06) :765-+

[5] THE POINTWISE ERGODIC THEOREM FOR TRANSFORMATIONS WHOSE ORBITS CONTAIN OR ARE CONTAINED IN THE ORBITS OF A MEASURE-PRESERVING TRANSFORMATION [J].

KIEFFER, JC ;

RAHE, M .

CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, 1982, 34 (06) :1303-1318

[6] SAMPLE CONVERSES IN SOURCE-CODING THEORY [J].

KIEFFER, JC .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1991, 37 (02) :263-268

[7]

KIEFFER JC, 1980, P 18 ALL C COMM CONT, P438

[8] THE PERFORMANCE OF UNIVERSAL ENCODING [J].

KRICHEVSKY, RE ;

TROFIMOV, VK .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1981, 27 (02) :199-207

[9] On the average redundancy rate of the Lempel-Ziv code [J].

Louchard, G ;

Szpankowski, W .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1997, 43 (01) :2-8

[10] A GENERALIZED SUFFIX TREE AND ITS (UN)EXPECTED ASYMPTOTIC BEHAVIORS [J].

SZPANKOWSKI, W .

SIAM JOURNAL ON COMPUTING, 1993, 22 (06) :1176-1198

← 1 2 →