# Data Compression with a Time Limit
## 2 Data Compression with a Time Limit
### A Data Compression Algorithm with a Time Limit
This step is necessary because there may still be algorithms that are better than the previous one but that involve a non-optimal mix. By definition of a convex surface, there cannot be points below it, while points above the lower polygonal chain will not correspond to optimal algorithms due to a larger resulting dimension. For each possible time budget, we will then have two possible options. It will be possible to use a specific algorithm, or the document can be partitioned into two parts, where each will be compressed by one of the two members of the optimal algorithm pair for that time budget. If we consider the optimization of the compression of multiple documents, an important feature of the resulting polygon chain is the slope of the segments connecting two algorithms. This slope captures the concept of benefit obtained by switching from one algorithm to another. A more significant slope will result in a greater benefit. The optimization of the compression of multiple documents starts from the lower polygon chains built through the process seen previously for each document. The idea is to join these chains to obtain an overall chain representing the entire set of documents. The resulting lower polygon chain will be made up of points representing combinations of algorithms to be used, one for each document involved in the process. Each point of this lower polygon chain will be chosen in order to maximize the benefit for that specific time budget. This maximization is obtained by changing, with respect to the previous combination, only one algorithm. Once the overall lower polygon chain is obtained, the mixing process will be similar to the one seen previously. The optimal algorithms will correspond to the extremes of the segment where the time budget falls. Following the work of [PERSON] and [PERSON] in [1], let us suppose we find ourselves in a situation where we want to compress a single file \(f\) or a large data set \(D\) by using a compressor. In real life, we will have many compressors and setups to choose from, but here, for simplicity let us consider the situation in which we have two possible compressors available, or two possible configurations of a single compressor called, respectively, _setup_1 and _setup_2: it could be easy then to generalize the following discussion to multiple compressors and multiple setups. Suppose setup1 takes less time to compress than setup2, but that setup2 compresses more than setup1. Now, suppose that the execution must finish within a certain time \(t^{\prime}\) (let us call this value _time-budget_). We define \(t_{1}\) as the time taken by setup1, \(t_{2}\) the time taken by setup2. 1. \(t^{\prime}<t_{1}\): it is not possible to compress with either setup, since the time budget is less than the time taken by the fastest compressor (setup1). 2. \(t^{\prime}>t_{2}\): it is possible to compress with both setup1 and setup2. We choose to compress with setup2, since compression is more effective in terms of output size. 3. \(t_{1}<t^{\prime}<t_{2}\): it is not possible to compress with setup2 because the time budget is not sufficient. We therefore decide to use setup1. If we find ourselves in situation 3, the system manages to compress \(f\) (or \(D\)) through setup1; however, the time value \(\Delta(t)=t^{\prime}-t_{1}\) in which the system remains unused is not negligible since the chosen setup finished its execution before the set time \(t^{\prime}\). Compression optimization tries to reduce, if not to eliminate, the \(\Delta(t)\) value, considering not one, but a mix of setups. In our previous example, if we found ourselves in a situation in which the time-budget is \(t_{1}<t^{\prime}<t_{2}\), we could think of adopting a \"mixing\" strategy in which a part of the file \(f\) (or of the data set \(D\)) to be compressed goes as input to setup1, while the remaining part to setup2. This strategy, compared to the classic application of a single compression tool, could lead to the use of the entire time budget initially chosen and to a reduction in the output size.