Engineering Augmented Suffix Sorting Algorithms | Zendy

Felipe A. Louza | Zendy; Guilherme P. Telles | Zendy; Simon Gog | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Engineering Augmented Suffix Sorting Algorithms

Author(s) -

Felipe A. Louza,

Guilherme P. Telles,

Simon Gog

Publication year - 2018

Language(s) - English

Resource type - Conference proceedings

DOI - 10.5753/ctd.2018.3652

Subject(s) - suffix array , suffix , compressed suffix array , computer science , sorting , generalized suffix tree , algorithm , string (physics) , construct (python library) , prefix , set (abstract data type) , suffix tree , string searching algorithm , theoretical computer science , trie , constant (computer programming) , data structure , mathematics , mathematical physics , programming language , philosophy , linguistics

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research