On sliding-window universal data compression with limited memory

被引：19
作者：
Hershkovits, Y
Ziv, J
机构：
[1] Adv Recognit Technol, IL-61398 Tel Aviv, Israel
[2] Technion Israel Inst Technol, Dept Elect Engn, IL-32000 Haifa, Israel
来源：
IEEE TRANSACTIONS ON INFORMATION THEORY | 1998年 / 44卷 / 01期
关键词：
information theory; universal source coding;
D O I：
10.1109/18.650988
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
Nonasymptotic coding and converse theorems are derived for universal data-compression algorithms in cases where the training sequence ("history") that is available to the encoder consists of the most recent segment of the input data string that has been processed, but is not large enough so as to yield the ultimate compression, namely, the entropy of the source.
引用
收藏
页码：66 / 78
页数：13
相关论文
共 13 条
[1]  
COVER T, 1991, ELEMNTS INFORMATION
[2]   UNIVERSAL NOISELESS CODING [J].
DAVISSON, LD .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1973, 19 (06) :783-795
[3]   MINIMAX NOISELESS UNIVERSAL CODING FOR MARKOV SOURCES [J].
DAVISSON, LD .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1983, 29 (02) :211-215
[4]  
GALLAGER RG, 1968, INFORMATION THEORY R
[5]   LOWER BOUNDS FOR CONSTANT WEIGHT CODES [J].
GRAHAM, RL ;
SLOANE, NJA .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1980, 26 (01) :37-43
[6]   On fixed-database universal data compression with limited memory [J].
Hershkovits, Y ;
Ziv, J .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1997, 43 (06) :1966-1976
[7]   ON THE NOTION OF RECURRENCE IN DISCRETE STOCHASTIC PROCESSES [J].
KAC, M .
BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1947, 53 (10) :1002-1010
[8]   UNIVERSAL DATA-COMPRESSION AND REPETITION TIMES [J].
WILLEMS, FMJ .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1989, 35 (01) :54-58
[9]   SOME ASYMPTOTIC PROPERTIES OF THE ENTROPY OF A STATIONARY ERGODIC DATA SOURCE WITH APPLICATIONS TO DATA-COMPRESSION [J].
WYNER, AD ;
ZIV, J .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1989, 35 (06) :1250-1258
[10]   FIXED DATA-BASE VERSION OF THE LEMPEL-ZIV DATA-COMPRESSION ALGORITHM [J].
WYNER, AD ;
ZIV, J .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1991, 37 (03) :878-890
12