Implementation of Suffix Array Construction Algorithms

The SDSL (Succinct Data Structure Library) has various implementations of string indices based on suffix arrays. It is currently using third-party algorithms for suffix array construction. This thesis aims at designing an interface for choosing between different construction algorithms and implementing two differnet algorithms.

• The first algorithm (parallelized radix in-place sorting algorithm) is already implemented in SeqAn2 and has to be adapted to the SDSL
• The second algorithm can be a state-of-the-art algorithm of the students choice (in consultation with the advisor)

Both algorithms will have to be tested and evaluated (also against the third-party construction algorithm of the SDSL)

Links

Comments