Compression of individual sequences via variable-rate coding
The DOI matches its Crossref record; 7 of the 7 references it cites were found in a registry or an index.
Abstract
Compressibility of individual sequences by the class of generalized finite-state information-lossless encoders is investigated. These encoders can operate in a variable-rate mode as well as a fixed-rate one, and they allow for any finite-state scheme of variable-length-to-variable-length coding. For every individual infinite sequencexa quantity\rho(x)is defined, called the compressibility ofx, which is shown to be the asymptotically attainable lower bound on the compression ratio that can be achieved forxby any finite-state encoder. This is demonstrated by means of a constructive coding theorem and its converse that, apart from their asymptotic significance, also provide useful performance criteria for finite and practical data-compression tasks. The proposed concept of compressibility is also shown to play a role analogous to that of entropy in classical information theory where one deals with probabilistic ensembles of sequences rather than with individual sequences. While the definition of\rho(x)allows a different machine for each different sequence to be compressed, the constructive coding theorem leads to a universal algorithm that is asymptotically optimal for all sequences.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“While these sequence prediction algorithms are able to predict the next activity that occurs in a sequence, they do not provide information about when that activity might occur.”
From Forecasting occurrences of activities (2017) · cites this paper as [3]
Citations
Cites
A universal algorithm for sequential data compression
Ziv, J., & Lempel, A. (1977) · IEEE Transactions on Information Theory · doi:10.1109/tit.1977.1055714 · Cited by 5,456
Self-citationInformation Theory and Reliable Communication.
Lee, P. M., & Gallager, R. T. (1970) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2344305 · Cited by 5,399
Information Theory and Reliable Communication
Bell, D. A. (1969) · Electronics and Power · doi:10.1049/ep.1969.0319 · Cited by 4,012
On the Complexity of Finite Sequences
Lempel, A., & Ziv, J. (1976) · IEEE Transactions on Information Theory · doi:10.1109/tit.1976.1055501 · Cited by 2,717
Self-citationCoding theorems for individual sequences
Ziv, J. (1978) · IEEE Transactions on Information Theory · doi:10.1109/tit.1978.1055911 · Cited by 180
Self-citationOn Information Lossless Automata of Finite Order
Even, S. (1965) · IEEE Transactions on Electronic Computers · doi:10.1109/pgec.1965.263996 · Cited by 76
Generalized automata and their information losslessness
Even, S. (1962) · Annual Symposium on Switching Circuit Theory and Logical Design (SWCT) · doi:10.1109/focs.1962.6 · Cited by 13
Cited by
Baeza-Yates, R. A., & Ribeiro-Neto, B. A. (1999) · Cited by 12,609
A Block-sorting Lossless Data Compression Algorithm
Burrows, M. T., & Wheeler, D. J. (1994) · Cited by 3,103
Arithmetic coding for data compression
Witten, I. H., Neal, R. M., & Cleary, J. G. (1987) · Communications of the ACM · doi:10.1145/214762.214771 · Cited by 2,877
Gray, R. M. (1990) · Readings in Speech Recognition · doi:10.1016/b978-0-08-051584-7.50011-5 · Cited by 2,845
A Technique for High-Performance Data Compression
Welch (1984) · Computer · doi:10.1109/mc.1984.1659158 · Cited by 2,182
Data Compression Using Adaptive Coding and Partial String Matching
Cleary, J., & Witten, I. (1984) · IEEE Transactions on Communications · doi:10.1109/tcom.1984.1096090 · Cited by 1,241
TestU01: A C library for empirical testing of random number generators
L'Ecuyer, P., & Simard, R. (2007) · ACM Transactions on Mathematical Software · doi:10.1145/1268776.1268777 · Cited by 1,014
“This number measures the compressibility of the sequence by the Lempel-Ziv compression algorithm given in Ziv and Lempel [1978]. According to Kirschenhofer et al.”
MethodEphraim, Y., & Merhav, N. (2002) · IEEE Transactions on Information Theory · doi:10.1109/tit.2002.1003838 · Cited by 798
Modern information retrieval: the concepts and technology behind search
(2011) · Choice Reviews Online · doi:10.5860/choice.48-6950 · Cited by 786
Navarro, G., & Mäkinen, V. (2007) · ACM Computing Surveys · doi:10.1145/1216370.1216372 · Cited by 735
“The LZ78 parsing [Ziv and Lempel 1978] of text T1,n is a sequence Z [1, n1] of phrases such that T = Z [1] Z [2] ···Z [n1], built as follows.”
BackgroundWitten, I. H., & Bell, T. C. (1991) · IEEE Transactions on Information Theory · doi:10.1109/18.87000 · Cited by 729
Berger, T. (2003) · Wiley Encyclopedia of Telecommunications · doi:10.1002/0471219282.eot142 · Cited by 717
Integrating compression and execution in column-oriented database systems
Abadi, D. J., Madden, S. R., & Ferreira, M. (2006) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/1142473.1142548 · Cited by 714
Ferragina, P., & Manzini, G. (2005) · Journal of the ACM · doi:10.1145/1082036.1082039 · Cited by 686
Replacing suffix trees with enhanced suffix arrays
Abouelhoda, M. I., Kurtz, S., & Ohlebusch, E. (2004) · Journal of Discrete Algorithms · doi:10.1016/s1570-8667(03)00065-0 · Cited by 668
Data compression via textual substitution
Storer, J. A., & Szymanski, T. G. (1982) · Journal of the ACM · doi:10.1145/322344.322346 · Cited by 634
A universal data compression system
Rissanen, J. (1983) · IEEE Transactions on Information Theory · doi:10.1109/tit.1983.1056741 · Cited by 631
How smart are our environments? An updated look at the state of the art
Cook, D. J., & Das, S. K. (2007) · Pervasive and Mobile Computing · doi:10.1016/j.pmcj.2006.12.001 · Cited by 589
A First Course in Information Theory
Yeung, R. W. (2002) · Information Technology: Transmission, Processing and Storage · doi:10.1007/978-1-4419-8608-5 · Cited by 533
MavHome: an agent-based smart home
Cook, D. J., Youngblood, M., Heierman, E. O., Gopalratnam, K., Rao, S., Litvin, A., & Khawaja, F. (2004) · Proceedings of the First IEEE International Conference on Pervasive Computing and Communications, 2003. (PerCom 2003). · doi:10.1109/percom.2003.1192783 · Cited by 525
A locally adaptive data compression scheme
Bentley, J. L., Sleator, D. D., Tarjan, R. E., & Wei, V. K. (1986) · Communications of the ACM · doi:10.1145/5684.5688 · Cited by 523
Reliable communication under channel uncertainty
Lapidoth, A., & Narayan, P. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.720535 · Cited by 519
Bannard, C., & Matthews, D. (2008) · Psychological Science · doi:10.1111/j.1467-9280.2008.02075.x · Cited by 518
“That the best code, given the statistics of natural language, includes multiword elements has been repeatedly shown by both minimum-description-length modeling (e.g., Kit &Wilks, 1999) and related work in text compression (e.g., Ziv & Lempel, 1978).”
BackgroundDiagnosis of Alzheimers Disease from EEG Signals: Where Are We Standing?
Dauwels, J., Vialatte, F., & Cichocki, A. (2010) · Current Alzheimer Research · doi:10.2174/156720510792231720 · Cited by 492
Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Sahai, A., & Shelat, A. A. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.850116 · Cited by 483
The power of amnesia: Learning probabilistic automata with variable memory length
Ron, D., Singer, Y., & Tishby, N. (1997) · Machine Learning · doi:10.1007/bf00114008 · Cited by 447
Merhav, N., & Feder, M. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.720534 · Cited by 438
Online Learning: Theory, Algorithms, and Applications
Shalev‐Shwartz, S. (2007) · Cited by 422
Implementing the PPM data compression scheme
Moffat, A. (1990) · IEEE Transactions on Communications · doi:10.1109/26.61469 · Cited by 420
Interpretation of the Lempel-Ziv Complexity Measure in the Context of Biomedical Signal Analysis
Aboy, M., Hornero, R., Abasolo, D., & Alvarez, D. (2006) · IEEE Transactions on Biomedical Engineering · doi:10.1109/tbme.2006.883696 · Cited by 407
Pearce, M. T. (2005) · City Research Online (City University London) · Cited by 405
Lelewer, D. A., & Hirschberg, D. S. (1987) · ACM Computing Surveys · doi:10.1145/45072.45074 · Cited by 377
Universal prediction of individual sequences
Feder, M., Merhav, N., & Gutman, M. (1992) · IEEE Transactions on Information Theory · doi:10.1109/18.144706 · Cited by 373
Benedetto, D., Caglioti, E., & Loreto, V. (2002) · Physical Review Letters · doi:10.1103/physrevlett.88.048702 · Cited by 364
Ambient intelligence: A survey
Sadri, F. (2011) · ACM Computing Surveys · doi:10.1145/1978802.1978815 · Cited by 363
Grammar-based codes: a new class of universal lossless source codes
Kieffer, J. C., & Yang, E.-H. (2000) · IEEE Transactions on Information Theory · doi:10.1109/18.841160 · Cited by 352
A new sequence distance measure for phylogenetic tree construction
Otu, H. H., & Sayood, K. (2003) · Bioinformatics · doi:10.1093/bioinformatics/btg295 · Cited by 348
Energy-aware lossless data compression
Barr, K. C., & Asanović, K. (2006) · ACM Transactions on Computer Systems · doi:10.1145/1151690.1151692 · Cited by 346
Embedded Computing: A VLIW Approach to Architecture, Compilers and Tools
Fisher, J. A., Faraboschi, P., & Young, C. (2004) · Cited by 333
Arithmetic coding for data compression
Howard, P. G., & Vitter, J. S. (1994) · Proceedings of the IEEE · doi:10.1109/5.286189 · Cited by 323
The role of prediction algorithms in the MavHome smart home architecture
Das, S. K., Cook, D. J., Battacharya, A., Heierman, E. O., & Lin, T.-Y. (2002) · IEEE Wireless Communications · doi:10.1109/mwc.2002.1160085 · Cited by 322
Entropy estimation of symbol sequences
Schürmann, T., & Grassberger, P. (1996) · Chaos: An Interdisciplinary Journal of Nonlinear Science · doi:10.1063/1.166191 · Cited by 319
A Comprehensive Study of the Past, Present, and Future of Data Deduplication
Xia, W., Jiang, H., Feng, D., Douglis, F., Shilane, P., Hua, Y., Fu, M., Zhang, Y., & Zhou, Y. (2016) · Proceedings of the IEEE · doi:10.1109/jproc.2016.2571298 · Cited by 318
Polar codes for channel and source coding
Korada, S. B. (2009) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · doi:10.5075/epfl-thesis-4461 · Cited by 318
The string B-tree: a new data structure for string search in external memory and its applications
Ferragina, P., & Grossi, R. (1999) · Journal of the ACM · doi:10.1145/301970.301973 · Cited by 317
Verdu, S. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.720531 · Cited by 316
LeZi-update: an information-theoretic approach to track mobile users in PCS networks
Bhattacharya, A., & Das, S. K. (1999) · Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking · doi:10.1145/313451.313457 · Cited by 307
Navarro, G., & Raffinot, M. (2002) · Cambridge University Press eBooks · doi:10.1017/cbo9781316135228 · Cited by 291
Offline dictionary-based compression
Larsson, N. J., & Moffat, A. (1999) · DCC · doi:10.1109/dcc.1999.755679 · Cited by 287
Wyner, A. D., & Ziv, J. (1989) · IEEE Transactions on Information Theory · doi:10.1109/18.45281 · Cited by 286
Self-citationEntropy and data compression schemes
Ornstein, D. S., & Weiss, B. (1993) · IEEE Transactions on Information Theory · doi:10.1109/18.179344 · Cited by 281
Jayasankar, U., Thirumal, V., & Ponnurangam, D. (2021) · Journal of King Saud University - Computer and Information Sciences · doi:10.1016/j.jksuci.2018.05.006 · Cited by 279
The Myriad Virtues of Subword Trees
Apostolico, A. (1985) · Combinatorial Algorithms on Words · doi:10.1007/978-3-642-82456-2_6 · Cited by 274
Fast and flexible word searching on compressed text
de Moura, E. S., Navarro, G., Ziviani, N., & Baeza-Yates, R. A. (2000) · ACM Transactions on Information Systems · doi:10.1145/348751.348754 · Cited by 267
A comparative classification of complexity measures
Wackerbauer, R., Witt, A., Atmanspacher, H., Kurths, J., & Scheingraber, H. (1994) · Chaos, Solitons & Fractals · doi:10.1016/0960-0779(94)90023-x · Cited by 262
Bell, T., Witten, I. H., & Cleary, J. G. (1989) · ACM Computing Surveys · doi:10.1145/76894.76896 · Cited by 261
Evaluating location predictors with extensive Wi-Fi mobility data
Song, L., Kotz, D., Jain, R., & He, X. (2005) · IEEE INFOCOM 2004 · doi:10.1109/infcom.2004.1357026 · Cited by 259
Off-line dictionary-based compression
Larsson, N. J., & Moffat, A. (2000) · Proceedings of the IEEE · doi:10.1109/5.892708 · Cited by 259
On Prediction Using Variable Order Markov Models
Begleiter, R., El-Yaniv, R., & Yona, G. (2004) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1491 · Cited by 258
Foundations of Data Quality Management
Fan, W., & Geerts, F. (2012) · Synthesis Lectures on Data Management · doi:10.1007/978-3-031-01892-3 · Cited by 251
Kontoyiannis, I., Algoet, P. H., Suhov, Y. M., & Wyner, A. J. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.669425 · Cited by 251
Practical data compression in wireless sensor networks: A survey
Srisooksai, T., Keamarungsi, K., Lamsrichan, P., & Araki, K. (2012) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2011.03.001 · Cited by 248
Linear Algorithm for Data Compression via String Matching
Rodeh, M., Pratt, V., & Even, S. (1981) · Journal of the ACM · doi:10.1145/322234.322237 · Cited by 247
Programming pearls: algorithm design techniques
Bentley, J. (1984) · Communications of the ACM · doi:10.1145/358234.381162 · Cited by 242
Asymptotically optimal classification for multiple tests with empirically observed statistics
Gutman, M. (1989) · IEEE Transactions on Information Theory · doi:10.1109/18.32134 · Cited by 238
Can We Learn to Beat the Best Stock
Borodin, A., El-Yaniv, R., & Gogan, V. (2004) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1336 · Cited by 237
Universal discrete denoising: known channel
Weissman, T., Ordentlich, E., Seroussi, G., Verdu, S., & Weinberger, M. J. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.839518 · Cited by 233
Unbounded Length Contexts for PPM
Cleary, J. G. (1997) · The Computer Journal · doi:10.1093/comjnl/40.2_and_3.67 · Cited by 232
LESNE, A. (2014) · Mathematical Structures in Computer Science · doi:10.1017/s0960129512000783 · Cited by 227
Convergence properties of functional estimates for discrete distributions
Antos, A., & Kontoyiannis, I. (2001) · Random Structures & Algorithms · doi:10.1002/rsa.10019 · Cited by 224
Crochemore, M. (1986) · Theoretical Computer Science · doi:10.1016/0304-3975(86)90041-1 · Cited by 224
Practical prefetching via data compression
Curewitz, K. M., Krishnan, P., & Vitter, J. S. (1993) · Proceedings of the 1993 ACM SIGMOD international conference on Management of data · doi:10.1145/170035.170077 · Cited by 220
A compression algorithm for DNA sequences and its applications in genome comparison
Chen, X., Kwong, S., & Li, M. (2000) · Proceedings of the fourth annual international conference on Computational molecular biology · doi:10.1145/332306.332352 · Cited by 218
Data Compression Using Dynamic Markov Modelling
Cormack, G. V., & Horspool, R. N. S. (1987) · The Computer Journal · doi:10.1093/comjnl/30.6.541 · Cited by 213
“) The same assumption, that there is an underlying firstorder Markov model for the data, is made in the Ziv-Lempel coding technique [9,10].”
MethodDynamic syslog mining for network failure monitoring
Yamanishi, K., & Maruyama, Y. (2005) · Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining · doi:10.1145/1081870.1081927 · Cited by 213
Foundations of Data Quality Management
Fan, W., & Geerts, F. (2012) · Synthesis lectures on data management · doi:10.2200/s00439ed1v01y201207dtm030 · Cited by 212
Applications of universal context modeling to lossless compression of gray-scale images
Weinberger, M. J., Rissanen, J. J., & Arps, R. B. (1996) · IEEE Transactions on Image Processing · doi:10.1109/83.491334 · Cited by 206
LeZi-Update: An Information-Theoretic Framework for Personal Mobility Tracking in PCS Networks
Bhattacharya, A., & Das, S. K. (2002) · Wireless Networks · doi:10.1023/a:1013759724438 · Cited by 205
Berger, T., & Gibson, J. D. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.720552 · Cited by 205
Asymptotic Estimates in Information Theory with Non-Vanishing Error Probabilities
Tan, V. Y. F. (2014) · Foundations and Trends® in Communications and Information Theory · doi:10.1561/0100000086 · Cited by 205
Grumbach, S., & Tahi, F. (2002) · DCC · doi:10.1109/dcc.1993.253115 · Cited by 204
A corpus for the evaluation of lossless compression algorithms
Arnold, R., & Bell, T. (2002) · Proceedings DCC '97. Data Compression Conference · doi:10.1109/dcc.1997.582019 · Cited by 203
Compression of two-dimensional data
Lempel, A., & Ziv, J. (1986) · IEEE Transactions on Information Theory · doi:10.1109/tit.1986.1057132 · Cited by 201
Self-citationAlgorithms and Data Structures for External Memory
Vitter, J. S. (2008) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000014 · Cited by 199
Compression and Explanation using Hierarchical Grammars
Nevill-Manning, C. G. (1997) · The Computer Journal · doi:10.1093/comjnl/40.2_and_3.103 · Cited by 199
Evaluating Next-Cell Predictors with Extensive Wi-Fi Mobility Data
Song, L., Kotz, D., Jain, R., & He, X. (2006) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2006.185 · Cited by 198
Quantum information theoryPreprint
Nielsen, M. A. (2000) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0011036 · Cited by 196
Minimax Estimation of Functionals of Discrete Distributions
Jiao, J., Venkat, K., Han, Y., & Weissman, T. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2412945 · Cited by 194
Compression of FASTQ and SAM Format Sequencing Data
Bonfield, J. K., & Mahoney, M. V. (2013) · PLoS ONE · doi:10.1371/journal.pone.0059190 · Cited by 194
At the roots of dictionary compression: string attractors
Kempa, D., & Prezza, N. (2018) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3188745.3188814 · Cited by 194
Complexity of strings in the class of Markov sources
Rissanen, J. (1986) · IEEE Transactions on Information Theory · doi:10.1109/tit.1986.1057210 · Cited by 192
On compressing and indexing repetitive sequences
Kreft, S., & Navarro, G. (2012) · Theoretical Computer Science · doi:10.1016/j.tcs.2012.02.006 · Cited by 190
Roldán, É., & Parrondo, J. M. R. (2012) · Physical Review E · doi:10.1103/physreve.85.031129 · Cited by 185
Compressed text indexes: From theory to practice
Ferragina, P., González, R., Navarro, G., & Venturini, R. (2009) · ACM Journal of Experimental Algorithmics · doi:10.1145/1412228.1455268 · Cited by 181
Energy aware lossless data compression
Barr, K., & Asanović, K. (2003) · Proceedings of the 1st international conference on Mobile systems, applications and services · doi:10.1145/1066116.1066123 · Cited by 180
Data compression with finite windows
Fiala, E. R., & Greene, D. H. (1989) · Communications of the ACM · doi:10.1145/63334.63341 · Cited by 178
A Simple Statistical Algorithm for Biological Sequence Compression
Duc Cao, M., Dix, T. I., Allison, L., & Mears, C. (2007) · 2007 Data Compression Conference (DCC'07) · doi:10.1109/dcc.2007.7 · Cited by 177
Ziv, J. (1985) · IEEE Transactions on Information Theory · doi:10.1109/tit.1985.1057034 · Cited by 177
Self-citationZiv, J., & Merhav, N. (1993) · IEEE Transactions on Information Theory · doi:10.1109/18.243444 · Cited by 177
Self-citationModelling sequences and temporal networks with dynamic community structures
Peixoto, T. P., & Rosvall, M. (2017) · Nature Communications · doi:10.1038/s41467-017-00148-9 · Cited by 175
Metadata
- Authors
- Ziv, J., & Lempel, A.
- Affiliations
- AT&T (United States) (US)
- Technion – Israel Institute of Technology (IL)
- Venue
- IEEE Transactions on Information Theory
- Published
- 1978-09
- Volume
- 24
- Issue
- 5
- Pages
- 530-536
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2122962290
- Cited by
- 3,432
- References
- 7
- Citations by year
- 2026: 53 · 2025: 79 · 2024: 76 · 2023: 74 · 2022: 72 · 2021: 106 · 2020: 122 · 2019: 137 · 2018: 92 · 2017: 121 · 2016: 102 · 2015: 108 · 2014: 150 · 2013: 144 · 2012: 136
- FWCI
- 2.08
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- Locations
- IEEE Transactions on Information Theory (publishedVersion)
- Topics
- Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Advanced Data Compression Techniques
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Keywords
- variable-rate coding, compressibility, universal compression
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.