A note on the Ziv - Lempel model for compressing individual sequences (Corresp.)
- 1 March 1983
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 29 (2), 284-287
- https://doi.org/10.1109/tit.1983.1056645
Abstract
The Ziv-Lempel compression algorithm is a string matching and parsing approach to data compression. The symbolwise equivalent for parsing models has been defined by Rissanen and Langdon and gives the same ideal codelength at the same cost in coding parameters. By describing the context and coding parameter for each symbol an insight is provided into how the Ziv-Lempel method achieves compression. This treatment does not employ a probabilistic source for the data string. The Ziv-Lempel method effectively counts symbol instances within parsed phrases. The coding parameter for each symbolwise context is determined by cumulative count ratios. The code string length increase for a symbolyfollowing substrings, under the symbolwise equivalent, is the log of the ratio of node counts in subtreessands\cdot yof the Ziv-Lempel parsing tree. To demonstrate the symbolwise equivalent of the Ziv-Lempel algorithm, we extend the work of Rissanen and Langdon to incomplete parse trees. The result requires the proper handling of the comma when one phrase is the prefix of another phrase.Keywords
This publication has 5 references indexed in Scilit:
- Compression of Black-White Images with Arithmetic CodingIEEE Transactions on Communications, 1981
- Universal modeling and codingIEEE Transactions on Information Theory, 1981
- Compression of individual sequences via variable-rate codingIEEE Transactions on Information Theory, 1978
- Generalized Kraft Inequality and Arithmetic CodingIBM Journal of Research and Development, 1976
- A Mathematical Theory of CommunicationBell System Technical Journal, 1948