On optimally partitioning a text to improve its compression (Articolo in rivista)

Type
Label
  • On optimally partitioning a text to improve its compression (Articolo in rivista) (literal)
Anno
  • 2009-01-01T00:00:00+01:00 (literal)
Alternative label
  • Ferragina P.; Nitto I.; Venturini R. (2009)
    On optimally partitioning a text to improve its compression
    in Lecture notes in computer science
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Ferragina P.; Nitto I.; Venturini R. (literal)
Pagina inizio
  • 420 (literal)
Pagina fine
  • 431 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 5757 (literal)
Rivista
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#note
  • 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. (literal)
Note
  • ISI Web of Science (WOS) (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • Department of Computer Science, Univ. Pisa, CNR-ISTI, Pisa (literal)
Titolo
  • On optimally partitioning a text to improve its compression (literal)
Abstract
  • 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. (literal)
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


Prodotto
Autore CNR di
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
Insieme di parole chiave di
data.CNR.it