Istituto di Scienza e Tecnologie dell'Informazione     
Ferragina P., Nitto I., Venturini R. On optimally partitioning a text to improve its compression. In: ESA 2009 - Algorithms. 17th Annual European Symposium (Copenhagen, Denmark, 7-9 September 2009). Proceedings, pp. 420 - 431. (Lecture Notes in Computer Science, vol. 5757). Springer, 2009.
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.
URL: http://www.springerlink.com/content/q80265664736/?sortorder=asc&p_o=30
DOI: 10.1007/978-3-642-04128-0_38
Subject Compression
F.2 Analysis of Algorithms and Problem Complexity

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional