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

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Fast Lightweight Suffix Array Construction and Checking

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

Burkhardt,  Stefan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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

Kärkkäinen,  Juha
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Baeza-Yates,  R.
Max Planck Society;

Chávez,  E.
Max Planck Society;

Crochemore,  M.
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

Burkhardt, S., & Kärkkäinen, J. (2003). Fast Lightweight Suffix Array Construction and Checking. In Combinatorial Pattern Matching: 14th Annual Symposium, CPM 2003 (pp. 55-69). Heidelberg, Germany: Springer.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-2D03-F
Zusammenfassung
We describe an algorithm that, for any $v\in[2,n]$, constructs the suffix array of a string of length $n$ in $\Oh{vn + n \log n}$ time using $\Oh{v+n/\sqrt{v}}$ space in addition to the input (the string) and the output (the suffix array). By setting $v=\log n$, we obtain an $\Oh{n \log n}$ time algorithm using $\Oh{n/\sqrt{\log n}}$ extra space. This solves the open problem stated by Manzini and Ferragina [ESA\;'02] of whether there exists a lightweight (sublinear extra space) $\Oh{n \log n}$ time algorithm. The key idea of the algorithm is to first sort a sample of suffixes chosen using mathematical constructs called difference covers. The algorithm is not only lightweight but also fast in practice as demonstrated by experiments. Additionally, we describe fast and lightweight suffix array checkers, i.e., algorithms that check the correctness of a suffix array.