Engineering Augmented Suffix Sorting Algorithms

  • Felipe A. Louza
  • Guilherme P. Telles
  • Simon Gog

Resumo


Strings are prevalent in Computer Science and algorithms for their efficient processing are fundamental in various applications. The results introduced in this work contribute with theoretical improvements and practical advances in building full-text indexes. Our first contribution is an in-place algorithm that computes the Burrows-Wheeler transform and the longest common prefix (LCP) array. Our second contribution is the construction of the suffix array augmented with the LCP array in optimal time and space for strings from constant size alphabets. Our third contribution is a set of algorithms to construct full-text indexes for string collections in optimal theoretical bounds. This work is an extended abstract of the Ph.D. thesis of the first author.

Publicado
26/07/2018
LOUZA, Felipe A.; TELLES, Guilherme P.; GOG, Simon. Engineering Augmented Suffix Sorting Algorithms. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 31. , 2018, Natal. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . ISSN 2763-8820. DOI: https://doi.org/10.5753/ctd.2018.3652.