Computer Science – Data Structures and Algorithms
Scientific paper
2009-06-25
Computer Science
Data Structures and Algorithms
Scientific paper
In this paper we investigate the problem of partitioning an input string T in such a way that compressing individually its parts via a base-compressor C gets a compressed output that is shorter than applying C over the entire T at once. This problem was introduced in the context of table compression, and then further elaborated and extended to strings and trees. Unfortunately, the literature offers poor solutions: namely, we know either a cubic-time algorithm for computing the optimal partition based on dynamic programming, or few heuristics that do not guarantee any bounds on the efficacy of their computed partition, or algorithms that are efficient but work in some specific scenarios (such as the Burrows-Wheeler Transform) and achieve compression performance that might be worse than the optimal-partitioning by a $\Omega(\sqrt{\log n})$ factor. Therefore, computing efficiently the optimal solution is still open. In this paper we provide the first algorithm which is guaranteed to compute in $O(n \log_{1+\eps}n)$ time a partition of T whose compressed output is guaranteed to be no more than $(1+\epsilon)$-worse the optimal one, where $\epsilon$ may be any positive constant.
Ferragina Paolo
Nitto Igor
Venturini Rossano
No associations
LandOfFree
On optimally partitioning a text to improve its compression does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On optimally partitioning a text to improve its compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On optimally partitioning a text to improve its compression will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-537475