Engineering a Lightweight Suffix Array Construction Algorithm. (Articolo in rivista)

Type
Label
  • Engineering a Lightweight Suffix Array Construction Algorithm. (Articolo in rivista) (literal)
Anno
  • 2004-01-01T00:00:00+01:00 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi
  • 10.1007/s00453-004-1094-1 (literal)
Alternative label
  • G. Manzini, P. Ferragina (2004)
    Engineering a Lightweight Suffix Array Construction Algorithm.
    in Algorithmica; Springer Verlag, New York NY (Stati Uniti d'America)
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • G. Manzini, P. Ferragina (literal)
Pagina inizio
  • 33 (literal)
Pagina fine
  • 50 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#url
  • http://dx.doi.org/10.1007/s00453-004-1094-1 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 40 (literal)
Rivista
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#pagineTotali
  • 18 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroFascicolo
  • 1 (literal)
Note
  • Scopu (literal)
  • ISI Web of Science (WOS) (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • Universita' del Piemonte Orientale Universita' di Pisa (literal)
Titolo
  • Engineering a Lightweight Suffix Array Construction Algorithm. (literal)
Abstract
  • In this paper we describe a new algorithm for building the suffix array of a string. This task is equivalent to the problem of lexicographically sorting all the suffixes of the input string. Our algorithm is based on a new approach called deep-shallow sorting: we use a \"shallow\" sorter for the suffixes with a short common prefix, and a \"deep\" sorter for the suffixes with a long common prefix. All the known algorithms for building the suffix array either require a large amount of space or are inefficient when the input string contains many repeated substrings. Our algorithm has been designed to overcome this dichotomy. Our algorithm is \"lightweight\" in the sense that it uses very small space in addition to the space required by the suffix array itself. At the same time our algorithm is fast even when the input contains many repetitions: this has been shown by extensive experiments with inputs of size up to 110 Mb. The source code of our algorithm, as well as a C library providing a simple API, is available under the GNU GPL. (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