Indexing Compressed Text (Articolo in rivista)

Type
Label
  • Indexing Compressed Text (Articolo in rivista) (literal)
Anno
  • 2005-01-01T00:00:00+01:00 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi
  • 10.1145/1082036.1082039 (literal)
Alternative label
  • P. Ferragina, G. Manzini (2005)
    Indexing Compressed Text
    in Journal of the Association for Computing Machinery; ACM Press, New York (Stati Uniti d'America)
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • P. Ferragina, G. Manzini (literal)
Pagina inizio
  • 552 (literal)
Pagina fine
  • 581 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#url
  • http://dx.doi.org/10.1145/1082036.1082039 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 52 (literal)
Rivista
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#note
  • DOI: http://doi.acm.org/10.1145/1082036.1082039 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#pagineTotali
  • 30 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroFascicolo
  • 4 (literal)
Note
  • Scopu (literal)
  • ISI Web of Science (WOS) (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • Univ. di Pisa Univ. del Piemonte Orientale (literal)
Titolo
  • Indexing Compressed Text (literal)
Abstract
  • We design two compressed data structures for the full-text indexing problem that support efficient substring searches using roughly the space required for storing the text in compressed form. Our first compressed data structure retrieves the occ occurrences of a pattern P[1,p] within a text T[1,n] in O(p + occ log^(1+epsilon) n) time for any chosen epsilon between 0 and 1. This data structure uses at most 5nHk(T) + o(n) bits of storage, where Hk(T) is the kth order empirical entropy of T. The space usage is Theta(n) bits in the worst case and o(n) bits for compressible texts. This data structure exploits the relationship between suffix arrays and the Burrows-Wheeler Transform, and can be regarded as a compressed suffix array. Our second compressed data structure achieves O(p+occ) query time using O(nHk(T)log^(epsilon) n) + o(n) bits of storage for any chosen epsilon between 0 and 1. Therefore, it provides optimal output-sensitive query time using o(n log n) bits in the worst case. This second data structure builds upon the first one and exploits the interplay between two compressors: the Burrows-Wheeler Transform and the LZ78 algorithm. (literal)
Editore
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


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