{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:39:25Z","timestamp":1760240365106,"version":"build-2065373602"},"reference-count":25,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T00:00:00Z","timestamp":1559088000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Nowadays, a variety of data-compressors (or archivers) is available, each of which has its merits, and it is impossible to single out the best ones. Thus, one faces the problem of choosing the best method to compress a given file, and this problem is more important the larger is the file. It seems natural to try all the compressors and then choose the one that gives the shortest compressed file, then transfer (or store) the index number of the best compressor (it requires log m bits, if m is the number of compressors available) and the compressed file. The only problem is the time, which essentially increases due to the need to compress the file m times (in order to find the best compressor). We suggest a method of data compression whose performance is close to optimal, but for which the extra time needed is relatively small: the ratio of this extra time and the total time of calculation can be limited, in an asymptotic manner, by an arbitrary positive constant. In short, the main idea of the suggested approach is as follows: in order to find the best, try all the data compressors, but, when doing so, use for compression only a small part of the file. Then apply the best data compressors to the whole file. Note that there are many situations where it may be necessary to find the best data compressor out of a given set. In such a case, it is often done by comparing compressors empirically. One of the goals of this work is to turn such a selection process into a part of the data compression method, automating and optimizing it.<\/jats:p>","DOI":"10.3390\/a12060116","type":"journal-article","created":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T11:31:28Z","timestamp":1559129488000},"page":"116","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Time-Universal Data Compression"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7232-9644","authenticated-orcid":false,"given":"Boris","family":"Ryabko","sequence":"first","affiliation":[{"name":"Institute of Computational Technologies of the Siberian Branch of the Russian Academy of Science, 630090 Novosibirsk, Russia"},{"name":"Department of Information Technologies, Novosibirsk State University, 630090 Novosibirsk, Russia"}]}],"member":"1968","published-online":{"date-parts":[[2019,5,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","article-title":"A mathematical theory of communication","volume":"27","author":"Shannon","year":"1948","journal-title":"Bell Syst. Tech. J."},{"key":"ref_2","first-page":"3","article-title":"Optimal encoding for unknown and changing statistics of messages","volume":"2","author":"Fitingof","year":"1966","journal-title":"Probl. Inform. Transm."},{"key":"ref_3","first-page":"3","article-title":"Three approaches to the quantitative definition of information","volume":"1","author":"Kolmogorov","year":"1965","journal-title":"Probl. Inform. Transm."},{"key":"ref_4","first-page":"48","article-title":"A relation between the plausibility of information about a source and encoding redundancy","volume":"4","author":"Krichevsky","year":"1968","journal-title":"Probl. Inform. Transm."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1109\/TCOM.1984.1096090","article-title":"Data compression using adaptive coding and partial string matching","volume":"32","author":"Cleary","year":"1984","journal-title":"IEEE Trans. Commun."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1147\/rd.232.0149","article-title":"Arithmetic coding","volume":"23","author":"Rissanen","year":"1979","journal-title":"IBM J. Res. Dev."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","article-title":"A universal algorithm for sequential data compression","volume":"23","author":"Ziv","year":"1977","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_8","unstructured":"(2019, May 15). A Block-Sorting Lossless Data Compression Algorithm. Available online: https:\/\/www.hpl.hp.com\/techreports\/Compaq-DEC\/SRC-RR-124.pdf."},{"key":"ref_9","first-page":"265","article-title":"Data compression by means of a \u201cbook stack\u201d","volume":"16","author":"Ryabko","year":"1980","journal-title":"Probl. Inf. Transm."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1145\/5684.5688","article-title":"A locally adaptive data compression scheme","volume":"29","author":"Bentley","year":"1986","journal-title":"Commun. ACM"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"792","DOI":"10.1145\/30401.315747","article-title":"Technical correspondence","volume":"30","author":"Ryabko","year":"1987","journal-title":"Commun. ACM"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1109\/18.841160","article-title":"Grammar-based codes: A new class of universal lossless source codes","volume":"46","author":"Kieffer","year":"2000","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1109\/18.841161","article-title":"Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform. i. without context models","volume":"46","author":"Yang","year":"2000","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"2928","DOI":"10.1109\/TIT.2010.2046248","article-title":"Tunstall code, Khodak variations, and random walks","volume":"56","author":"Drmota","year":"2010","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1400","DOI":"10.1109\/18.144725","article-title":"A fast on-line adaptive code","volume":"28","author":"Ryabko","year":"1992","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1109\/18.382012","article-title":"The context-tree weighting method: Basic properties","volume":"41","author":"Willems","year":"1995","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Ryabko, B., Astola, J., and Malyutov, M. (2016). Compression-Based Methods of Statistical Analysis and Prediction of Time Series, Springer International Publishing.","DOI":"10.1007\/978-3-319-32253-7"},{"key":"ref_18","unstructured":"Li, M., and Vitanyi, P. (2008). An Introduction to Kolmogorov Complexity and Its Applications, Springer. [3rd ed.]."},{"key":"ref_19","unstructured":"Calude, C.S. (2002). Information and Randomness\u2014An Algorithmic Perspective, Springer. [2nd ed.]."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"411","DOI":"10.2178\/bsl\/1154698741","article-title":"Calibrating randomness","volume":"12","author":"Downey","year":"2006","journal-title":"Bull. Symb. Log."},{"key":"ref_21","unstructured":"Hutter, M. (2005). Universal Artificial Intelligence: Sequential Decisions based on Algorithmic Probability, Springer."},{"key":"ref_22","unstructured":"Cover, T.M., and Thomas, J.A. (2006). Elements of Information Theory, Wiley-Interscience."},{"key":"ref_23","unstructured":"Mahoney, M. (2019, March 15). Data Compression Programs. Available online: http:\/\/mattmahoney.net\/dc\/."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Krichevsky, R. (1993). Universal Compression and Retrival, Kluwer Academic Publishers.","DOI":"10.1007\/978-94-017-3628-2"},{"key":"ref_25","first-page":"173","article-title":"Twice-universal coding","volume":"3","author":"Ryabko","year":"1984","journal-title":"Probl. Inf. Transm."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/6\/116\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:54:36Z","timestamp":1760187276000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/6\/116"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,29]]},"references-count":25,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2019,6]]}},"alternative-id":["a12060116"],"URL":"https:\/\/doi.org\/10.3390\/a12060116","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2019,5,29]]}}}