de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

On Constructing Suffix Arrays in External Memory

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44266

Crauser,  Andreas
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44412

Ferragina,  Paolo
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Crauser, A., & Ferragina, P. (1999). On Constructing Suffix Arrays in External Memory. In J. Nesetril (Ed.), Proceedings of the 7th Annual European Symposium on Algorithms (ESA-99) (pp. 224-235). Berlin: Springer.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-35E5-A
Zusammenfassung
The construction of full-text indexes on very large text collections is nowadays a hot problem. The suffix array~\cite{Manber-Myers} is one of the most attractive full-text indexing data structures due to its simplicity, space efficiency and powerful/fast search operations supported. In this paper we analyze theoretically and experimentally, the I/O-complexity and the working space of six algorithms for constructing large suffix arrays. Additionally, we design a new external-memory algorithm that follows the basic philosophy underlying the algorithm in~\cite{book-info} but in a significantly different manner, thus combining its good practical qualities with efficient worst-case performances. At the best of our knowledge, this is the first study which provides a wide spectrum of possible approaches to the construction of suffix arrays in external memory, and thus it should be helpful to anyone who is interested in building full-text indexes on very large text collections.