# Data Compression with a Time Limit
## 2 Data Compression with a Time Limit
### Past Related Work  
Data compression is nowadays a very active field of research: every reduction in the size of digital data allows us to transmit them faster, and therefore has a significant economic impact. In lossless compression algorithms, the decoded output of the compression system is identical, bit for bit, to the original data. In contrast, lossy compression algorithms produce an \"acceptable\" approximation (depending on the application) of the original input. Textual data, including text and HTML pages, are typically not stored in compressed form since they need to be searchable. In contrast, raster data such as audio, images, and video are generally stored in compressed formats and are often created in compressed form by the devices that generate them. Lossy compression is used exclusively for raster data. [PERSON] and [PERSON] in [1] studied for the first time the problem of optimizing the lossless compression of one-dimensional data when there is a time limit within which the compression process must be completed. They experimentally demonstrated that the optimization is possible. [PERSON] in [2] resumed the work of [PERSON] and [PERSON] and extended it to the lossless compression of two-dimensional data (images). In the paper of [PERSON], [PERSON], [PERSON], and [PERSON] [3], a comprehensive model for the total retention cost (TRC) of a data archiving system is established, integrating cloud computing provider charging rates to quantify costs across various compression strategies. This analysis serves as a foundation for developing innovative, cost-efficient alternatives that surpass the effectiveness of existing methods. [PERSON] and [PERSON] [4] investigate the application of compression techniques to enhance middleware-based information exchange in interactive and collaborative distributed systems. In these environments, achieving high compression ratios must be balanced with compression speeds that align with sustainable network transfer rates. Their approach dynamically monitors network and processor resources, evaluates compression efficiency, and autonomously selects the most suitable compression methods to optimize performance. In this paper, we study data compression with a time limit in both the one-dimensional and the two-dimensional case and in the case of both lossless and lossy compression. Lossless compression algorithms are often based on the text substitution model introduced by [PERSON], [PERSON], and [PERSON] in the 1970s. and later used for text and image compression (see for example [5; 6; 7]), or using Huffman or arithmetic coding (see for example [8; 9]). The approach we have presented for the optimization of compression given a time limit is totally independent of the algorithms used in the experiments. For simplicity, we have chosen to use in the experiments some of the most popular compression tools. Obviously, this choice has no impact on the optimization process other than providing data different from others. In this paper, regarding the lossless compression of one-dimensional data, we have used in our experiments _gzip_ (see [10]), _xz_ (based on LZMA: deriving from the seminal work of [PERSON] and [PERSON] [4; 5]), and _bzip2_ (based on the Burrows Wheeler transform, see [11]), _arithmetic coding_ (see [9]). Lossless and lossy image compression algorithms often use the \"modeling + coding\" approach in which a prediction of the current pixel is built consistently by encoder and decoder depending on a chosen context of already coded samples, and then a prediction error, i.e., the difference between the real value of the current pixel and the prediction made, is sent from the encoder to the decoder. As for lossless image compression, we used _PNG_ (see [12]), _TIFF_ (based on the LZW algoritym, see [13]), _JPEG-LS_ (see [14]), _JPEG200_ (see [15]), _BMP_ (see [16]), and _FELICS_ (see [17]) in the testing phase. [PERSON] in [18] presents a review of lossy image compression algorithms.