A Heuristic Algorithm for Recompressing Compressed Data Files
Bekir Tevfik Akgün · 2025
We proposed a recompression methodology based on partitioning of a compressed data file into fixed-sized pages. We select some pages to form a separate file called the sub-file showing in the Figure. After saving the encoded addressing information related to these selected pages and the remaining pages of the input file in an output file, we then compress the newly created sub-file by using an off-the-shelf compression program as 7-Zip in ultra-option. The process ends by adding the compressed sub-file content to the output file. The recompression will be successfully done if the reduction amount obtained from the sub-file compression is higher than the size of the encoded addressing information. We partition an input file into$m$pages, therefore, there are$2^{m}$different sub-files to be formed, compressed and tested. In this work, we propose a heuristic algorithm, which is based on the selection of such a page containing identical data words, for determining pages to form a sub-file. We need only three experiments instead of$2^{m}$experiments due to three data word versions of the algorithm. The time complexity of the algorithm including a linear searching is$O(n)$, where$n$is the size of the input file in bytes. We also proposed an encoding schema to store the addressing information related to the selected pages with minimal memory cost, by designing a hierarchical partition tree of the input file in three levels [1]. Our results showed that we are able to obtain Space Saving rates more than 0.01% on chosen example compressed data files showing a few in the Table, while obtaining 3.3% for one case.