Contributo in atti di convegno, 2009, ENG, 10.1007/978-3-642-04128-0_38
Ferragina P.; Nitto I.; Venturini R.
Department of Computer Science, Univ. Pisa, Italy; Department of Computer Science, Univ. Pisa, Italy; CNR-ISTI, Pisa, Italy
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 gets a compressed output that is shorter than applying over the entire T at once. This problem was introduced in [2,3] in the context of table compression, and further elaborated and extended to strings and trees by [10,11,20], but it is still open how to efficiently compute the optimal partition [4]. In this paper we provide the first algorithm which is guaranteed to compute in O(n polylog(n)) time a partition of T whose compressed output is guaranteed to be no more than (1 + ε)-worse the optimal one, where ε is any positive constant.
Algorithms. 17th Annual European Symposium - ESA 2009, pp. 420–431, Copenhagen, Denmark, 7-9 September 2009
Analysis of Algorithms and Problem Complexity, Compression
ISTI – Istituto di scienza e tecnologie dell'informazione "Alessandro Faedo"
CNR authors
External links
OAI-PMH: Dublin Core
OAI-PMH: Mods
OAI-PMH: RDF
DOI: 10.1007/978-3-642-04128-0_38
URL: https://link.springer.com/book/10.1007%2F978-3-642-04128-0
External IDs
CNR OAI-PMH: oai:it.cnr:prodotti:44298
DOI: 10.1007/978-3-642-04128-0_38