Title :
Redundancy of the Lempel-Ziv codes
Author :
Savari, Serap A.
Author_Institution :
Bell Labs., Lucent Technol., Murray Hill, NJ, USA
fDate :
29 Jun-4 Jul 1997
Abstract :
For unifilar, Markov sources, we demonstrate that the redundancy of encoding the first n letters of the source output with the Lempel-Ziv (1977) string matching code (LZ ´77) is O((ln ln n)/(ln n)) and the redundancy with the Lempel-Ziv incremental parsing rule (LZ ´78) is O(1/(ln n)); in both cases, we upper bound the exact form of convergence
Keywords :
Markov processes; convergence of numerical methods; redundancy; source coding; string matching; variable length codes; Lempel-Ziv codes; Lempel-Ziv incremental parsing rule; Lempel-Ziv string matching code; convergence; lossless data compression; redundancy; source output; unifilar Markov sources; universal variable-to-fixed length codes; Code standards; Convergence; Data compression; Decoding; Dictionaries; Encoding; Entropy; Upper bound;
Conference_Titel :
Information Theory. 1997. Proceedings., 1997 IEEE International Symposium on
Conference_Location :
Ulm
Print_ISBN :
0-7803-3956-8
DOI :
10.1109/ISIT.1997.613233
