caa a22 4500 445805129 CHVBK 20180317145154.0 cr unu---uuuuu 170323e20110901xx s 000 0 eng 10.1007/s00453-010-9437-6 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9437-6 On Optimally Partitioning a Text to Improve Its Compression [Elektronische Daten] [Paolo Ferragina, Igor Nitto, Rossano Venturini] 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 Buchsbaum etal. (Proc. of 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 175-184, 2000; J. ACM 50(6):825-851, 2003) in the context of table compression, and then further elaborated and extended to strings and trees by Ferragina etal. (J. ACM 52:688-713, 2005; Proc. of 46th IEEE Symposium on Foundations of Computer Science, pp. 184-193, 2005) and Mäkinen and Navarro (Proc. of 14th Symposium on String Processing and Information Retrieval, pp. 229-241, 2007). Unfortunately, the literature offers poor solutions: namely, we know either a cubic-time algorithm for computing the optimal partition based on dynamic programming (Buchsbaum etal. in J. ACM 50(6):825-851, 2003; Giancarlo and Sciortino in Proc. of 14th Symposium on Combinatorial Pattern Matching, pp.129-143, 2003), or few heuristics that do not guarantee any bounds on the efficacy of their computed partition (Buchsbaum etal. in Proc. of 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 175-184, 2000; J. ACM 50(6):825-851, 2003), or algorithms that are efficient but work in some specific scenarios (such as the Burrows-Wheeler Transform, see e.g. Ferragina etal. in J. ACM 52:688-713, 2005; Mäkinen and Navarro in Proc. of 14th Symposium on String Processing and Information Retrieval, pp. 229-241, 2007) and achieve compression performance that might be worse than the optimal-partitioning by a Ω(log n/log log n) factor. Therefore, computing efficiently the optimal solution is still open (Buchsbaum and Giancarlo in Encyclopedia of Algorithms, pp. 939-942, 2008). In this paper we provide the first algorithm which computes in O(nlog 1+ε n) time and O(n) space, apartition of T whose compressed output is guaranteed to be no more than (1+ε)-worse the optimal one, where ε may be any positive constant fixed in advance. This result holds for any base-compressor C whose compression performance can be bounded in terms of the zero-th or the k-th order empirical entropy of the textT. We will also discuss extensions of our results to BWT-based compressors and to the compression booster of Ferragina etal. (J. ACM 52:688-713, 2005). Springer Science+Business Media, LLC, 2010 Data compression nationallicence Dynamic programming nationallicence Compression boosting nationallicence Table compression nationallicence Empirical entropy nationallicence Burrows-Wheeler transform nationallicence Arithmetic and Huffman coding nationallicence Ferragina Paolo Dipartimento di Informatica, University of Pisa, Largo Bruno Pontecorvo 3, 56127, Pisa, Italy aut Nitto Igor Dipartimento di Informatica, University of Pisa, Largo Bruno Pontecorvo 3, 56127, Pisa, Italy aut Venturini Rossano ISTI-CNR, Via G. Moruzzi 1, 56124, Pisa, Italy aut Algorithmica Springer-Verlag 61/1(2011-09-01), 51-74 0178-4617 61:1<51 2011 61 453 https://doi.org/10.1007/s00453-010-9437-6 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9437-6 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Ferragina Paolo Dipartimento di Informatica, University of Pisa, Largo Bruno Pontecorvo 3, 56127, Pisa, Italy aut NATIONALLICENCE 700 1- Nitto Igor Dipartimento di Informatica, University of Pisa, Largo Bruno Pontecorvo 3, 56127, Pisa, Italy aut NATIONALLICENCE 700 1- Venturini Rossano ISTI-CNR, Via G. Moruzzi 1, 56124, Pisa, Italy aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/1(2011-09-01), 51-74 0178-4617 61:1<51 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer