Research output: Contribution to journal › Article › peer-review
Time-Universal data compression. / Ryabko, Boris.
In: Algorithms, Vol. 12, No. 6, 116, 01.06.2019.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - Time-Universal data compression
AU - Ryabko, Boris
N1 - Publisher Copyright: © 2019 by the authors. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2019/6/1
Y1 - 2019/6/1
N2 - 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 logm 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.
AB - 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 logm 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.
KW - Data compression
KW - Time-series forecasting
KW - Universal coding
KW - data compression
KW - universal coding
KW - time-series forecasting
UR - http://www.scopus.com/inward/record.url?scp=85077441742&partnerID=8YFLogxK
U2 - 10.3390/a12060116
DO - 10.3390/a12060116
M3 - Article
AN - SCOPUS:85077441742
VL - 12
JO - Algorithms
JF - Algorithms
SN - 1999-4893
IS - 6
M1 - 116
ER -
ID: 22967600